399. Evaluate Division

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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

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) Java

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, List<String>> eqs = new HashMap<>();
        Map<String, List<Double>> vals = new HashMap<>();
        int idx = 0;
        for (String[] equation : equations) {
            if (!eqs.containsKey(equation[0])) {
                eqs.put(equation[0], new ArrayList<String>());
                vals.put(equation[0], new ArrayList<Double>());
            }
            eqs.get(equation[0]).add(equation[1]);
            vals.get(equation[0]).add(values[idx]);
            if (!eqs.containsKey(equation[1])) {
                eqs.put(equation[1], new ArrayList<String>());
                vals.put(equation[1], new ArrayList<Double>());
            }
            eqs.get(equation[1]).add(equation[0]);
            vals.get(equation[1]).add(1.0/values[idx]);
            idx++;
        }
        double[] rst = new double[queries.length];
        Arrays.fill(rst, -1.0);
        for (int i = 0; i < queries.length; i++) {
            String[] query = queries[i];
            if (query[0].equals(query[1]) && eqs.containsKey(query[0])) {
                rst[i] = 1.0;
                continue;
            }
            dfs(query, eqs, vals, rst, i, 1, query[1], query[0]);
        }
        return rst;
    }

    private boolean dfs(String[] query , Map<String, List<String>> eqs, Map<String, List<Double>> vals, double[] rst, int idx, double prevVal, String target, String parent) {
        if (!eqs.containsKey(query[0])) {
            return false;
        }
        List<String> denomitors = eqs.get(query[0]);
        if (denomitors.indexOf(target) != -1) {
            rst[idx] = prevVal*(vals.get(query[0]).get(denomitors.indexOf(target)));
            return true;
        }
        if (!eqs.containsKey(query[1])) {
            return false;
        }
        for (int i = 0; i < denomitors.size(); i++) {
            String nd = denomitors.get(i);
            if (nd.equals(parent)) {
                continue;
            }
            String[] query2 = new String[] {nd, query[1]};
            if (dfs(query2, eqs, vals, rst, idx, prevVal*(vals.get(query[0]).get(i)), target,query[0])) {
                return true;
            }
        } 
        return false;                               
    }
}

If using UF:

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if(equations==null || equations.length==0) return new double [] {};

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

        for (int i=0;i<equations.length;i++){
            String x1=equations[i][0], x2=equations[i][1];
            root.putIfAbsent(x1, x1);
            root.putIfAbsent(x2, x2);
            map.putIfAbsent(x1, 1.0);
            map.putIfAbsent(x2, 1.0);

            String r1=find(root, x1);
            String r2=find(root, x2);
            root.put(r2, r1);
            map.put(r2, map.get(x1)*values[i]/map.get(x2));
        }

        double[] res=new double[queries.length];
        for (int i=0;i<queries.length;i++){
            res[i]=-1.0;
            String x1=queries[i][0], x2=queries[i][1];
            if (!root.containsKey(x1) || !root.containsKey(x2)) continue;
            String r1=find(root, x1);
            String r2=find(root, x2);
            if (r1.equals(r2))
                res[i]=get(root, map, x2) / get(root, map, x1);
        }
        return res;
    }

    private String find(Map<String, String>root, String var){
        if (root.get(var).equals(var)) return var;
        return find(root, root.get(var));
    }

    private double get(Map<String, String>root, Map<String, Double>map, String var){
        String r=root.get(var);
        double result=map.get(var);

        if (r.equals(var)) return result;
        return result*get(root, map, r);
    }
}

(2) Python



(3) Scala



results matching ""

    No results matching ""