Java实现 LeetCode 399 除法求值

399. 除法求值

给出方程式 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& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)，其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。返回vector类型。

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

equations(方程式) = [ [“a”, “b”], [“b”, “c”] ],

values(方程式结果) = [2.0, 3.0],

queries(问题方程式) = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

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

PS：

用map构建关系，然后dfs找

class Solution {

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

        Map<String, Map<String,Double>> graph = doGraph(equations, values);

        double[] res = new double[queries.size()];

        int index = 0;

        for(List<String> q : queries){

            res[index++] = dfs(graph, new HashSet<>(), q.get(0), q.get(1), 1);

        }

        return res;

    }

    public double dfs(Map<String, Map<String,Double>> graph, Set<String> visited, String start, String end, double ans){

        if(!graph.containsKey(start) || !graph.containsKey(end)) return -1;

        Map<String, Double> edges = graph.get(start);

        for(String key : edges.keySet()){

            if(!visited.contains(key)){

                visited.add(key);

                double v = edges.get(key);

                if(key.equals(end)) return ans*v;  //

                double d = dfs(graph, visited, key, end, ans*v);

                if(d != -1) return d;

            }

        }

        return -1;

    }

    public Map<String, Map<String,Double>> doGraph(List<List<String>> equations, double[] values){

        Map<String, Map<String,Double>> graph = new HashMap<>();

        for(int i = 0 ; i < equations.size(); i++){

            String s = equations.get(i).get(0);

            String t = equations.get(i).get(1);

            double val = values[i];

            Map<String, Double> edge1 = graph.getOrDefault(s, new HashMap<>());

            edge1.put(t, val);

            graph.put(s, edge1);

            Map<String, Double> edge2 = graph.getOrDefault(t, new HashMap<>());

            edge2.put(s, 1/val);

            graph.put(t, edge2);

        }

        return graph;

    }

}

巴特西

Java实现 LeetCode 399 除法求值

399. 除法求值

最新文章

热门文章