这是个图的问题，A / B = k 就表示A到B的边的权重是k。
A / B = a, B / C = b, 而A / C就是找A到C的路径，求距离。
思路：
先建图然后找路径。
如果出发点或终点不在图里，那就不存在路径，当前query是-1。
方法1：
DFS找路径。
注意存在起点和终点是同一个点的情况，所以终止条件是1。
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int nq = queries.size();
double[] res = new double[nq];
HashMap<String, List<Pair<String, Double>>> graph = new HashMap<>();
for(int i = 0; i < equations.size(); i++) {
String u = equations.get(i).get(0);
String v = equations.get(i).get(1);
if(!graph.containsKey(u)) graph.put(u, new ArrayList<Pair<String, Double>>());
if(!graph.containsKey(v)) graph.put(v, new ArrayList<Pair<String, Double>>());
graph.get(u).add(new Pair(v, values[i]));
graph.get(v).add(new Pair(u, 1 / values[i]));
}
for(int i = 0; i< nq; i++) {
String uq = queries.get(i).get(0);
String vq = queries.get(i).get(1);
if(!graph.containsKey(uq) || !graph.containsKey(vq)) {
res[i] = -1;
} else if(uq.equals(vq)) {
res[i] = 1;
} else {
HashSet<String> visited = new HashSet<>();
res[i] = dfs(uq, vq, graph, visited);
}
}
return res;
}
double dfs(String start, String end, HashMap<String, List<Pair<String, Double>>> graph,
HashSet<String> visited) {
if(start.equals(end)) return 1;
visited.add(start);
for(Pair<String, Double> nxt : graph.get(start)) {
String child = nxt.getKey();
double value = nxt.getValue();
if(visited.contains(child)) continue;
double d = dfs(child, end, graph, visited);
if(d > 0) return d * value;
}
return -1;
}
}
方法2：
Union Find。
还是找路径，在Union这一步直接把距离都求好，
在Find时一步到位返回距离。
注意存在起点终点是同一点的情况，所以root到它自身的距离是1。
有几处比较难理解的地：
A / B = k, 不找rank了，统一认为B是root, A = B * k, 所以A到B的距离是k, B到A的距离是1/k。
A的root是rA, B的root是rB, 如果把A的root改为rB, 这时权重要怎么改呢，
A到rA的距离是a，B到rB的距离为b，A到B的距离为k。
要更新rA的新root到rB，并更新rA到rB的距离。
A / B = k, A / rA = a, B / rB = b => rA / rB = k / a * b
求A到B的距离时，要用A到rA的距离 ?? rA到rB的距离。（注意不是距离加）
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
//parents["A"] = {"B", 2.0} => A / B = 2.0
//parents["B"] = {"C", 3.0} => B / C = 3.0
HashMap<String, Pair<String, Double>> parents = new HashMap<>();
int n = equations.size();
double[] res = new double[queries.size()];
for(int i = 0; i < n; i++) {
String A = equations.get(i).get(0);
String B = equations.get(i).get(1);
double val = values[i];
//union
if(!parents.containsKey(A) && !parents.containsKey(B)) {
parents.put(A, new Pair(B, val));
parents.put(B, new Pair(B, 1.0));
} else if (!parents.containsKey(A)) {
parents.put(A, new Pair(B, val));
} else if (!parents.containsKey(B)) {
parents.put(B, new Pair(A, 1.0 / val));
} else {
Pair<String, Double> pA = find(A, parents);
Pair<String, Double> pB = find(B, parents);
parents.put(pA.getKey(), new Pair(pB.getKey(), val / pA.getValue() * pB.getValue())); //更新pA的新root为pB,更新pA到pB的距离
}
}
for(int i = 0; i < queries.size(); i++) {
String X = queries.get(i).get(0);
String Y = queries.get(i).get(1);
if(!parents.containsKey(X) || !parents.containsKey(Y)) {
res[i] = -1;
continue;
}
Pair<String, Double> pX = find(X, parents);
Pair<String, Double> pY = find(Y, parents);
if(!pX.getKey().equals(pY.getKey())) { //不是同一group
res[i] = -1;
} else {
res[i] = (pX.getValue() / pY.getValue());
}
}
return res;
}
Pair<String, Double> find(String C, HashMap<String, Pair<String, Double>> parents) {
if(!C.equals(parents.get(C).getKey())) {
Pair<String, Double> p = find(parents.get(C).getKey(), parents);
parents.put(C, new Pair(p.getKey(), parents.get(C).getValue() * p.getValue())); //当前权重*到root的权重
}
return parents.get(C);
}
}
