leetcode 399. Evaluate Division（除法求值）

这是个图的问题，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);
    }
}

参考链接