分享一个LC399的使用并查集的解法

LeetCode 399: Evaluation Division
小弟我今天花了两个小时终于用Union-Find数据结构把这个题做出来了。这应该是我在刷题网提交的最长的一段code了，做出来还有点小兴奋，于是在此分享一下我的code。希望能给各位有所帮助。如有大神指点其中不足那就更好了！

1. class Solution {
   
2.     public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
   
3.         Map<String, Integer> symbolMap = new HashMap<>();
   
4.         int index = 0;
   
5.         for (List<String> equation: equations) {
   
6.             for (String symbol: equation) {
   
7.                 if (!symbolMap.containsKey(symbol)) {
   
8.                     symbolMap.put(symbol, index++);
   
9.                 }
   
10.             }
    
11.         }
    
12.         
    
13.         UF eval = new UF(symbolMap.size());
    
14.         for (int i = 0; i < values.length; i++) {
    
15.             eval.union(symbolMap.get(equations.get(i).get(0)), symbolMap.get(equations.get(i).get(1)), values[i]);
    
16.         }
    
17.         
    
18.         // System.out.println(Arrays.toString(eval.quotients));
    
19.         
    
20.         double[] res = new double[queries.size()];
    
21.         for (int i = 0; i < res.length; i++) {
    
22.             if (!symbolMap.containsKey(queries.get(i).get(0)) || !symbolMap.containsKey(queries.get(i).get(1))) {
    
23.                 res[i] = -1.0;
    
24.             } else {
    
25.                 res[i] = eval.find(symbolMap.get(queries.get(i).get(0)), symbolMap.get(queries.get(i).get(1)));
    
26.             }
    
27.         }
    
28.         
    
29.         return res;
    
30.     }
    
31.    
    
32.     // Use Union-Find to evaluate the quotients, with some modification to the classic implementation of UF.
    
33.     // The tricky part is to maintain the array quotients in path compression and union by rank
    
34.     private class UF {
    
35.         public int parents[], treeSizes[];
    
36.         public double quotients[];  // the quotients array is used to store the result of "node / parents[node]"
    
37.         
    
38.         public UF(int size) {
    
39.             parents = new int[size];
    
40.             treeSizes = new int[size];
    
41.             quotients = new double[size];
    
42.             
    
43.             for (int i = 0; i < size; ++i) {
    
44.                 parents[i] = i;
    
45.                 treeSizes[i] = 1;
    
46.                 quotients[i] = 1.0;
    
47.             }
    
48.         }
    
49.         
    
50.         public void union(int node1, int node2, double q) {
    
51.             Pair<Integer, Double> r1 = getRoot(node1), r2 = getRoot(node2);
    
52.             
    
53.             if (r1.getKey() == r2.getKey()) {
    
54.                 return;
    
55.             }
    
56.             
    
57.             // Note that getRoot return "q1 = node1 / root(node1)" and "q2 = node2 / root(node2)", therefore
    
58.             // q1 / q2 = (node1 / node2) * (root(node2) / root(node1))
    
59.             // since node1 / node2 is given as an input q, so we have both
    
60.             // root(node2) / root(node1) = (q1 / q2) / q
    
61.             // root(node1) / root(node2) = q * q2 / q1
    
62.             // In union by rank we choose either parents[root(node1)] = root(node2) or the other way around, so
    
63.             // we can choose to use either method depending on the situation.
    
64.             if (treeSizes[r1.getKey()] > treeSizes[r2.getKey()]) {
    
65.                 parents[r2.getKey()] = r1.getKey();
    
66.                 treeSizes[r1.getKey()] += treeSizes[r2.getKey()];
    
67.                 quotients[r2.getKey()] = r1.getValue() / r2.getValue() / q;
    
68.             } else {
    
69.                 parents[r1.getKey()] = r2.getKey();
    
70.                 treeSizes[r2.getKey()] += treeSizes[r1.getKey()];
    
71.                 quotients[r1.getKey()] = q * r2.getValue() / r1.getValue();
    
72.             }
    
73.         }
    
74.         
    
75.         public double find(int node1, int node2) {
    
76.             Pair<Integer, Double> r1 = getRoot(node1), r2 = getRoot(node2);
    
77.             if (r1.getKey() != r2.getKey()) {
    
78.                 return -1.0;
    
79.             }
    
80.             
    
81.             // node1 / node2 = (node1 / root(node1)) / (node2 / root(node2)) * root(node2) / root(node1)
    
82.             // Note that root(node1) == root(node2) (otherwise the function returns -1.0 before this line)
    
83.             // Hence, node1 / node2 = (node1 / root(node1)) / (node2 / root(node2))
    
84.             // and these two parts are calculated by the getRoot method.
    
85.             return r1.getValue() / r2.getValue();
    
86.         }
    
87.         
    
88.         // getRoot method now need to find both the root index and the value "node / root(node)"
    
89.         private Pair<Integer, Double> getRoot(int node) {
    
90.             // Use variable q to find node / root(node)
    
91.             // node / root(node) = node/parents[node] * parents[node]/parents[parents[node]] * ...
    
92.             //                   = quotients[node] * quotients[parents[node]] * ...
    
93.             double q = 1.0;
    
94.             while (node != parents[node]) {
    
95.                 quotients[node] = quotients[node]*quotients[parents[node]];
    
96.                 parents[node] = parents[parents[node]];
    
97.                
    
98.                 q *= quotients[node];
    
99.                 node = parents[node];
    
100.             }
     
101.             
     
102.             return new Pair<>(node, q);
     
103.         }
     
104.     }
     
105. }

复制代码