399. 除法求值
Problem: 399. 除法求值
题目思路比较清晰，用BFS或者Floyd算法即可，但是有一些实现的小细节需要注意。
浮点数精度问题
Java存储浮点数由于使用的是二进制，在运算的时候可能会出现精度的累计误差。一个值可能应该等于0，但是因为浮点数的误差使得其值大于0，而被判定为路径存在。因此，我们设置一个阈值1e-6，把小于该与阈值的数都视为0，以防止误差的累积。
图信息存储的细节
一般情况下，图论相关的题目都会给定节点从1或者0开始，这样存储图不论用邻接矩阵或者邻接列表都很方便（用下标表示节点）。那如果节点的key值不是数字怎么办？
我们第一反应应该是建立key值和数字的映射，实际上这样处理就是可以的。使用一个HashMap来存储即可。
另外，图如果还要存储边权重信息，可以使用pair来作为图的属性。s
Code
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
55
56
57
| class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int n = values.length;
int nvars = 0;
HashMap<String, Integer> variables = new HashMap<>();
for (List<String> equation: equations) {
String a = equation.get(0);
String b = equation.get(1);
if (!variables.containsKey(a)) {
variables.put(a, nvars++);
}
if (!variables.containsKey(b)) {
variables.put(b, nvars++);
}
}
List<Pair<Integer, Double>>[] graph = new ArrayList[nvars];
for (int i = 0; i < nvars; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
int a = variables.get(equations.get(i).get(0));
int b = variables.get(equations.get(i).get(1));
graph[a].add(new Pair(b, values[i]));
graph[b].add(new Pair(a, 1.0 / values[i]));
}
double[][] dist = new double[nvars][nvars];
for (int i = 0; i < nvars; i++) {
for (int j = 0; j < nvars; j++) {
dist[i][j] = -1;
}
}
for (int i = 0; i < nvars; i++) {
for (int j = 0; j < graph[i].size(); j++) {
dist[i][graph[i].get(j).getKey()] = graph[i].get(j).getValue();
}
}
for (int k = 0; k < nvars; k++) {
for (int i = 0; i < nvars; i++) {
for (int j = 0; j < nvars; j++) {
if (dist[i][k] > 1e-6 && dist[k][j] > 1e-6) dist[i][j] = dist[i][k] * dist[k][j];
}
}
}
double[] ans = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
int a = variables.getOrDefault(queries.get(i).get(0), -1);
int b = variables.getOrDefault(queries.get(i).get(1), -1);
if (a == -1 ||b == -1 || dist[a][b] == -1) {
ans[i] = -1;
} else{
ans[i] = dist[a][b];
}
}
return ans;
}
}
|
