LeetCode399 除法求值

链接: https://leetcode-cn.com/problems/evaluate-division/

题面

给定一串等式除法的式子和计算结果,要求你根据这些式子计算出另一些除法的计算结果,如果无法计算则输出-1

解法

带权并查集。
核心思想是维护子节点与父节点上的权重,作为父节点与子节点的比值
然后每次在查找的时候都会进行路径压缩,更新父节点的同时也会更新权重值
union的时候同样需要根据等式来进行权重的更新
还是常规的并查集的操作,合并两棵树和查找父节点
只是在查找和合并的时候需要进行权重的更新
还需要保留原父节点以便进行更新
实现起来细节比较多,可以结合代码理解

代码

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
class Solution {
public:
map<string, int> index;
vector<int> par;
vector<double> weight;
int find(int i) {
if (par[i] == i) return i;
int root = find(par[i]);
weight[i] *= weight[par[i]];
return par[i] = root;
}
void unions(int a, int b, double val) {
int pa = find(a);
int pb = find(b);
weight[pa] = weight[b] * val / weight[a];
par[pa] = pb;
}
void init(vector<vector<string>>& equations) {
int n = equations.size();
par.resize(n * 2);
weight.resize(n * 2);
int id = 0;
for (auto idx: equations) {
if (index.find(idx[0]) == index.end()) {
index[idx[0]] = id++;
}
if (index.find(idx[1]) == index.end()) {
index[idx[1]] = id++;
}
}
for (int i = 0; i < id; i++) {
par[i] = i;
weight[i] = 1;
}
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, double> val;
if (equations.size() < 0) {
return vector<double>(queries.size(), -1);
}
int n = equations.size();
init(equations);
for (int i = 0; i < n; i++) {
auto idx = equations[i];
unions(index[idx[0]], index[idx[1]], values[i]);
}
vector<double> ans;
for (auto idx: queries) {
string a = idx[0], b = idx[1];
if (index.find(a) == index.end() || index.find(b) == index.end()) {
ans.push_back(-1);
}
else {
int pa = index[a], pb = index[b];
if (find(pa) == find(pb)) {
ans.push_back(weight[pa] / weight[pb]);
}
else {
ans.push_back(-1);
}
}
}
return ans;
}
};