LeetCode-Go 题解精讲:0399 Evaluate Division 加权并查集求除法表达式
LeetCode-Go 题解精讲:0399 Evaluate Division 加权并查集求除法表达式
导读
本文以 LeetCode 第 399 题 Evaluate Division(除法求值)为研究对象,完整讲解题目语义、两种主流解题思路(DFS 建图与加权并查集),并结合本仓库 399. Evaluate Division.go 的源码级实现,推导带权并查集 union() 的权重公式与 find() 路径压缩原理。读完本文,你不仅能 AC 该题,还能掌握一套可复用的「带权重并查集」模板,用于处理任何形如 A / B = k 的变量间倍数关系推导问题。
题目回顾
原题出自 LeetCode 399。给定若干形如 A / B = k 的方程式,其中 A、B 是字符串表示的变量,k 是浮点数。再给定若干查询 queries,每个查询形如 C / D,要求返回计算结果;如果结果不存在,则返回 -1.0。
示例:
已知:
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]
对应输入为:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]
约束与保证:
equations.size() == values.size(),即每个方程式与一个结果值一一对应;- 所有
values均为正数; - 输入总是有效的:除法运算中不会出现除数为 0 的情况,方程式之间不存在矛盾。
题目本质:变量间的倍数关系推导
题目给出的 A / B = k 本质上描述的是两个变量之间的相对倍数关系。例如 a / b = 2.0 表示「a 是 b 的 2 倍」,b / c = 3.0 表示「b 是 c 的 3 倍」,由此可以链式推导出 a / c = 6.0。
把每个变量看作图上的节点,A / B = k 就是节点 A 指向节点 B 的一条带权有向边,权值为 k。于是任意查询 X / Y 就等价于:在图上寻找一条从节点 X 到节点 Y 的路径,若存在,则结果为路径上所有边权值的累乘;若不存在(包括变量根本未出现过的情况),则返回 -1.0。
基于这一建模,原文档给出了两种典型解法:DFS 搜索与并查集(Union-Find)。下面先概述 DFS 思路,再重点结合本仓库源码剖析加权并查集实现。
解法一:DFS 建图搜索
DFS 做法思路直观:
- 建图:将每个变量视为节点,每条
equations[i]视为一条有向边。边A -> B权值为values[i],同时补一条反向边B -> A,权值为1 / values[i](因为B / A = 1 / k)。 - 查询:对每个
query = [X, Y],从节点X出发 DFS 搜索节点Y。搜索过程中把经过的边权值累乘,到达Y时累乘结果即为答案。 - 无解判定:若搜索结束仍无法到达
Y,返回-1.0;若X或Y压根不在节点集合中(从未在equations中出现过),同样返回-1.0。
DFS 的时间复杂度为 O(queries × (V + E)),当查询较多、图较大时效率偏低,因此更推荐使用并查集将预处理复杂度降到近线性。
解法二:加权并查集(本仓库实现)
原文档指出并查集做法的核心:先把所有有倍数关系的节点做 union() 操作,再借助「共同根节点 + 各自到根的倍数」推导任意两变量的比值。本仓库的 399. Evaluate Division.go 正是这一思路的完整实现,下面逐层拆解。
数据结构设计
源码第 3-6 行定义了带权并查集结构:
type stringUnionFind struct {
parents map[string]string // 记录每个节点的父节点
vals map[string]float64 // 记录当前节点相对父节点的倍数(节点值 / 父节点值)
}
与经典并查集不同,这里多了一张 vals 表。vals[x] 的含义是 x / parents[x] 的值,即节点 x 相对其父节点的倍数。当 x 是根节点时(parents[x] == x),规定 vals[x] = 1.0,表示 x / x = 1。
由于题目变量是字符串而非整数下标,这里用 map[string]string 而非数组实现并查集,这是本题与常规整数并查集最大的差异点,也体现了本仓库对该题“字符串变量”场景的针对性设计。
add:节点注册
func (suf stringUnionFind) add(x string) {
if _, ok := suf.parents[x]; ok {
return
}
suf.parents[x] = x
suf.vals[x] = 1.0
}
add() 负责注册新节点:若 x 已存在则跳过;否则令 x 自指(成为一棵树的根),并令 vals[x] = 1.0,即「根节点与自身的比值为 1」。
find:查找根 + 路径压缩 + 权重累乘
func (suf stringUnionFind) find(x string) string {
p := suf.parents[x]
if x != p {
pp := suf.find(p)
suf.vals[x] *= suf.vals[p]
suf.parents[x] = pp
}
return suf.parents[x]
}
find(x) 完成两件事:
- 查找根节点:递归向上,直到找到
parents[x] == x的根; - 路径压缩:回溯过程中把
x直接指向根pp,摊平树结构; - 权重修正:关键在
suf.vals[x] *= suf.vals[p]这一步。递归返回时suf.vals[p]已更新为p / 根的值,而suf.vals[x]原本是x / p,两者相乘恰好得到x / 根。因此路径压缩后,vals[x]语义升级为「节点相对最终根节点的倍数」,这正是后续查询能够直接相除的前提。
union:合并两棵树并推导权重
func (suf stringUnionFind) union(x, y string, v float64) {
suf.add(x)
suf.add(y)
px, py := suf.find(x), suf.find(y)
suf.parents[px] = py
// x / px = vals[x]
// x / y = v
// 由上面 2 个式子就可以得出 px = v * vals[y] / vals[x]
suf.vals[px] = v * suf.vals[y] / suf.vals[x]
}
union(x, y, v) 表示已知 x / y = v,将两棵树合并。px、py 分别为 x、y 当前的根,合并策略是让 px 指向 py,即 parents[px] = py。
关键在于新根 px 相对 py 的倍数 vals[px] 如何确定。源码注释给出了完整推导:
- 已知
x / px = vals[x](即x = px × vals[x]); - 已知
x / y = v(即x = y × v); - 而
y / py = vals[y],即y = py × vals[y]。
由 px × vals[x] = x = y × v = py × vals[y] × v,可解出:
px / py = v × vals[y] / vals[x]
所以 vals[px] = v * suf.vals[y] / suf.vals[x]。这里需要注意原文档描述的一个细节:当关系中的 y 已经位于并查集中(已有确定的相对根倍数)时,合并公式会自动把新关系统一到同一根上,无需手动翻转关系,例如 B/C = 3 与 C/B = 1/3 会被同一套公式自然兼容。
calcEquation:主流程
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
res, suf := make([]float64, len(queries)), stringUnionFind{parents: map[string]string{}, vals: map[string]float64{}}
for i := 0; i < len(values); i++ {
suf.union(equations[i][0], equations[i][1], values[i])
}
for i := 0; i < len(queries); i++ {
x, y := queries[i][0], queries[i][1]
if _, ok := suf.parents[x]; ok {
if _, ok := suf.parents[y]; ok {
if suf.find(x) == suf.find(y) {
res[i] = suf.vals[x] / suf.vals[y]
} else {
res[i] = -1
}
} else {
res[i] = -1
}
} else {
res[i] = -1
}
}
return res
}
主流程分为两个阶段:
阶段一(预处理):遍历所有 equations,用 union() 把每对变量合并进并查集,构建完整的倍数关系森林。
阶段二(查询):对每个查询 [x, y] 依次判定:
- 若
x或y从未在parents中出现过(不在任何方程式里),返回-1.0; - 若
find(x) != find(y),说明二者不在同一连通分量内,没有可推导的倍数关系,返回-1.0; - 若二者同根,说明
x、y都相对同一个根建立了倍数,直接返回suf.vals[x] / suf.vals[y]即可。这正是原文档所述「parents[A] / parents[C] = 2 / (1/3) = 6」在实现层面的落地——find()过程中vals已被压缩为相对根的倍数,相除即得答案。
以示例验证:已知 a/b=2.0、b/c=3.0,并查集最终形态中 a、b、c 同根,vals[a]=2.0(a 相对根 b),vals[b]=1.0,vals[c]=1/3。查询 a/c:vals[a]/vals[c] = 2.0 / (1/3) = 6.0;查询 b/a:vals[b]/vals[a] = 1.0/2.0 = 0.5;查询 a/a:2.0/2.0 = 1.0;而 a/e、x/x 因变量未注册或不同根,返回 -1.0,与预期输出完全一致。
测试用例验证
仓库为本题提供了两个精心设计的测试用例,见 399. Evaluate Division_test.go:
用例一(示例回归):
para399{[][]string{{"a", "b"}, {"b", "c"}}, []float64{2.0, 3.0}, [][]string{{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}}},
ans399{[]float64{6.0, 0.5, -1.0, 1.0, -1.0}},
覆盖了链式推导(a/c=6.0)、反向推导(b/a=0.5)、未注册变量(a/e、x/x 返回 -1)以及自比值(a/a=1.0)等全部场景。
用例二(不连通分量):
// two disconnected components: a/b and c/d, query across them hits the
// different-set branch (res = -1).
para399{[][]string{{"a", "b"}, {"c", "d"}}, []float64{2.0, 3.0}, [][]string{{"a", "d"}, {"a", "b"}}},
ans399{[]float64{-1.0, 2.0}},
这里构建了两棵互不相连的树(a/b 与 c/d),专门用于验证 find(x) != find(y) 时走「不同集合」分支返回 -1.0 的路径;同时 a/b 查询验证同集合分支输出 2.0。测试同时检查了结果长度与逐元素相等,可以完整覆盖 calcEquation 的每条分支。
复杂度与总结
- 时间复杂度:预处理阶段每条方程式执行一次带路径压缩的
union(),均摊近似O(α(N)),其中N为变量总数;查询阶段每个查询执行两次find(),同样近似O(α(N))。整体远优于每次查询都 DFS 一遍图的O(Q × (V + E))方案。 - 空间复杂度:
parents与vals两张哈希表各存储所有出现的变量,总空间O(N)。
本题是「带权重并查集」的经典应用:相比普通并查集只维护连通性,加权并查集在每个节点上额外维护「相对父节点(或根节点)的倍数」,从而把原本需要建图搜索的问题转化为常数级除法运算。本仓库的实现将字符串映射、路径压缩与权重累乘封装在 stringUnionFind 结构体内,结构清晰、边界分支完整,可作为处理同类「变量间比例关系」问题的可复用模板。若需复现运行,可在仓库根目录执行 go test ./leetcode/0399.Evaluate-Division/ -run Test_Problem399 -v 查看测试输出。