image.png

    1. class Solution {
    2.     public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    3.         int equationsSize = equations.size();
    4.         UnionFind unionFind = new UnionFind(2 * equationsSize); //最大需要两倍空间（每个list有两个字母）
    5.         //第一步，预处理，将变量的值与id进行映射，使得并查集的底层用数组实现，方便编码
    6.         Map<String, Integer> map = new HashMap<>(2 * equationsSize);//初始化map将字母关系转化为数字
    7.         int id = 0; //对应values中索引和映射字母
    8.         for (int i = 0; i < equationsSize; i++) {
    9.             List<String> equation = equations.get(i);
    10.             String var1 = equation.get(0);
    11.             String var2 = equation.get(1);
    12.             if (!map.containsKey(var1)) {
    13.                 map.put(var1, id++);
    14.             }
    15.             if (!map.containsKey(var2)) {
    16.                 map.put(var2, id++);
    17.             }
    18.             //并查询查询之前执行一次合并操作
    19.             unionFind.union(map.get(var1), map.get(var2), values[i]);
    20.         }
    21.         //第二步  做查询
    22.         int queriesSize = queries.size();
    23.         double[] res = new double[queriesSize];
    24.         for (int i = 0; i < queriesSize; i++) {
    25.             String var1 = queries.get(i).get(0);
    26.             String var2 = queries.get(i).get(1);
    27.             //得到需要查询的字母对应的id
    28.             Integer id1 = map.get(var1);
    29.             Integer id2 = map.get(var2);
    30.             if (id1 == null || id2 == null) {
    31.                 res[i] = -1.0;
    32.             } else {
    33.                 //两个节点都存在，则转化为和父节点的关系进行比较
    34.                 res[i] = unionFind.isConnected(id1, id2);
    35.             }
    36.         }
    37.         return res;
    38.     }
    40.     class UnionFind {
    41.         private int[] parent; //表示每个节点对应的父节点的id
    42.         private double[] weight; //表示节点指向父节点的权值
    44.         public UnionFind(int n) {
    45.             this.parent = new int[n];
    46.             this.weight = new double[n];
    47.             //初始化，所有的父节点开始都是指向自己
    48.             for (int i = 0; i < n; i++) {
    49.                 parent[i] = i;
    50.                 weight[i] = 1.0d;
    51.             }
    52.         }
    54.         /**
    55.          * 合并操作
    56.          *
    57.          * @param x，y   两个节点
    58.          * @param value 有向边的权值
    59.          */
    60.         public void union(int x, int y, double value) {
    61.             //找到两个节点对应的父节点
    62.             int rootx = find(x);
    63.             int rooty = find(y);
    64.             if (rootx == rooty) {
    65.                 return;
    66.             }
    67.             parent[rootx] = rooty;
    68.             weight[rootx] = weight[y] * value / weight[x];
    69.         }
    71.         /**
    72.          * 路径压缩
    73.          *
    74.          * @param id 输入节点的id
    75.          * @return 根节点的id
    76.          */
    77.         private int find(int id) {
    78.             if (id != parent[id]) {
    79.                 //根据上一次节点的权值来更新当前节点的权值
    80.                 int preNode = parent[id];
    81.                 parent[id] = find(parent[id]);
    82.                 weight[id] *= weight[preNode];
    83.             }
    84.             return parent[id];
    85.         }
    87.         public double isConnected(int x, int y) {
    88.             int rootX = find(x);
    89.             int rootY = find(y);
    90.             if (rootX == rootY) {
    91.                 return weight[x] / weight[y];
    92.             } else {
    93.                 //说明不在一个集合中
    94.                 return -1;
    95.             }
    96.         }
    97.     }
    98. }

    hot100-除法求值