399. Evaluate Division - jiejackyzhang/leetcode-note GitHub Wiki

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& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

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.

解题思路为根据给定的equation来建立一个双向graph。 对于每个query，如"a/b"，则采用bfs来找a->b的path。

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] res = new double[queries.length];
        //Construct a graph with directed edges, vertices and weights
        Map<String, Set<String>> edges = new HashMap<>();
        Map<String, Double> weights = new HashMap<>();
        for(int i = 0; i < equations.length; i++) {
            addToGraph(edges, weights, equations[i][0], equations[i][1], values[i]);
        }
        for(int i = 0; i < queries.length; i++) {
            String a = queries[i][0];
            String b = queries[i][1];
            if(!edges.containsKey(a) || !edges.containsKey(b)) {
                res[i] = -1.0;
            } else if(a.equals(b)) {
                res[i] = 1.0;
            } else {
                res[i] = bfs(edges, weights, a, b);
            }
        }
        return res;
    }
    
    private void addToGraph(Map<String, Set<String>> edges, Map<String, Double> weights, String a, String b, double value) {
        if(!edges.containsKey(a)) edges.put(a, new HashSet<String>());
            if(!edges.containsKey(b)) edges.put(b, new HashSet<String>());
            edges.get(a).add(b);
            edges.get(b).add(a);
            weights.put(a+"/"+b, value);
            weights.put(b+"/"+a, 1/value);
    }
    
    private double bfs(Map<String, Set<String>> edges, Map<String, Double> weights, String a, String b) {
        if(weights.containsKey(a+"/"+b)) return weights.get(a+"/"+b);
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.add(a);
        while(!q.isEmpty()) {
            String vertex = q.poll();
            visited.add(vertex);
            Set<String> adjacentVertices = edges.get(vertex);
            for(String v : adjacentVertices) {
                if(visited.contains(v)) continue;
                q.add(v);
                if(!weights.containsKey(a+"/"+v)) {
                    double d1 = weights.get(a+"/"+vertex);
                    double d2 = weights.get(vertex+"/"+v);
                    weights.put(a+"/"+v, d1*d2);
                }
                if(v.equals(b)) return weights.get(a+"/"+b);
            }
        }
        return -1.0;
    }
}
⚠️ **GitHub.com Fallback** ⚠️