399. Evaluate Division

Leetcode Graph

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: 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();}

        // start dfs
        distTo.put(v, 1.0);
        dfs(graph, mark, distTo, v);

        // check result
        if (!mark.contains(w)) res[i] = -1.0;
        else res[i] = distTo.get(w);
    }
    return res;
}

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);
        }
    }
}

糖果

糖果
LUA教程

如果不小心安装错 SQL Server 为 Evaluation 的版本,要小心当超过 180 天之后,系统就会无法正常使用了 这几天遇到一个蛮特别的案例,原本收到的问题是 “维护计划” 忽然无法使用,即便是里面没有任何的Task,都无法顺利地执行。但从对方所提供的错误消...… Continue reading

PLUM NIZ静电容键盘怎么样?

Published on September 25, 2020

程序员如何选择合适的机械键盘

Published on September 18, 2020