LeetCode 399. Evaluate Division

Problem

LeetCode 399. Evaluate Division

1. 题目简述

给出一系列等式，例如”A / B = k”，A和B都是字符串形式的字母，k是一个double数字。然后给出一些要求计算的等式，如果能根据已知的等式求出来，则计算，不能则返回-1.0。例如：

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

上面的例子给出的输入是如下所示：

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

2. 算法思路

参考视频：花花酱LeetCode

经典老题目，可以用DFS也可以用union-find。

Graph + DFS

我们想一下，如果说我们将给出的所有等式当做一个图，对于每个query，我们对于这两个数的商的计算其实就是找一下这两个数之间是否存在一条路径，如果找到一条路径，则说明二者相除有结果；如果没有，则为-1。

时间复杂度：O(e + q * e)，q是query的数量，e是equation数量。首次生成graph的时候是O(e)的复杂度，q * e是所有query的复杂度，因此每次都要重新做DFS。

空间复杂度：O(e)，就是存储整张图的graph大小。

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap();
        buildGraph(equations, values, graph);

        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            res[i] = getResult(queries.get(i).get(0), queries.get(i).get(1), new HashSet<String>(), graph);
        }

        return res;
    }

    // s1是除数，s2是被除数，找s1/s2之间的一条路径，并将所有double值相乘
    private double getResult(String s1, String s2, Set<String> visited, Map<String, Map<String, Double>> graph) {
        if (!graph.containsKey(s1) || !graph.containsKey(s2) || visited.contains(s1)) {
            return -1.0d;
        }
        if (s1.equals(s2)) {
            return 1.0d;
        }
        // 开始dfs
        visited.add(s1);
        for (Map.Entry<String, Double> nei: graph.get(s1).entrySet()) {
            if (nei.getKey().equals(s2)) {
                return nei.getValue();
            }
            double temp = getResult(nei.getKey(), s2, visited, graph);
            if (temp != -1.0) {
                return temp * nei.getValue();
            }
        }

        return -1.0d;
    }

    private void buildGraph(List<List<String>> equations, double[] values, Map<String, Map<String, Double>> graph) {
        for (int i = 0; i < equations.size(); i++) {
            String s1 = equations.get(i).get(0), s2 = equations.get(i).get(1);
            if (!graph.containsKey(s1)) {
                graph.put(s1, new HashMap<String, Double>());
            }
            if (!graph.containsKey(s2)) {
                graph.put(s2, new HashMap<String, Double>());
            }
            // value为0怎么办？
            graph.get(s1).put(s2, values[i]);
            graph.get(s2).put(s1, 1 / values[i]);
        }
    }
}

Union-Find(待完成)

上面的时间复杂度其实可以再往下降一些的，因为每次都用DFS其实某种程度上很累赘。如果我们使用Union-Find，每个字母和根节点parent相连，每次计算只需要判断二者是否在同一个森林里，如果再，则只需要计算一下每个节点与根节点相除的值，然后二者相除即可；不在同一个森林则是-1.0。

class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

    }
}