LeetCode-Go 题解精讲:0399 Evaluate Division 加权并查集求除法表达式

原创2026-09-09 21:26:171,981 阅读
文章标签:示例工程教程教育静态站点

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 做法思路直观:

  1. 建图:将每个变量视为节点,每条 equations[i] 视为一条有向边。边 A -> B 权值为 values[i],同时补一条反向边 B -> A,权值为 1 / values[i](因为 B / A = 1 / k)。
  2. 查询:对每个 query = [X, Y],从节点 X 出发 DFS 搜索节点 Y。搜索过程中把经过的边权值累乘,到达 Y 时累乘结果即为答案。
  3. 无解判定:若搜索结束仍无法到达 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) 完成两件事:

  1. 查找根节点:递归向上,直到找到 parents[x] == x 的根;
  2. 路径压缩:回溯过程中把 x 直接指向根 pp,摊平树结构;
  3. 权重修正:关键在 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] 依次判定:

  1. 若 x 或 y 从未在 parents 中出现过(不在任何方程式里),返回 -1.0;
  2. 若 find(x) != find(y),说明二者不在同一连通分量内,没有可推导的倍数关系,返回 -1.0;
  3. 若二者同根,说明 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 查看测试输出。

登录后查看全文
LeetCode-Go