面试算法111：计算除法

题目

输入两个数组equations和values，其中，数组equations的每个元素包含两个表示变量名的字符串，数组values的每个元素是一个浮点数值。如果equations[i]的两个变量名分别是Ai和Bi，那么Ai/Bi=values[i]。再给定一个数组queries，它的每个元素也包含两个变量名。对于queries[j]的两个变量名Cj和Dj，请计算Cj/Dj的结果。假设任意values[i]大于0。如果不能计算，那么返回-1。
例如，输入数组equations为[[“a”，“b”]，[“b”，“c”]]，数组values为[2.0，3.0]，如果数组queries为[[“a”，“c”]，[“b”，“a”]，[“a”，“e”]，[“a”，“a”]，[“x”，“x”]]，那么对应的计算结果为[6.0，0.5，-1.0，1.0，-1.0]。由数组equations和values可知，a/b=2.0，b/c=3.0，所以，a/c=6.0，b/a=0.5，a/a=1.0。

分析

可以尝试根据数组equations[[“a”，“b”]，[“b”，“c”]]和数组values[2.0，3.0]构建对应的图。因为a/b=2.0，所以图中有一条从节点a到节点b的边，权重为2.0。同时由数学常识可知b/a=1/2，所以图中还有一条由节点b指向节点a的权重为1/2的边。类似地，因为b/c=3.0，所以图中有一条由节点b指向节点c的权重为3.0的边，还有一条由节点c指向节点b的权重为1/3的边。

解

public class Test {
    public static void main(String[] args) {

        List<String> list1 = Arrays.asList("a", "b");
        List<String> list2 = Arrays.asList("b", "c");
        List<List<String>> equations = Arrays.asList(list1, list2);

        double[] values = {2.0, 3.0};

        List<String> list3 = Arrays.asList("a", "c");
        List<String> list4 = Arrays.asList("b", "a");
        List<String> list5 = Arrays.asList("a", "e");
        List<String> list6 = Arrays.asList("a", "a");
        List<String> list7 = Arrays.asList("x", "x");
        List<List<String>> queries = Arrays.asList(list3, list4, list5, list6, list7);

        double[] result = calcEquation(equations, values, queries);
        for (double item : result){
            System.out.println(item);
        }
    }

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String from = queries.get(i).get(0);
            String to = queries.get(i).get(1);
            if (!graph.containsKey(from) || !graph.containsKey(to)) {
                results[i] = -1;
            }
            else {
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, from, to, visited);
            }
        }

        return results;
    }

    private static Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);

            graph.putIfAbsent(var1, new HashMap<>());
            graph.get(var1).put(var2, values[i]);

            graph.putIfAbsent(var2, new HashMap<>());
            graph.get(var2).put(var1, 1.0 / values[i]);
        }

        return graph;
    }

    private static double dfs(Map<String, Map<String, Double>> graph, String from, String to, Set<String> visited) {
        if (from.equals(to)) {
            return 1.0;
        }

        visited.add(from);
        for (Map.Entry<String, Double> entry : graph.get(from).entrySet()) {
            String next = entry.getKey();
            if (!visited.contains(next)) {
                double nextValue = dfs(graph, next, to, visited);
                if (nextValue > 0) {
                    return entry.getValue() * nextValue;
                }
            }
        }

        visited.remove(from);
        return -1.0;
    }

}