友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
399. 除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i]。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。
示例 1：
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000] 解释： 条件：a / b = 2.0, b / c = 3.0 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ] 注意：x 是未定义的 => -1.0
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] 输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
-
1 <= equations.length <= 20 -
equations[i].length == 2 -
1 <= Ai.length, Bi.length <= 5 -
values.length == equations.length -
0.0 < values[i] <= 20.0 -
1 <= queries.length <= 20 -
queries[i].length == 2 -
1 <= Cj.length, Dj.length <= 5 -
Ai,Bi,Cj,Dj由小写英文字母与数字组成
思路分析
没想到这玩意竟然可以用并查集解决！还在想怎么表示代数式呢？
另外，尝试一下带权重的并查集，有意思！
-
一刷
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-16 23:26:48
*/
public double[] calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
int length = equations.size();
UnionFind unionFind = new UnionFind(2 * length);
Map<String, Integer> map = new HashMap<>(2 * length);
int id = 0;
for (int i = 0; i < length; i++) {
List<String> equation = equations.get(i);
String s1 = equation.getFirst();
String s2 = equation.getLast();
if (!map.containsKey(s1)) {
map.put(s1, id);
id++;
}
if (!map.containsKey(s2)) {
map.put(s2, id);
id++;
}
unionFind.union(map.get(s1), map.get(s2), values[i]);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
List<String> query = queries.get(i);
String s1 = query.getFirst();
String s2 = query.getLast();
Integer id1 = map.get(s1);
Integer id2 = map.get(s2);
if (id1 == null || id2 == null) {
result[i] = -1.0;
} else {
result[i] = unionFind.isConnected(id1, id2);
}
}
return result;
}
public static class UnionFind {
private int[] parent;
private double[] weights;
;
public UnionFind(int capacity) {
parent = new int[capacity];
weights = new double[capacity];
for (int i = 0; i < capacity; i++) {
parent[i] = i;
weights[i] = 1.0;
}
}
public void union(int a, int b, double weight) {
int ap = find(a);
int bp = find(b);
if (ap == bp) {
return;
}
parent[ap] = bp;
weights[ap] = weights[b] * weight / weights[a];
}
public double isConnected(int a, int b) {
int ap = find(a);
int bp = find(b);
if (ap == bp) {
return weights[a] / weights[b];
} else {
return -1.0;
}
}
private int find(int x) {
if (x != parent[x]) {
int origin = parent[x];
parent[x] = find(parent[x]);
weights[x] *= weights[origin];
}
return parent[x];
}
}