# 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: `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.

#### 分析¶

``````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], w = equations[i];
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], w = queries[i];
// 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) {
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教程

#### PLUM NIZ静电容键盘怎么样?

Published on September 25, 2020

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

Published on September 18, 2020