LeetCode LCR 111. 除法求值
题目描述
题意分析
已知若干变量之间的除法等式，回答新的比值查询。比值能够沿关系链相乘传递，反向关系取倒数；变量未出现过，或两个变量之间没有关系链时，返回
-1.0。题目保证已知关系无矛盾。可以为每个连通分量选一个代表变量，并维护各变量相对代表的比值，这样同分量内两变量的比值就能通过共同代表相除得到。
解法：带权并查集维护比例
核心思路
[!blue]
先给等式中出现的变量编号。并查集的
p[x]记录父节点，w[x]表示变量x的值除以父变量p[x]的值，不是两个编号的比值。初始时每个变量是自己的根，所以p[x] = x、w[x] = 1。查找根时需要同步压缩权重。先保存旧父节点
origin = p[x]，递归调用find(origin)；递归结束后，w[origin]已表示旧父变量相对根的比值。再将x直接挂到根，执行w[x] *= w[origin]，因为x/origin × origin/root = x/root。乘法必须在旧父节点完成递归之后进行。合并关系
a/b = value时，先查出两端的根pa、pb。此时w[a] = a/pa、w[b] = b/pb。如果把根pa挂到pb下，需要保存的是pa/pb：由a = w[a]×pa、b = w[b]×pb代入已知等式，得到pa/pb = value×w[b]/w[a]。因此更新p[pa] = pb，并设w[pa] = w[b]×value/w[a]，就能把两个分量的比例统一起来。如果两端已经同根，这条等式只提供分量内部已有的关系；输入保证自洽，直接跳过即可。合并方向与公式必须保持配套，不能改变挂接方向却仍使用同一个权重表达式。
查询时先检查变量是否在等式中出现过，未知变量不应被临时加入并查集。两个变量均已定义时，分别调用
find，让它们的权重都相对于各自的根：根不同就无法求值，根相同则返回w[c]/w[d]，共同根的值正好约掉。已定义变量除以自身得到一，未定义变量查询自身仍返回-1.0。
解题步骤
- 按每条等式最多引入两个变量准备数组，将父节点初始化为自身、权重初始化为一。
- 遍历等式，为新变量分配编号，查出两端根和相对根权重。
- 不同根时按代码方向把
pa挂到pb下，并由等式计算新根边权；相同根则跳过。find保存旧父，先递归处理旧父，再更新父指针和两段权重的乘积。- 对每个查询先判断变量是否存在，再比较两次
find的结果；同根返回权重之比，其余返回-1.0。Java 用缺失映射判未定义，Go 从一开始编号，用映射默认的零区分未定义。
代码实现
class Solution {
private int[] p;
private double[] w;
public double[] calcEquation(
List<List<String>> equations, double[] values, List<List<String>> queries) {
int n = equations.size();
// 每条等式最多引入两个新变量。
p = new int[n << 1];
w = new double[n << 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
// 初始时自己是根，x / x = 1。
w[i] = 1.0;
}
Map<String, Integer> mp = new HashMap<>(n << 1);
int idx = 0;
for (int i = 0; i < n; ++i) {
List<String> e = equations.get(i);
String a = e.get(0);
String b = e.get(1);
if (!mp.containsKey(a)) {
mp.put(a, idx++);
}
if (!mp.containsKey(b)) {
mp.put(b, idx++);
}
int pa = find(mp.get(a));
int pb = find(mp.get(b));
if (pa == pb) {
continue;
}
p[pa] = pb;
// 根据权重关系计算 pa / pb = (a / b) * (w[b] / w[a])。
w[pa] = w[mp.get(b)] * values[i] / w[mp.get(a)];
}
int m = queries.size();
double[] res = new double[m];
for (int i = 0; i < m; ++i) {
String c = queries.get(i).get(0);
String d = queries.get(i).get(1);
Integer id1 = mp.get(c);
Integer id2 = mp.get(d);
// 变量从未出现过，值未定义。
if (id1 == null || id2 == null) {
res[i] = -1.0;
} else {
int pa = find(id1);
int pb = find(id2);
res[i] = pa == pb ? w[id1] / w[id2] : -1.0;
}
}
return res;
}
private int find(int x) {
if (p[x] != x) {
int origin = p[x];
p[x] = find(p[x]);
// 递归返回后 w[origin] 已是「相对根」，此处两段倍率相乘。
w[x] *= w[origin];
}
return p[x];
}
}
var p []int
var w []float64
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
n := len(equations)
p = make([]int, (n<<1)+10)
w = make([]float64, (n<<1)+10)
for i := 0; i < (n<<1)+10; i++ {
p[i] = i
// 初始时自己是根，x / x = 1。
w[i] = 1.0
}
mp := make(map[string]int)
// 下标从 1 开始，0 用来表示「未出现过」。
idx := 1
for i, e := range equations {
a, b := e[0], e[1]
if mp[a] == 0 {
mp[a] = idx
idx++
}
if mp[b] == 0 {
mp[b] = idx
idx++
}
pa, pb := find(mp[a]), find(mp[b])
if pa == pb {
continue
}
p[pa] = pb
// 根据权重关系计算 pa / pb = (a / b) * (w[b] / w[a])。
w[pa] = w[mp[b]] * values[i] / w[mp[a]]
}
var res []float64
for _, q := range queries {
c, d := q[0], q[1]
// 变量从未出现过，值未定义。
if mp[c] == 0 || mp[d] == 0 {
res = append(res, -1.0)
} else {
pa, pb := find(mp[c]), find(mp[d])
if pa == pb {
res = append(res, w[mp[c]]/w[mp[d]])
} else {
res = append(res, -1.0)
}
}
}
return res
}
func find(x int) int {
if p[x] != x {
origin := p[x]
p[x] = find(p[x])
// 递归返回后 w[origin] 已是「相对根」，此处两段倍率相乘。
w[x] *= w[origin]
}
return p[x]
}
复杂度分析
设等式数为
E，查询数为Q，实际变量数为V，且V <= 2E。
- 时间复杂度：在题目变量名长度有常数上界、哈希操作按期望成本计算时，为 $O((E+Q)\log(V+1))$。初始化数组为 $O(E)$，每条等式和查询只进行常数次查找；当前实现只做路径压缩，使用对数摊还上界。
- 空间复杂度：辅助空间为 $O(E)$，结果另占 $O(Q)$。父节点和权重数组实际按等式数分配，映射与递归栈为 $O(V)$，因此总空间为 $O(E+Q)$。
当前代码没有按秩或大小选择合并方向，不能直接套用同时采用两种优化时的反阿克曼界。路径压缩单独的分析见 MIT 课程讲义第 5 节。
关键点总结
[!green]
- 权重始终围绕父指针定义，查找完成后才成为相对根的比值。
- 路径压缩通过连乘合并两段比例，合并分量则通过已知等式反推出根之间的比例。
- 查询两端压缩到同一根后，权重相除即可消去共同基准。
- 连通性与变量是否定义需要分别判断，未知变量不能因为名称相同就返回一。
易错点总结
[!yellow]
- 只改父指针而不更新权重，会让父子关系与比例含义不一致。
- 在旧父节点递归完成前乘它的权重，可能只得到相对中间节点的部分比例。
- 直接把原等式值赋给根边权，忽略了两端变量各自到根的倍率。
- 查询前不调用
find，两个权重可能相对不同的中间父节点，不能直接相除。- 对未知变量先建节点再回答自身查询，会把本应未定义的比值误判为一。
- 将数组空间只写成实际变量数
O(V)，没有反映当前实现按等式数预分配容量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 721. 账户合并 | 中等 | 同样按共享关系判断连通，原题只合并分组，本题还要维护节点之间的乘法比例。 |