Evaluate Division 399

Question

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -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 ].

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],

values = [2.0, 3.0],

queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Solution

这道题已知条件中给了一些除法等式，然后给了另外一些除法等式，问我们能不能根据已知条件求出结果，不能的用-1表示。问题本身是很简单的数学问题，但是写代码来自动实现就需要我们用正确的数据结构和算法，通过观察题目中的例子，我们可以看出如果需要分析的除法式的除数和被除数如果其中任意一个没有在已知条件中出现过，那么返回结果-1，所以我们在分析已知条件的时候，可以使用set来记录所有出现过的字符串，然后我们在分析其他除法式的时候，可以使用递归来做。通过分析得出，不能直接由已知条件得到的情况主要有下面三种：

1) 已知: a / b = 2, b / c = 3， 求 a / c 2) 已知: a / c = 2, b / c = 3， 求 a / b 3) 已知: a / b = 2, a / c = 3， 求 b / c

在递归函数中，我们有一个需要分析的除法表达式，我们遍历所有的已知条件，如果跟某一个已知表达式相等，直接返回结果，或者跟某一个已知表达式正好相反，那么返回已知表达式结果的倒数即可。如果都没有的话，那么就需要间接寻找了，我们需要一个vector来记录已经访问过的表达式，我们先看待求表达式的被除数和当前遍历到的已知表达式的被除数是否相同如果相同，那么就是上面的第一种情况，我们就可以把待求表达式的被除数换成已知表达式的除数，比如已知a/b，要求a/c就换成了求b/c，而求b/c的过程就可以调用递归函数来求解，结果要乘以a/b的值。如果算出来是正数我们直接返回，如果是非正数说明没有找到。对于上面的第一种情况，如果我们要求c/a，那么上面的方法就没法开始查找，所以我们同时也要看待求表达式的除数和当前遍历到的已知表达式的被除数是否相同，比如已知a/b，要求b/c就换成了求a/c，而求b/c的过程就可以调用递归函数来求解，结果要除以a/b的值。

代码如下：

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] res = new double[queries.length];
        Set<String> set = new HashSet<String>();
        // 过滤掉没有遇见过的字符
        for (int i = 0; i < equations.length; i++) {
            set.add(equations[i][0]);
            set.add(equations[i][1]);
        }

        for (int i = 0; i < queries.length; i++) {
            String[] keys = queries[i];
            if (!set.contains(keys[0]) || !set.contains(keys[1])){
                res[i] = -1.0d;
            } else {
                Stack<Integer> stack = new Stack<Integer>();
                res[i] = helper(equations, values, keys, stack);
            }
        }

        return res;
    }

    private double helper (String[][] equations, double[] values, String[] keys, Stack<Integer> stack) {
        for (int i = 0; i < equations.length; i++) {
            // 直接查找，key的顺序有正反
            if (equations[i][0].equals(keys[0]) && equations[i][1].equals(keys[1])) {
                return values[i];
            }
            if (equations[i][0].equals(keys[1]) && equations[i][1].equals(keys[0])) {
                return 1 / values[i];
            }

            // 间接查找，key的顺序也有正反
            if (!stack.contains(i) && equations[i][0].equals(keys[0])) {
                stack.push(i);
                double temp = values[i] * helper(equations, values, new String[]{equations[i][1], keys[1]}, stack);
                if (temp > 0) {
                    return temp;
                } else {
                    stack.pop();
                }
            }

            if (!stack.contains(i) && equations[i][1].equals(keys[0])) {
                stack.push(i);
                double temp = helper(equations, values, new String[]{equations[i][0], keys[1]}, stack) / values[i];
                if (temp > 0) {
                    return temp;
                } else {
                    stack.pop();
                }
            }
        }

        // 查不到，返回-1
        return -1.0d;
    }
}