AlgoNote「算法通关手册」题解精讲:0399. 除法求值——用带权并查集维护变量间的倍数关系

原创2026-10-07 17:21:512,267 阅读
文章标签:教程教育

AlgoNote「算法通关手册」题解精讲:0399. 除法求值——用带权并查集维护变量间的倍数关系

本文是「算法通关手册」题解系列的深度解析,聚焦 docs/solutions/0300-0399/evaluate-division.md 这道 LeetCode 0399「除法求值」题。该题在经典并查集的基础上引入了「倍数关系」这一额外信息,是理解**带权并查集(Weighted Union-Find)**的最佳入门例题。读完本文,你将掌握:如何把字符串变量的除法等式建模为图与并查集、如何在 find 时维护并累乘倍数、如何在 union 时推导合并公式,以及如何用它高效回答任意变量间的除法查询。

1. 题目概览

这道题与「等式方程的可满足性」(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「等式方程的可满足性」的递进关系

原文档明确指出,本题是在「等式方程的可满足性」的基础上增加了倍数关系:

也就是说:处理「传递关系」依然用并查集,但本题要求「在使用并查集的同时还要维护倍数关系」。

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

该方法同时完成三件事:

  1. 递推寻找根节点:沿 parent 链向上走到根;
  2. 倍数累乘:multiple 累乘路径上每个节点的 multiples[x],最终得到「origin 与根节点的倍数关系」;
  3. 路径压缩:把 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 的执行流程分三段:

  1. 变量编号与建集:初始化容量为 2 * equations_size 的并查集(每条等式最多引入 2 个新变量,总变量数上界即 2 * n)。用 hash_map 把字符串变量映射为 0, 1, 2, ... 的整数编号,同时调用 union 把每对变量按 values[i] 的倍数关系并入集合;
  2. 查询处理:遍历 queries,若任一变量从未出现过(不在 hash_map 中)直接填入 -1.0,否则调用 is_connected 得到比值;
  3. 返回答案数组 res。

6. 复杂度分析

  • 时间复杂度:O((m+n)×α(m+n))O((m + n) \times \alpha(m + n)),其中 mm 为 equations 的数量、nn 为 queries 的数量,α\alpha 是反 Ackerman 函数(增长极其缓慢,实际应用中可视为常数)。这里的依据是:每个变量至多执行一次 union,每次查询执行一次 is_connected,而带路径压缩的并查集单次操作均摊复杂度约为 O(α)O(\alpha)。
  • 空间复杂度:O(m+n)O(m + n)。主要由 parent、multiples 两个数组(长度约为 2m2m)与 hash_map(变量映射表)构成,res 结果数组长度为 nn。

在本题约束(m,n≤20m, n \le 20)下,该解法无论从时间还是代码简洁度上都极具优势。

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. 延伸学习:仓库中的同源题目与并查集系列

  1. 同题镜像:力扣 LCR 111「除法求值」与本题完全同源,仓库题解见 docs/solutions/LCR/vlzXQL.md,可作为对照练习;
  2. 基础递进题:docs/solutions/0900-0999/satisfiability-of-equality-equations.md(0990 等式方程的可满足性)只判断相等/不等关系,先掌握它再攻克本题会顺畅很多;
  3. 并查集系统教程:docs/05_tree/05_08_union_find.md 覆盖数组实现、森林实现、路径压缩(隔代/完全)与按秩合并的完整原理;
  4. 仓库代码实现: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 分别给出五种并查集实现,可对照阅读;
  5. 实战应用:并查集同样用于 Kruskal 最小生成树算法(见 codes/python/06_graph/Graph-Kruskal.py);
  6. 更多练习:并查集题目合集见 docs/00_preface/00_06_categories_list.md 中的「并查集题目」列表,包含 0547 省份数量、0684 冗余连接、0947 移除最多的同行或同列石头、1202 交换字符串中的元素、0765 情侣牵手等经典题目,完整题解均可在 docs/solutions 目录下找到。

小结:0399「除法求值」通过给并查集增加 multiples 权重数组,把「集合连通性」升级为「集合内相对数值关系」,是理解带权并查集不可多得的经典例题。掌握 find 累乘、union 公式推导与 is_connected 比值查询这三板斧,同类「带权关系推导」问题均可迎刃而解。

登录后查看全文
AlgoNote