🌕🌕🌗 399. 除法求值

难度: 🌕🌕🌗

问题描述

---

解法 1 - DFS 图的遍历

class Solution {
    HashMap<String, HashMap<String, Double>> map = new HashMap<>(); // a - {b, val}
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 思路：
        // 图的遍历
        int len = values.length;
        // 遍历给定条件，记录到 map 中
        for(int i = 0; i < len; i ++) {
            List<String> cur = equations.get(i);
            String first = cur.get(0);
            String next = cur.get(1);
            double val = values[i];

            // 添加 a/b = val
            if(!map.containsKey(first)) {
                HashMap<String, Double> tmp = new HashMap<>();
                map.put(first, tmp);
            }
            HashMap<String, Double> tmpMap = map.get(first);
            tmpMap.put(next, val);
            map.put(first, tmpMap);

            // 添加 b/a = 1/val
            if(!map.containsKey(next)) {
                HashMap<String, Double> tmp = new HashMap<>();
                map.put(next, tmp);
            }
            tmpMap = map.get(next);
            tmpMap.put(first, 1.0 / val);
            map.put(next, tmpMap);
        }
        // 递归依次根据给定要求查找结果
        len = queries.size();
        double[] res = new double[len];
        for(int i = 0; i < len; i ++) {
            List<String> cur = queries.get(i);
            String first = cur.get(0);
            String next = cur.get(1);
            HashSet<String> path = new HashSet<>();
            res[i] = mySol(next, 1.0, first, path);
        }
        return res;
    }

    private double mySol(String end, double cur, String str, HashSet<String> path) {
        // 递归终止条件
        if(!map.containsKey(str) || !map.containsKey(end)) {
            return -1.0; // 如果不存在某个元素，即使的 x/x 也不能得到 1.0 的结果
        }
        if(str.equals(end)) {
            return cur;
        }
        // 遍历从 str 能到达的所有下一个节点
        HashMap<String, Double> tmpMap = map.get(str);
        for(Map.Entry<String, Double> entry: tmpMap.entrySet()) {
            String fur = entry.getKey(); // 下一个能到达的节点
            double val = entry.getValue();
            if(path.contains(fur)) {
                // 说明已经走过，跳
                continue;
            }
            path.add(fur);
            double tmp = mySol(end, cur * val, fur, path);
            if(tmp != -1) {
                return tmp; // 找到路径，直接返回
            }
            path.remove(fur);
        }
        return -1.0;
    }
}

---

输出 1

---

解法 2 - 并查集

class Solution {
    HashMap<String, String> map = new HashMap<>(); // cur - father
    HashMap<String, Double> vm = new HashMap<>(); // cur - val
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 思路：
        // 并查集
        // 遍历给定条件，将 a/b = val 设置为 a -[father] -> b, [a] = val, [b] = 1, 这样求 a/b 时只需执行 [a] * [b] 即可
        // 始终保证根的 val = 1
        // 这样其余所有数都是 自己所能到达的根节点的倍数，即 1*[?]
        // 例：a/b = 3, b/c = 3, e/f = 10, a/e = 1/2
        // 1) 添加 a/b = 3 到并查集中，a.father = b, [a] = 3, [b] = 1 = root
        // 2) 添加 b/c = 3 到并查集中，c.father = b, [c] = 1/3, [b] = 1 = root，一个以 b 展开的图
        // 3) 添加 e/f = 10 到并查集中，e.father = f, [e] = 10, [f] = 1，一个以 f 展开的图，和上一个图所有元素均不相干
        // 4) 添加 a/e = 1/2 到并查集中，由于 a.father = b, e.father = f，此时出现不同根情况，需要合并 2 个图为一个图
        // 即将两个图的根节点连接，最终保留一个根节点，假设保留 e 的根节点 f
        // 已知公式 a / father[a] = [a], e / father[e] = [e], a/e = 1/2
        // 可以得到 father[a] / father[e] = [e] / [a] * val 然后将此结果作为 val 然后连接使得，father[a].father = e
        // 最终保留一个 root = f
        int len = values.length;
        for(int i = 0; i < len; i ++) {
            List<String> cur = equations.get(i);
            String first = cur.get(0);
            String next = cur.get(1);
            double val = values[i];
            // 连接并查集 - 分情况讨论
            if(!map.containsKey(first) && !map.containsKey(next)) {
                // 除数 & 被除数 之前均没有出现过，那么直接添加，这两个节点自成一个图，[next] = 1, [first] = val
                map.put(first, next);
                map.put(next, next);
                vm.put(first, val);
                vm.put(next, 1.0);
            } else if(!map.containsKey(first)) {
                // 不存在第一个数，但是存在第二个数 - 添加第一个数
                map.put(first, next);
                vm.put(first, val);
            } else if(!map.containsKey(next)) {
                // 不存在第二个数，但存在第一个数 - 本来是让第二个数作为根的，但是既然第一个数存在，所以就让第一个数做根，因此翻转
                map.put(next, first);
                vm.put(next, 1.0 / val);
            } else {
                // 除数 & 被除数 均存在，判断是否同一个根节点
                // 如果同根，说明这两个数无需再次添加到并查集中，原本就可以计算得到两者之商
                // 若不同根，需要进行 2 根的合并，最终保留一个根
                String ff = findFather(first);
                String fn = findFather(next);
                if(ff.equals(fn)) {
                    continue;
                }
                // 不同父，连接 2 父
                map.put(ff, fn);
                double tmpVal = vm.get(next) / vm.get(first) * val;
                vm.put(ff, tmpVal);
            }
        }
        // 遍历计算所求
        len = queries.size(); 
        double[] res = new double[len];
        for(int i = 0; i < len; i ++) {
            List<String> cur = queries.get(i);
            String first = cur.get(0);
            String next = cur.get(1);
            // 判断 first & next 是否存在
            if(!map.containsKey(first) || !map.containsKey(next)) {
                res[i] = -1.0;
                continue;
            }
            // 找到 first & next 的父亲
            // System.out.println(i + ": " + first + "  " + next);
            String ff = findFather(first);
            String fn = findFather(next);
            if(!ff.equals(fn)) {
                res[i] = -1.0; // 说明各自在 2 个不相邻的并查集中
                continue;
            }
            // 同一个根节点，计算各自为 根节点的多少倍，由于根节点 val = 1，因此得到的结果可以看作各自的实际值
            double f = getNum(first, 1.0);
            double n = getNum(next, 1.0);
            res[i] = f / n;
        }
        return res;
    }

    private double getNum(String cur, double num) {
        // 递归终止条件
        String father = map.get(cur);
        if(father.equals(cur)) {
            return num;
        }
        // 继续乘以当前节点的值
        return getNum(father, num * vm.get(cur));
    }

    private String findFather(String cur) {
        String father = map.get(cur);
        // 递归终止条件 - 根就是它本身
        if(father.equals(cur)) {
            return cur;
        } 
        // 根不是它本身 - 继续向上找根
        return findFather(father);
    }
}

---

输出 2