LeetCode 399 Evaluate Division 这道题说实话第一次做的时候我没反应过来它是图论题。题目给了一组形如 a / b 2.0 的等式和一组形如 a / c 等于多少 的查询看起来只是一堆四则运算直到动手建等式才意识到字符串变量、除法比例、路径方向这三点放在一起不就是带权图上的路径计算吗。这道题被收录在 LeetCode 热题 100 和很多大厂的面试题库里是因为它把「建模」这个抽象能力考得很直接你能不能在看到字符串和除法等式时马上把它翻译成一张图然后用图遍历或者并查集把结果算出来。适合刚刷完基础链表/数组题、想进阶图的读者也适合准备面试时用来串一遍图论细节的人。这篇文章我不会只贴一份代码而是把 DFS、Floyd、并查集三种解法全部拆开连同我踩过的坑一起写清楚争取看完你能自己复现并且举一反三。1. 题目拆解除法等式背后藏着一张带权图1.1 先看清楚题目的输入输出原题描述不复杂。它会给一个等式列表equations比如[[a,b],[b,c]]对应一个权重列表values比如[2.0, 3.0]意思就是a / b 2.0b / c 3.0。然后给一批queries比如[[a,c],[b,a],[a,x]]要求返回每个查询的结果无法计算就返回-1.0。我第一次看到这个输入输出时脑子里第一反应是解方程把a当成未知数b当成未知数联立等式硬解。这个思路在小数据里勉强能跑但一旦碰到查询里的变量在等式里完全没出现过或者两个变量之间根本没有等式路径可以串联就会卡住。本质原因是题目给的并不是一组完整的代数方程组而是一个「关系网」变量之间有等式关系就连一条边没有就直接孤立。1.2 为什么能联想到「图」我们把每个变量名字符串看成一个节点把a / b 2.0看成一条从a指向b的有向边边的权重是2.0。与此同时a / b 2.0也意味着b / a 0.5所以还需要补一条反向边权重是1 / 2.0 0.5。这样一来整个问题就变成了给定一张带权有向图任意查询两个节点A和B求从A出发到B的一条路径把路径上所有边的权重依次乘起来就是A / B的结果。为什么是乘法因为路径上的每一条边都代表一次除法关系a - b是a / b 2.0b - c是b / c 3.0那么a / c就等价于(a / b) * (b / c) 2.0 * 3.0 6.0。中间经过多少个节点就乘多少条边的权重如果中间断开了说明两个变量之间没有已知关系返回-1.0。这个建图过程是整个题目的核心也是一个很好的面试考察点。面试官不会直接说请用图做而是看你能否自己把字符串和除法等式映射到图模型上。一旦这一步想通后面 DFS、BFS、Floyd、并查集这些解法都是水到渠成的事。1.3 建图时的两个关键细节第一个细节是必须同时建正向边和反向边。只建a - b而不建b - a查询b / a的时候就会直接判不可达结果就会错。反向边的权重一定是正向边权重的倒数这是除法本身的特性不需要额外记忆。第二个细节是变量可能很多但节点总数有限。题目约束equations长度最多 20每条等式最多引入 2 个新变量所以整个图的节点数最多 40 个。这个规模非常小意味着 O(n^3) 的 Floyd 算法也完全能扛得住。很多人在做这道题时纠结复杂度其实是没注意到这个约束条件。40 个节点的三重循环只有 64000 次运算在一台普通电脑上是毫秒级的工作量。1.4 这道题到底想考什么我后来在面试复盘里总结LeetCode 399 主要考三件事。第一件是把非图论语言翻译成图这是建模能力第二件是知道不同图算法的适用场景这是算法储备第三件是处理边界条件比如变量没出现过、两个节点相等、路径不存在这是工程严谨性。这三件事恰好对应了面试中从思路到代码再到测试的完整流程。所以它被放在热门 100 题里是有道理的。它不像纯模板题那样背个 BFS 模板就能过也不像数学题那样需要临时推导公式。它更像一个中转站把熟悉的图算法和陌生的实际问题连接起来。把这题吃透之后遇到汇率换算、单位换算、配料比例、依赖关系传递这类场景你都会条件反射地往图上想。2. 拿到题目先选方案DFS、Floyd、并查集怎么挑2.1 三种解法各自的核心思想我第一次 AC 用的是 DFS后来看题解发现还有 Floyd 和并查集的做法而且一个比一个优雅。这三种解法不是互相替代的关系而是代表了三种不同的算法思维。DFS/BFS 是每次查询都实时搜索从起点出发沿着边往下走边走边把权重乘起来走到终点就返回结果。优点是好想好写缺点是每次查询都要重新遍历一次图如果查询特别多会很浪费。Floyd 是预处理一次查询 O(1)先用三重循环把任意两个节点之间的除法结果都算出来存在二维表里之后每个查询直接查表。这在查询次数很多的情况下非常有优势尤其是图上所有节点对都需要计算时。带权并查集是用集合维护比例关系把所有能互相推导的变量放进同一个集合集合内每个节点都记录它到根节点的比例。查询时只要两个变量在同一个集合里就能通过它们各自到根的比例得到答案。三种思路的对比我整理成了表格解法核心思想单次查询复杂度预处理复杂度代码复杂度DFS/BFS实时搜索路径路径权重连乘O(V E)O(V E) 建图低Floyd预处理所有点对的最短比值O(1)O(V^3)中带权并查集节点到根的比值 路径压缩近似 O(alpha(N))O(V * alpha(N))中高2.2 从题目规模看怎么选LeetCode 399 的变量数最多 40查询最多 20所以三种解法在耗时上没有任何差别都能在几毫秒内跑完。如果是面试场景我更建议先用 DFS 讲清楚思路再顺着面试官的问题往并查集方向深入。但如果把题目变形一下比如查询次数从 20 变成 10 万次那么 DFS 每次查询都要遍历图最坏情况下复杂度会变成 O(Q * (V E))也就是 10 万 * 40虽然还是能跑但在更稀疏更大规模的图上就会吃亏。这种情况下 Floyd 的 O(1) 查询和并查集的近 O(1) 查询就更有竞争力。所以做题不能只看能不能过还要看数据范围变化后你的方案是否依然成立。2.3 我推荐的刷题顺序我的建议是新手先老老实实把 DFS 写出来不要一上来就追求并查集因为 DFS 能帮你把图模型建立 路径权重相乘这个核心逻辑打通。然后第二遍再用带权并查集重写这时候你会体会到并查集在代码结构上的简洁和效率上的优势。Floyd 可以作为补充理解尤其是当你遇到多查询 全点对场景时它会是一个非常好的工具。这三种解法其实也对应了三种思考层次。DFS 是在图上直接模拟除法关系属于直观层Floyd 利用的是图上的传递闭包思想把除法结果预计算成一张表属于规划层并查集则是把每个连通分量当成一个有根集合用比例关系统一衡量属于抽象层。逐个吃透这三种思路比单纯记住一份代码有价值得多。3. 解法一DFS 搜索3.1 建图用 defaultdict(dict)DFS 的第一步是建图。对于每条等式(a, b)我习惯用defaultdict(dict)来存邻接表因为这样可以用graph[a][b] val的方式直接赋值不用担心graph[a]还不存在。from collections import defaultdict class Solution: def calcEquation(self, equations, values, queries): graph defaultdict(dict) for (a, b), value in zip(equations, values): graph[a][b] value graph[b][a] 1.0 / value这里有个小细节graph[a][b] value和graph[b][a] 1.0 / value都要写不能偷懒。而且反向边的权重一定是正数因为题目保证values是正浮点数所以1.0 / value永远合法不会出现除零错误。3.2 递归搜索路径乘法加哨兵值DFS 的核心是递归函数入参是当前节点、目标节点和一个visited集合。每次进入一个节点先把当前节点标记为已访问然后遍历它的所有邻居如果邻居就是目标直接返回边权否则递归去邻居的邻居递归结果乘上当前边权就是整条路径的乘积。这里需要一个哨兵值来表示路径不存在。我用-1.0因为题目保证所有计算结果都是正数所以-1.0永远不会和真实结果冲突。递归返回后如果子调用返回-1.0就说明这条路径走不通不能再乘而是继续尝试其他邻居。还需要注意一个边界条件如果起点等于终点且这个变量确实出现过那么结果应该是1.0因为任何变量除以自身都等于 1。但如果这个变量在图中从未出现过即使a a也应该返回-1.0。所以代码里要把是否在图中的判断放在是否相等之前不然会出现把-1.0错写成1.0的 bug。3.3 完整代码把上面的逻辑整合起来就是一份可以直接提交的 DFS 解法from collections import defaultdict class Solution: def calcEquation(self, equations, values, queries): graph defaultdict(dict) for (a, b), value in zip(equations, values): graph[a][b] value graph[b][a] 1.0 / value def dfs(src, dst, visited): if src not in graph or dst not in graph: return -1.0 if src dst: return 1.0 visited.add(src) for neighbor, weight in graph[src].items(): if neighbor in visited: continue sub_result dfs(neighbor, dst, visited) if sub_result ! -1.0: return weight * sub_result return -1.0 result [] for src, dst in queries: result.append(dfs(src, dst, set())) return result这段代码我之所以先判断dst not in graph是因为即使起点能到达终点终点不存在时也不可能找到结果。两个判断都放在开头可以避免进入递归后做大量无效搜索。3.4 复杂度分析与适用场景DFS 的单次查询最坏复杂度是 O(V E)V是节点数E是边数。在本题规模下 V 最多 40每次查询最多遍历几十个节点性能完全没问题。空间上因为递归调用栈和visited集合分别是 O(V) 和 O(E)也都很小。这个解法最大的优点是直观。面试时你先说出把除法等式建模成带权有向图然后每次查询 DFS 找路径乘权重面试官立刻就知道你理解了题目的本质。缺点是如果查询次数很多、图很大每次 DFS 都重复搜索会显得冗余。好在本题查询数量也不多所以 DFS 是我个人最推荐的第一版写法。4. 解法二Floyd 预计算4.1 多查询场景下的预处理思路如果题目改成有 10 万条查询每次都做 DFS 就会显得笨重。这个时候我们可以在查询前把图上所有节点对的除法结果都算出来之后每次查询直接查表这就是 Floyd 算法的基本思想。Floyd 常用于求任意两点间的最短路径它通过枚举中间节点k不断尝试用i - k和k - j来更新i - j的路径。在这道题里路径距离换成了路径乘积如果dist[i][k]和dist[k][j]都存在那么dist[i][j]就可以更新为dist[i][k] * dist[k][j]。这个更新公式和除法关系完全吻合。4.2 矩阵初始化和三重循环第一步先给每个变量分配一个唯一的整数索引方便用二维数组存储结果。索引表可以用dict维护遍历equations时遇到新变量就分配一个递增的编号。然后初始化dist矩阵。矩阵边长是变量总数n初始值全部设为0.0其中0.0表示不可达。对角线dist[i][i]初始化为1.0因为任何变量除以自身都等于 1。接着根据每条等式设置矩阵中的值dist[ia][ib] valuedist[ib][ia] 1.0 / value。之后就是标准的 Floyd 三重循环。注意更新条件必须是dist[i][k]和dist[k][j]都不为 0否则说明中间路径不通。满足条件时就更新为dist[i][k] * dist[k][j]。4.3 完整代码用二维数组实现的 Floyd 版本如下class Solution: def calcEquation(self, equations, values, queries): idx {} for a, b in equations: if a not in idx: idx[a] len(idx) if b not in idx: idx[b] len(idx) n len(idx) dist [[0.0] * n for _ in range(n)] for i in range(n): dist[i][i] 1.0 for (a, b), value in zip(equations, values): i, j idx[a], idx[b] dist[i][j] value dist[j][i] 1.0 / value for k in range(n): for i in range(n): for j in range(n): if dist[i][k] 0.0 and dist[k][j] 0.0: dist[i][j] dist[i][k] * dist[k][j] result [] for a, b in queries: if a not in idx or b not in idx: result.append(-1.0) else: val dist[idx[a]][idx[b]] result.append(val if val 0.0 else -1.0) return result这里用dist[i][k] 0.0来判断可达性是因为除法等式的计算结果始终是正数0.0只可能代表不可达不会和其他结果冲突。这是一个在浮点数场景下比较安全的做法。4.4 Floyd 解法的边界问题Floyd 有个容易被忽略的点如果两个变量之间原本已经存在一条路径后面又通过中间节点算出了一条更长的乘积路径那么我们需要不需要保留原来的值在这道题里由于每个除法结果都是确定的不存在多路径取最小或最大的问题所有路径的乘积最终应该一致所以可以直接覆盖也可以保留原有值。我在上面代码里直接用dist[i][k] * dist[k][j]更新只要条件满足就覆盖写起来更简洁。这个解法最适合的其实是变量很少、查询很多的变种场景。只要节点数不超过几百O(n^3) 的预处理完全可接受之后每一次查询都是 O(1)性能非常好看。面试时如果你抛出这个优化思路通常能加不少分。5. 解法三带权并查集最优解5.1 和普通并查集的区别在哪普通并查集只维护节点之间的连通关系也就是parent数组。而这道题不仅要知道a和b在不在同一个集合里还要知道a / b的值所以必须额外维护一个比值信息带权并查集就是干这个的。简单来说并查集里每个节点x都有一个parent[x]表示它的父节点。我们约在这基础上再维护一个weight[x]表示x到parent[x]的比值也就是x / parent[x]。这样当我们把集合不断向上合并之后任意节点x到根节点root的比值就可以通过路径上所有weight连乘得到。查询a / b时只要a和b在同一个集合里就用它们分别到根的比值做除法a / b (a / root) / (b / root) weight_a_to_root / weight_b_to_root。5.2 weight 数组的含义我先给weight一个非常明确的定义避免后面推导搞混weight[x]表示x除以parent[x]的结果即x / parent[x] weight[x]。初始时每个节点都是自己的父节点所以weight[x] 1.0。当我们把a和b合并时已知a / b value我们要设计weight的更新使得整棵树的比值关系始终保持正确。合并的过程其实是在构造一个新的父子关系把a的根root_a挂到b的根root_b下面然后计算root_a / root_b应该等于多少。5.3 find 的路径压缩该如何更新权重接下来是find函数。find(x)的目的是找到x的根节点同时把x的父节点直接指向根这就是路径压缩。但在压缩之前必须要先更新weight否则一旦parent[x]被直接改成根原来的父节点信息就丢了weight[x]就用不上了。正确的更新顺序是先递归调用find(parent[x])让父节点先完成路径压缩和权重更新此时weight[parent[x]]已经表示parent[x]到新根的比值。然后我们再把x的父节点指向新根并把weight[x]更新为weight[x] * weight[parent[x]]。这个乘法对应的是两级连乘x / root (x / old_parent) * (old_parent / root)。我在实际写代码时踩过一个坑如果先更新parent[x]再更新weight[x]那么weight[parent[x]]就会引用到新父节点的权重而不是旧父节点的权重导致计算结果完全错误。所以顺序一定不能反这是带权并查集最容易写错的地方。5.4 union 的权重公式推导union(a, b, value)表示已知a / b value要把两个集合合并。假设a所在集合的根是root_ab所在集合的根是root_b。我们要让root_a并入root_b也就是把parent[root_a]设为root_b。关键问题是weight[root_a]应该设成多少根据weight的定义a / root_a weight[a]所以a weight[a] * root_a。同理b weight[b] * root_b。已知a / b value代入得到(weight[a] * root_a) / (weight[b] * root_b) value移项整理root_a / root_b value * weight[b] / weight[a]而weight[root_a]的定义就是root_a / parent[root_a] root_a / root_b所以self.parent[root_a] root_b self.weight[root_a] value * self.weight[b] / self.weight[a]这里要稍微留意一下weight[a]和weight[b]必须是在调用find之后的值也就是它们各自到根的比值而不是原始状态下到父节点的比值。所以在union里我会先root_a self.find(a)、root_b self.find(b)确保weight[a]、weight[b]已经是最新结果。5.5 完整代码与正确性验证带权并查集的完整实现如下class UnionFind: def __init__(self): self.parent {} self.weight {} def find(self, x): if x not in self.parent: self.parent[x] x self.weight[x] 1.0 return x if self.parent[x] ! x: old_parent self.parent[x] new_parent self.find(old_parent) self.weight[x] self.weight[x] * self.weight[old_parent] self.parent[x] new_parent return self.parent[x] def union(self, a, b, value): root_a self.find(a) root_b self.find(b) if root_a root_b: return self.parent[root_a] root_b self.weight[root_a] value * self.weight[b] / self.weight[a] def compare(self, a, b): if a not in self.parent or b not in self.parent: return -1.0 root_a self.find(a) root_b self.find(b) if root_a ! root_b: return -1.0 return self.weight[a] / self.weight[b] class Solution: def calcEquation(self, equations, values, queries): uf UnionFind() for (a, b), value in zip(equations, values): uf.union(a, b, value) return [uf.compare(a, b) for a, b in queries]用题目样例验证一下。已知a / b 2.0b / c 3.0。执行union(a, b, 2.0)后a的根变成bweight[a] 2.0。执行union(b, c, 3.0)后b的根变成cweight[b] 3.0同时a的父节点还是b但在查询时会触发find(a)的路径压缩weight[a]会被更新成weight[a] * weight[b] 2.0 * 3.0 6.0。此时查询a / ccompare(a, c)返回weight[a] / weight[c] 6.0 / 1.0 6.0和 DFS 的结果一致。这个验证过程也解释了为什么find必须递归更新权重。6. 常见问题与排查技巧实录6.1 自环查询变量出现过和没出现过是两回事查询里经常出现[a,a]这种形式。很多人第一反应就是直接返回1.0但这个回答只在a出现过的情况下才正确。如果a从未在equations里出现过它没有任何已知的除法关系你根本不知道a是什么当然也不知道a / a是多少按照题意应该返回-1.0。DFS 解法里把src not in graph or dst not in graph放在最前面就是为了先处理这个边界。6.2 浮点数误差跟 -1.0 的坑题目给出的除法结果都是正数所以我放心用-1.0作为不可达哨兵。但要注意如果题目改动为可能出现负数结果这种写法就会出问题。浮点数计算还有一个固有误差问题比如连续乘了很多条边之后结果可能是1.0000000000000002而不是1.0。在做严格相等判断时不要用要么用abs(x - expected) 1e-9这种误差范围判断要么干脆把哨兵值换成None或者float(inf)从根源上避开冲突。6.3 递归方向别写反DFS 里return weight * sub_result的写法权重在前还是后其实无所谓因为乘法满足交换律。但在并查集的union里value * self.weight[b] / self.weight[a]的顺序就非常关键了。只要把分子分母写反算出来的就不是root_a / root_b而是它的倒数后面的所有查询结果都会错。我在代码里推导过一遍root_a / root_b value * weight[b] / weight[a]这个公式可以直接当结论记前提是weight[x]定义为x / parent[x]。6.4 未出现变量统一返回 -1.0不管用哪种解法都要在最后查询时先判断变量是否出现过。DFS 通过判断节点是否在图里解决Floyd 通过判断变量是否在索引表里解决并查集通过判断变量是否在parent里解决。这个判断不能省否则会抛出KeyError或者误用不存在的节点导致结果错误。我建议把这种数据完整性问题的检查统一放在查询入口不要散落在递归内部逻辑会更清晰。6.5 并查集 if/else 写错导致查不出根在find的路径压缩里如果写成if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[x] * self.weight[self.parent[x]]看起来只差一行顺序实际是错的。因为self.parent[x]被更新成新根之后self.weight[self.parent[x]]取到的是新根的权重而新根到它自己的比值总是1.0导致self.weight[x]没有真正乘上旧父节点到新根的那一段。正确写法必须先用一个变量把旧父节点保存下来比如我代码里的old_parent再更新self.weight[x]最后更新self.parent[x]。这个顺序问题我至少踩过两次写出来提醒一下。7. 实战心得与同一套模型还能解决什么7.1 从这道题总结出的刷题通法LeetCode 399 给我最大的收获不是背会了某一种解法而是再次确认了建模优先的刷题思路。拿到一道题先不要急着套模板而是问自己三个问题数据里有哪些实体实体之间有什么关系查询到底在问什么在这道题里实体是字符串变量关系是除法等式查询是求变量之间的除法比值。想清楚这三点图模型就自然浮出水面后面的算法选择反而简单了。另一个心得是面试中如果只写出 DFS可以主动补一句这题数据量小DFS 够用如果查询量很大可以用 Floyd 预计算或者带权并查集优化。这句话体现的不只是你会写代码而是你对复杂度和场景有意识。我见过不少候选人代码 AC 了但问他为什么不用并查集答不上来这就很可惜。算法题不是炫技是为了解决实际问题。7.2 现实场景汇率、单位换算、量纲这个题模型的应用场景其实很广。比如汇率换算给定一组货币对之间的汇率再给出大量货币兑换请求本质上就是从一个货币出发沿着已知汇率边换算到目标货币。再比如厨房里的单位换算已知1 cup 16 tablespoons1 tablespoon 3 teaspoons求cup / teaspoon是多少就是把单位当成节点换算比例当成边权。还有物理里的单位量纲、工程里的配料比例都是同一个带权图模型。面试时如果把这道题联系到实际业务会显得很有工程判断力。7.3 同类扩展题如果你刷完这道题还想巩固一下我推荐几个衍生题LeetCode 684 Redundant Connection 可以用来练并查集的连通性判断LeetCode 721 Accounts Merge 是并查集和字符串处理的组合LeetCode 547 Number of Provinces 练的是纯连通分量的计算。另外经典的带权并查集问题比如食物链、带权区间和问题思路也是从这题延伸出去的。把 399 吃透后续遇到这些题会轻松很多。最后分享一个我自己的小习惯做这类比例传递的题我会先在草稿纸上画一棵树把节点和边的权重标出来然后随便选一个根把每个节点到根的比值写在节点旁边。这么做之后并查集的weight更新逻辑立马变得很直观比硬背公式靠谱多了。如果你在代码里也经常搞混find的权重更新顺序我建议你也试试这个方法。