#Problem

#⭐️⭐️⭐️⭐️

Evaluate division

#Solution

首先先构建weighted directed graph.

a / b = c 会形成两条边, 一条从a到b,weight是c. 另一条从b到a, weight是1.0 / c.

那么query中分几种情况考虑:

  1. 分子分母如果任何一个是不在图里的结点,直接返回-1.0
  2. 分子分母相同,直接返回1.0
  3. 分子分母之间有directed edge, 直接返回weight
  4. 分子分母在图里:
    1. 分子分母之间有path, 从分子出发利用backtracking直到找到分母为止, 把一路的weight给乘起来就是结果. 最后注意cache结果.
    2. 分子分母之间没有path, 返回-1.0

#Code

代码比较长,但思路其实不复杂. 要注意的就是在第4种情况下,什么时候要cache result, 什么时候不需要.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
final Map<String, Map<String, Double>> graph = new HashMap<>();
int n = equations.length;
for (int i = 0; i < n; i++) {
graph.putIfAbsent(equations[i][0], new HashMap<>());
graph.putIfAbsent(equations[i][1], new HashMap<>());
graph.get(equations[i][0]).put(equations[i][1], values[i]);
graph.get(equations[i][1]).put(equations[i][0], 1.0 / values[i]);
}
final double[] res = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
final String[] query = queries[i];
if (!graph.containsKey(query[0]) || !graph.containsKey(query[1])) {
res[i] = -1.0;
} else if (query[0].equals(query[1])) {
res[i] = 1.0;
} else if (graph.containsKey(query[0]) && graph.get(query[0]).containsKey(query[1])) {
res[i] = graph.get(query[0]).get(query[1]);
} else {
double[] tmp = { 1.0 };
double[] localRes = { -1.0 };
Set<String> visited = new HashSet<>();
dfs(query[0], query[1], visited, graph, tmp, localRes);
res[i] = localRes[0];
// Only update when there is a valid path from src to dst.
if (localRes[0] != -1.0) {
graph.get(query[0]).put(query[1], localRes[0]);
graph.get(query[1]).put(query[0], 1.0 / localRes[0]);
}
}
}
return res;
}
// Backtracking
private void dfs(final String src, final String dst, final Set<String> visited, final Map<String, Map<String, Double>> graph, final double[] tmp, final double[] res) {
if (src.equals(dst)) {
res[0] = tmp[0];
return;
}
visited.add(src);
for (final String adj : graph.get(src).keySet()) {
if (!visited.contains(adj)) {
tmp[0] *= graph.get(src).get(adj);
dfs(adj, dst, visited, graph, tmp, res);
tmp[0] /= graph.get(src).get(adj);
}
}
}
}

Comments