399. Evaluate Division

topic
5.1k 词 

<a href="https://techlarry.github.io/tags/Leetcode/" style="color:white" class="tag"> Leetcode </a>



<a href="https://techlarry.github.io/tags/Graph/" style="color:white" class="tag"> Graph </a>



            <p>Equations are given in the format <code class="codehilite">A / B = k</code>, where <code class="codehilite">A</code> and <code class="codehilite">B</code> are variables represented as strings, and <code class="codehilite">k</code> is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return <code class="codehilite">-1.0</code>.</p>

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: String[][] equations, double[] values, String[][] queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return 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.

分析

这道题目的难点在于发现可以用图论解决。对于方程A/B = C，可以把A、B视为图的节点，AB构成图的一条边，C为边的权重。以这种方式构建有向图，那么对于任意方程x/y的问题可以转化为在有向图中，是否存在一条路径x-y，如果存在则返回路径的权重。可以用DFS解决，时间复杂度为O(Qtimes(E+V))，其中Q为查询的数量，E为方程数量，V为方程中字母的数量。

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    if (equations == null || values == null || queries == null) return new double[]{};
    // construct graph
    Map<String, Map<String, Double>> graph = new HashMap<>(); // graph
    for (int i = 0; i < equations.length; i++) {
        String v = equations[i][0], w = equations[i][1];
        if (!graph.containsKey(v)) graph.put(v, new HashMap<>());
        if (!graph.containsKey(w)) graph.put(w, new HashMap<>());
        graph.get(v).put(w, values[i]);
        graph.get(w).put(v, 1.0/values[i]);
    }
    Set<String> mark = new HashSet<>();;
    Map<String, Double> distTo = new HashMap<>();;
    double[] res = new double[queries.length];
    for (int i = 0; i < queries.length; i++) {
        String v = queries[i][0], w = queries[i][1];
        // invalid query
        if (!graph.containsKey(v) || !graph.containsKey(w)) {
            res[i] = -1.0;  continue; }
        // clear dfs result
        if (i > 0) { distTo.clear(); mark.clear();}

    <span class="c1">// start dfs</span>
    <span class="n">distTo</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">v</span><span class="o">,</span> <span class="mf">1.0</span><span class="o">);</span>
    <span class="n">dfs</span><span class="o">(</span><span class="n">graph</span><span class="o">,</span> <span class="n">mark</span><span class="o">,</span> <span class="n">distTo</span><span class="o">,</span> <span class="n">v</span><span class="o">);</span>

    <span class="c1">// check result</span>
    <span class="k">if</span> <span class="o">(!</span><span class="n">mark</span><span class="o">.</span><span class="na">contains</span><span class="o">(</span><span class="n">w</span><span class="o">))</span> <span class="n">res</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="o">;</span>
    <span class="k">else</span> <span class="n">res</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">distTo</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">w</span><span class="o">);</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">res</span><span class="o">;</span>



}


private void dfs(Map<String, Map<String, Double>> graph, Set<String> mark,

Map<String, Double> distTo, String v) {

mark.add(v);

for (String w: graph.get(v).keySet()) {

if (!mark.contains(w)) {

distTo.put(w, distTo.get(v)*graph.get(v).get(w));

dfs(graph, mark, distTo, w);

}

}

}