05 August 2008
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
/**
* key : 当前节点
* value : 其父节点
*/
private Map<String, String> parents = new HashMap<>();
/**
* key : 当前节点
* value : 父节点/当前节点
*/
private Map<String, Double> values = new HashMap<>();
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
for (int i = 0; i < equations.size(); i++) {
union(equations.get(i).get(0), equations.get(i).get(1), values[i]);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
String e = queries.get(i).get(0);
String q = queries.get(i).get(1);
if (!(parents.containsKey(e) && parents.containsKey(q))) {
result[i] = -1;
continue;
}
if (e.equals(q)) {
result[i] = 1;
continue;
}
String r1 = root(e);
String r2 = root(q);
if (!r1.equals(r2)) {
// 如果两者不相等，说明两个节点是不连通的
result[i] = -1;
continue;
}
result[i] = pm(q)/pm(e);
}
return result;
}
private void union(String parent, String child, double value) {
add(parent);
add(child);
String r1 = root(parent);
String r2 = root(child);
if (!r1.equals(r2)) {
parents.put(r2, r1);
values.put(r2, value * (pm(parent)/pm(child)));
}
}
private void add(String x) {
if (!parents.containsKey(x)) {
parents.put(x, x);
values.put(x, 1.0);
}
}
/**
* 找到x的根节点
*/
private String root(String x) {
while (!parents.get(x).equals(x)) {
x = parents.get(x);
}
return x;
}
/**
* 循环的pm函数
*/
private double pm(String x) {
double v = 1;
while (!parents.get(x).equals(x)) {
v*= values.get(x);
x = parents.get(x);
}
return v;
}
// /**
// * 递归的pm函数
// * @param x
// * @return
// */
// private double pm(String x){
// return parents.get(x).equals(x)?1:values.get(x)*pm(parents.get(x));
// }
}