刷leetcode——除法求值 除法程序c++代码

这道题主要涉及的是对树的理解，相关的算法是BFS、DFS、并查集。

原题

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :

给定?a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ??
返回?[6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double> values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)。
其中?equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。
返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

原题url：https://leetcode-cn.com/problems/evaluate-division/

解题

BFS或DFS

一般而言，如果我们知道了a/b和b/c，求a/c的话，可以通过a/b * b/c求得结果。联想成树的话，也就是节点与节点之间是否相连。总的来说，我们需要进行关系的转换。

利用递归的话，可以很好写出代码，我提供一个 DFS 的例子：

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 记录出现了哪些字符串
        Set<String> keySet = new HashSet<>();
        // 记录等式关系，第一层key为除数，第二层key为被除数，第二层value为结果
        Map<String, Map<String, Double>> map = new HashMap<>();
        // 当前是第几个等式，也代表当前要去取第几个结果
        int count = 0;
        // 遍历等式
        for (List<String> equation : equations) {
            // 除数
            String divisor = equation.get(0);
            keySet.add(divisor);
            // 被除数
            String divided = equation.get(1);
            keySet.add(divided);
            // 结果
            double value = values[count];
            // 赋值
            putValue(value, divisor, divided, map);

            count++;
        }
        
        // 计算结果
        double[] result = new double[queries.size()];
        count = 0;
        for (List<String> query : queries) {
            // 除数
            String divisor = query.get(0);
            // 被除数
            String divided = query.get(1);
            // 求结果
            result[count] = cal(divisor, divided, map, new HashSet<>(), keySet);
            count++;
        }

        return result;
    }

    public double cal(
        String divisor, 
        String divided,
        Map<String, Map<String, Double>> map,
        Set<String> divisorSet,
        Set<String> keySet) {
        // 但凡除数、被除数有一个不存在，则直接返回-1.0
        if (!keySet.contains(divisor) || !keySet.contains(divided)) {
            return -1.0;
        }
        // 根据除数，获取valueMap
        Map<String, Double> valueMap = map.get(divisor);
        // 查找是否有现成结果
        Double result = valueMap.get(divided);
        // 如果有就直接返回
        if (result != null) {
            return result;
        }

        // 没有就进行计算
        for (String key : keySet) {
            Double value = valueMap.get(key);
            if (value == null) {
                continue;
            }
            // 如果为-1.0，说明无法计算
            if (value == -1.0) {
                continue;
            }
            // 原本是计算"divisor/divided"，现在可以尝试求出"divisor/key"和"key/divided"
            // 如果key的数据已经计算过，则不再重复计算
            if (divisorSet.contains(key)) {
                continue;
            }
            divisorSet.add(key);
                        // DFS
            double tempResult = cal(key, divided, map, divisorSet, keySet);
            // 记录中间结果
            putValue(tempResult, key, divided, map);
            // 如果为-1.0，说明无法计算
            if (tempResult == -1.0) {
                continue;
            }
            // 记录最终结果
            putValue(value * tempResult, divisor, divided, map);
            // 返回结果
            return value * tempResult;
        }

        // 说明无法计算
        putValue(-1.0, divisor, divided, map);
        return -1.0;
    }

    public void putValue(
        double value,
        String divisor, 
        String divided,
        Map<String, Map<String, Double>> map) {
        // 根据除数赋值
        Map<String, Double> valueMap = map.get(divisor);
        if (valueMap == null) {
            valueMap = new HashMap<>();
            map.put(divisor, valueMap);
            // 记录"divisor/divisor = 1.0"
            valueMap.put(divisor, 1.0);
        }
        valueMap.put(divided, value);
        // 根据被除数赋值
        valueMap = map.get(divided);
        if (valueMap == null) {
            valueMap = new HashMap<>();
            map.put(divided, valueMap);
            // 记录"divided/divided = 1.0"
            valueMap.put(divided, 1.0);
        }
        valueMap.put(divisor, 1.0 / value);
    }
}

提交OK，大家可以尝试写一个 BFS(广度优先搜索) 的版本，需要借用队列记录中间遍历过的节点。

并查集

首先，我们需要了解什么是并查集，可以参考这一篇博客：https://www.cnblogs.com/noKing/p/8018609.html

我的理解是：当我们知道了一堆元素里某几个之间的关联关系，可以将所有元素归并到一个集合中，这个集合中所有元素都是有关系的。

虽然并查集在构造时复杂，消耗一定的时间，但它可以提高了查找的效率。

针对这道题目，我们不仅需要记录 数字 与 数字 之间是否存在关联，还需要记录具体的倍数关系。其实你可以简单理解为：

当我们知道了：
a / b = 3
b / d = 2
c / d = 4
我们可以将 d 看成是根节点，它有子节点 b、c，b有子节点 a

这样是不是好理解多了。

我是利用一个 HashMap 存储了节点之间是否关联，用另一个 HashMap 存储了节点之间的倍数关系，代码如下：

class Solution {
    /**
     * 并查集
     * key : 当前节点
     * value : 其父节点(也可以认为是大哥节点)
     */
    private Map<String, String> parents = new HashMap<>();
    /**
     * 并查集
     * key : 当前节点
     * value : 父节点(也可以认为是大哥节点) /当前节点
     */
    private Map<String, Double> values = new HashMap<>();

    private void add(String x) {
        // 添加节点x
        if (!parents.containsKey(x)) {
            parents.put(x, x);
            values.put(x, 1.0);
        }
    }

    private void union(String parent, String child, double value) {
        // 添加节点
        add(parent);
        add(child);
        // 找到parent和child的最终父节点
        String p1 = find(parent);
        String p2 = find(child);
        // 如果两个结果不等
        if (!p1.equals(p2)) {
            // 记录p1、p2的关系
            parents.put(p2, p1);
            values.put(p2, value * (values.get(parent) / values.get(child)));
        }
    }

    /**
     * 找到x的最终父节点
     */
    private String find(String x) {
        while (!parents.get(x).equals(x)) {
            x = parents.get(x);
        }
        return x;
    }


    /**
     * 一直计算到和根节点的关联
     */
    private double cal(String x) {
        double v = values.get(x);
        while (!parents.get(x).equals(x)) {
            x = parents.get(x);
            v *= values.get(x);
        }
        return v;
    }

    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[] answer = new double[queries.size()];
        // 计算
        for (int i = 0; i < queries.size(); i++) {
            // 需要计算的两个数
            String c1 = queries.get(i).get(0);
            String c2 = queries.get(i).get(1);
            // 如果有一个是不存在的，则没有计算的必要
            if (!parents.containsKey(c1) || !parents.containsKey(c2)) {
                answer[i] = -1;
                continue;
            }
            // 如果两者相等，则返回1
            if (c1.equals(c2)) {
                answer[i] = 1;
                continue;
            }
            // 找到两者的最终父节点，也就是各自的根节点?
            String p1 = find(c1);
            String p2 = find(c2);
            // 如果两者不等，说明两个节点无法构成关联
            if (!p1.equals(p2)) {
                answer[i] = -1;
                continue;
            }
            // 计算两者的结果
            answer[i] = cal(c2) / cal(c1);
        }
        return answer;
    }
}

提交OK，我的这个写法中，并查集是没有进行路径压缩的，有兴趣的同学可以在此之上进行优化，这样当 queries 越大时，查找的效率会越高。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是对树的理解，相关的算法是BFS、DFS、并查集。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道