AlgoNote「算法通关手册」题解精讲:0399. 除法求值——用带权并查集维护变量间的倍数关系
AlgoNote「算法通关手册」题解精讲:0399. 除法求值——用带权并查集维护变量间的倍数关系
本文是「算法通关手册」题解系列的深度解析,聚焦 docs/solutions/0300-0399/evaluate-division.md 这道 LeetCode 0399「除法求值」题。该题在经典并查集的基础上引入了「倍数关系」这一额外信息,是理解**带权并查集(Weighted Union-Find)**的最佳入门例题。读完本文,你将掌握:如何把字符串变量的除法等式建模为图与并查集、如何在
find时维护并累乘倍数、如何在union时推导合并公式,以及如何用它高效回答任意变量间的除法查询。
1. 题目概览
- 题目名称:0399. 除法求值(Evaluate Division)
- 标签:深度优先搜索、广度优先搜索、并查集、图、数组、最短路
- 难度:中等
- 题库位置:本题完整题解位于仓库 docs/solutions/0300-0399/evaluate-division.md,同时在题目分类列表中归入「并查集题目」一栏(见 docs/00_preface/00_06_categories_list.md)。
这道题与「等式方程的可满足性」(0990)高度相关——后者只判断变量间的相等/不等关系,而本题在传递关系之外还要回答具体的数值倍数,是并查集应用从「布尔连通性」升级到「带权关系」的关键转折题。
2. 题目大意与数据约束
题目描述:给定一个变量对数组 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 代替该答案。
数据约束(来自原文档,可视为算法设计上界):
| 约束项 | 取值 |
|---|---|
equations.length |
1 ≤ n ≤ 20 |
equations[i].length |
== 2 |
Ai.length, Bi.length |
1 ≤ len ≤ 5 |
values.length |
== equations.length |
values[i] |
0.0 < values[i] ≤ 20.0 |
queries.length |
1 ≤ n ≤ 20 |
queries[i].length |
== 2 |
| 变量命名 | 由小写英文字母与数字组成 |
注意两个关键约定:未在等式列表中出现的变量是未定义的,因此无法确定它们的答案;values 严格为正数,这保证了倍数关系不会出现零或负权重。
2.1 示例 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.2 示例 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]
示例 2 还体现了两个细节:变量名可以是多个字符("bc"、"cd"),并且查询可以出现「反向除法」(cd / bc),结果即原比值的倒数 0.2 = 1 / 5.0。
3. 解题思路:把除法关系建模为「带权并查集」
3.1 与 0990「等式方程的可满足性」的递进关系
原文档明确指出,本题是在「等式方程的可满足性」的基础上增加了倍数关系:
- 在 docs/solutions/0900-0999/satisfiability-of-equality-equations.md 中,方程只包含
a==b或a!=b,我们用并查集维护的是「是否属于同一集合」这一布尔关系,代码实现见 codes/python/05_tree/tree_unionFind.py; - 本题中,
a / b = 2.0除了说明a、b在同一集合外,还额外携带了「a是b的 2 倍」这一数值权重。因此,并查集在维护父子关系的同时,还必须维护一套倍数关系。
也就是说:处理「传递关系」依然用并查集,但本题要求「在使用并查集的同时还要维护倍数关系」。
3.2 倍数关系的直观推导
以原文档的举例来说明:
a / b = 2.0:说明a == 2b,a和b在同一个集合;b / c = 3.0:说明b == 3c,b和c在同一个集合。
根据上述两式可得:a、b、c 都在一个集合中,且:
a == 2b == 6c
于是 a / c = 6.0、b / a = 0.5,与示例 1 的输出完全一致。
核心思想:将同一集合中的所有变量,其倍数关系都转换为与根节点变量的倍数关系。比如上述例子中都转变为与 a 的倍数关系。这样,任意两个变量的比值,就等于它们各自与根节点倍数关系的商。
3.3 图视角的等价理解(为什么并查集可行)
从图论视角看,可以把每个变量看作节点,把等式 Ai / Bi = values[i] 看作一条从 Ai 指向 Bi、权重为 values[i] 的有向边,其反向边权重为 1 / values[i]。那么:
a / c = (a / b) × (b / c)
即路径上所有边权的乘积,这正对应着「最短路径」类思路(这也是该题标签中包含「图」「最短路」的原因)。但由于所有边权均为正数且查询数量很小,并查集是更简洁、更贴合传递性合并的解法,一次建集后即可在近乎常数时间内回答所有查询。
4. 带权并查集数据结构剖析
4.1 经典并查集基础回顾
经典并查集(Union-Find)用于管理若干不相交集合的合并与查询,核心接口为 union(合并)、find(查找根节点)、is_connected(判断连通性)。其详细原理、路径压缩与按秩合并策略,参见仓库教程 docs/05_tree/05_08_union_find.md,基础实现见 codes/python/05_tree/tree_unionFind.py。
本题的 UnionFind 与之相比多了一个关键数组 multiples,因此常被称为带权并查集。
4.2 两个数组的含义
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.multiples = [1 for _ in range(n)]
parent[x]:元素x的父节点编号,沿用经典森林式并查集;multiples[x]:表示x与其根节点root之间的倍数关系,即满足x == multiples[x] * root。
初始时每个元素自成集合,multiples[x] = 1(自己与自己比值为 1)。注意本题变量名是字符串,需先用哈希表映射为整数编号,见第 5 节主函数的 hash_map。
4.3 find:递推累乘倍数 + 路径压缩
def find(self, x):
multiple = 1.0
origin = x
while x != self.parent[x]:
multiple *= self.multiples[x]
x = self.parent[x]
self.parent[origin] = x
self.multiples[origin] = multiple
return x
该方法同时完成三件事:
- 递推寻找根节点:沿
parent链向上走到根; - 倍数累乘:
multiple累乘路径上每个节点的multiples[x],最终得到「origin与根节点的倍数关系」; - 路径压缩:把
origin直接挂到根节点下,并同步更新multiples[origin]为累乘结果。后续再查询origin时一步即可到达根节点。
这相当于经典并查集「完全压缩」思路的带权版本——压缩的不只是父指针,还包括该节点与根的倍数权重。
4.4 union:合并时的倍数公式推导
def union(self, x, y, multiple):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.parent[root_x] = root_y
self.multiples[root_x] = multiple * self.multiples[y] / self.multiples[x]
return
合并逻辑分两步:如果两个节点已属于同一集合(root_x == root_y),说明 x / y 的比值已经隐含在倍数关系中,无需处理;否则把 root_x 挂到 root_y 下,并推导 root_x 的新倍数。
公式推导(这是本题的灵魂):已知 x / y = multiple,且
x == multiples[x] * root_x
y == multiples[y] * root_y
代入得:
(multiples[x] * root_x) / (multiples[y] * root_y) = multiple
=> root_x / root_y = multiple * multiples[y] / multiples[x]
因此新根 root_y 相对 root_x 的倍数关系为:
multiples[root_x] = multiple * multiples[y] / multiples[x]
4.5 is_connected:同集合返回倍数比
def is_connected(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
return -1.0
return self.multiples[x] / self.multiples[y]
查询时先判断连通性:不属于同一集合返回 -1.0;属于同一集合时,由于 x、y 都已通过 find 完成路径压缩(其 multiples 均已更新为与根的直接倍数),答案即为:
x / y = multiples[x] / multiples[y]
这正是示例 1 中 a / a = 1.0 的来源(multiples[x] / multiples[x] == 1.0)。
5. 完整代码与逐行讲解
以下代码完整继承自原文档(docs/solutions/0300-0399/evaluate-division.md),可直接在 LeetCode 环境下运行(需引入 List 类型,如 from typing import List):
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.multiples = [1 for _ in range(n)]
def find(self, x):
multiple = 1.0
origin = x
while x != self.parent[x]:
multiple *= self.multiples[x]
x = self.parent[x]
self.parent[origin] = x
self.multiples[origin] = multiple
return x
def union(self, x, y, multiple):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.parent[root_x] = root_y
self.multiples[root_x] = multiple * self.multiples[y] / self.multiples[x]
return
def is_connected(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
return -1.0
return self.multiples[x] / self.multiples[y]
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
equations_size = len(equations)
hash_map = dict()
union_find = UnionFind(2 * equations_size)
id = 0
for i in range(equations_size):
equation = equations[i]
var1, var2 = equation[0], equation[1]
if var1 not in hash_map:
hash_map[var1] = id
id += 1
if var2 not in hash_map:
hash_map[var2] = id
id += 1
union_find.union(hash_map[var1], hash_map[var2], values[i])
queries_size = len(queries)
res = []
for i in range(queries_size):
query = queries[i]
var1, var2 = query[0], query[1]
if var1 not in hash_map or var2 not in hash_map:
res.append(-1.0)
else:
id1 = hash_map[var1]
id2 = hash_map[var2]
res.append(union_find.is_connected(id1, id2))
return res
主函数 calcEquation 的执行流程分三段:
- 变量编号与建集:初始化容量为
2 * equations_size的并查集(每条等式最多引入 2 个新变量,总变量数上界即2 * n)。用hash_map把字符串变量映射为0, 1, 2, ...的整数编号,同时调用union把每对变量按values[i]的倍数关系并入集合; - 查询处理:遍历
queries,若任一变量从未出现过(不在hash_map中)直接填入-1.0,否则调用is_connected得到比值; - 返回答案数组
res。
6. 复杂度分析
- 时间复杂度:,其中 为
equations的数量、 为queries的数量, 是反Ackerman函数(增长极其缓慢,实际应用中可视为常数)。这里的依据是:每个变量至多执行一次union,每次查询执行一次is_connected,而带路径压缩的并查集单次操作均摊复杂度约为 。 - 空间复杂度:。主要由
parent、multiples两个数组(长度约为 )与hash_map(变量映射表)构成,res结果数组长度为 。
在本题约束()下,该解法无论从时间还是代码简洁度上都极具优势。
7. 边界情况与易错点
结合原文档的示例与约束,总结以下几类必须处理的边界:
| 场景 | 结果 | 说明 |
|---|---|---|
| 查询变量从未在等式中出现 | -1.0 |
如示例 1 中 a / e、x / x,x 未定义故为 -1.0(而不是 1.0) |
| 两变量在不同集合 | -1.0 |
is_connected 中 root_x != root_y 分支 |
同一变量相除 a / a |
1.0 |
当 a 已定义时,multiples[x] / multiples[x] == 1.0 |
反向查询 cd / bc |
原比值的倒数 | 示例 2 输出 0.2,由倍数比直接得出 |
| 变量名为多字符 | 正常处理 | 如 "bc"、"cd",依赖哈希表编号而非单字符假设 |
另一个容易忽略的点:由于 values[i] > 0,所有倍数均为正数,因此不需要处理零值或负数路径,也避免了除零风险。
8. 延伸学习:仓库中的同源题目与并查集系列
- 同题镜像:力扣 LCR 111「除法求值」与本题完全同源,仓库题解见 docs/solutions/LCR/vlzXQL.md,可作为对照练习;
- 基础递进题:docs/solutions/0900-0999/satisfiability-of-equality-equations.md(0990 等式方程的可满足性)只判断相等/不等关系,先掌握它再攻克本题会顺畅很多;
- 并查集系统教程:docs/05_tree/05_08_union_find.md 覆盖数组实现、森林实现、路径压缩(隔代/完全)与按秩合并的完整原理;
- 仓库代码实现:codes/python/05_tree/tree_unionFind.py、codes/python/05_tree/tree_unionFind_QuickFind.py、codes/python/05_tree/tree_unionFind_QuickUnion.py、codes/python/05_tree/tree_unionFind_UnoinByRank.py、codes/python/05_tree/tree_unionFind_UnoinBySize.py 分别给出五种并查集实现,可对照阅读;
- 实战应用:并查集同样用于 Kruskal 最小生成树算法(见 codes/python/06_graph/Graph-Kruskal.py);
- 更多练习:并查集题目合集见 docs/00_preface/00_06_categories_list.md 中的「并查集题目」列表,包含 0547 省份数量、0684 冗余连接、0947 移除最多的同行或同列石头、1202 交换字符串中的元素、0765 情侣牵手等经典题目,完整题解均可在 docs/solutions 目录下找到。
小结:0399「除法求值」通过给并查集增加 multiples 权重数组,把「集合连通性」升级为「集合内相对数值关系」,是理解带权并查集不可多得的经典例题。掌握 find 累乘、union 公式推导与 is_connected 比值查询这三板斧,同类「带权关系推导」问题均可迎刃而解。