LeetCode 399. 除法求值

字数 2786 2025-12-07 16:35:56

LeetCode 399. 除法求值

题目描述
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示 Ai / Bi = values[i]。每个 Ai 或 Bi 是一个表示单个变量（小写英文字母组成的字符串）的字符串。

另给你一些查询数组 queries，其中 queries[j] = [Cj, Dj] 表示第 j 个查询，请你计算 Cj / Dj 的结果，即根据已知条件，返回第 j 个查询的结果。

如果存在某个无法确定的答案，则用 -1.0 替代。如果问题中出现了矛盾（即根据已知条件可以推导出冲突的结果），则不需要处理矛盾，直接返回 -1.0 即可。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果（题目后半句是针对“没有矛盾”情况的假设，实际上代码要处理“无法确定”的情况）。

示例
输入：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 = (a / b) * (b / c) = 2.0 * 3.0 = 6.0
b / a = 1 / (a / b) = 1 / 2.0 = 0.5
a / e 无法确定（e 未出现过） → -1.0
a / a = 1.0
x / x （x 未出现过） → -1.0

解题过程循序渐进讲解

第一步：问题理解与建模
我们将每个变量（如 "a"、"b"）看作图中的一个节点。已知条件 a / b = 2.0 可以表示为两条有向边：

从 a 到 b 的边，权值为 2.0（表示 a = 2.0 * b）
从 b 到 a 的边，权值为 1/2.0 = 0.5（表示 b = 0.5 * a）

这样，整个已知条件 equations 和 values 就构成了一张带权有向图，并且对于每一对已知关系，我们都添加了两条方向相反的边，权重互为倒数。

查询 C / D 就相当于在图中找一条从节点 C 到节点 D 的路径，并将路径上的所有权重相乘，得到的结果就是 C / D 的值。

第二步：选择数据结构
我们需要快速查找某个变量是否存在，以及它有哪些邻居节点和对应的权重。

使用哈希表（字典）来存储图：graph[node] = List[(neighbor, weight)]
例如，已知 a / b = 2.0，那么在 graph["a"] 中添加 ("b", 2.0)，在 graph["b"] 中添加 ("a", 1/2.0)。

因为查询可能涉及没有直接边的两个变量，我们需要在图中搜索路径。这可以用 DFS（深度优先搜索） 或 BFS（广度优先搜索） 或 并查集（带权） 来实现。
这里先用DFS讲解，更直观。

第三步：图的构建
遍历 equations 和 values：

对于 equations[i] = [A, B]，值 = val
在 graph[A] 中添加 (B, val)
在 graph[B] 中添加 (A, 1.0 / val)

注意：如果 A 或 B 第一次出现，需要在 graph 中初始化一个空列表。

第四步：DFS 搜索路径计算比值
对于一个查询 (C, D)：

如果 C 或 D 不在图中，返回 -1.0（因为变量未出现过）
如果 C == D，返回 1.0
否则，从 C 开始 DFS 找 D，并记录路径乘积。

DFS 过程：

用 visited 集合记录当前路径已访问的节点，防止环路死循环。
从起点 cur 开始，遍历它的每个邻居 (next_node, weight)：
- 如果 next_node 是目标 D，则当前乘积 product * weight 就是答案。
- 否则，如果 next_node 未访问，递归进入 DFS(next_node, D, product * weight, visited)。
如果所有路径都走完没找到 D，返回 -1.0。

注意：因为图是无向的（但用有向边双向表示），DFS 不会漏掉路径，visited 保证不会重复访问。

第五步：整体流程

构建图 graph（字典映射节点->列表(邻居,权重)）
对每个查询 (C, D)：调用 dfs(C, D, 1.0, visited)
收集结果到答案列表
返回结果

第六步：示例推演
equations = [["a","b"],["b","c"]], values = [2.0, 3.0]
构建图：

a -> [("b", 2.0)]
b -> [("a", 0.5), ("c", 3.0)]
c -> [("b", 1/3.0)]

查询 a / c：
DFS(a, c)：
a 的邻居 b，权重 2.0，乘积=2.0，递归 b
b 的邻居 a（已访问跳过），邻居 c 权重 3.0，乘积=2.0*3.0=6.0，找到 c，返回 6.0

查询 b / a：
DFS(b, a)：
b 的邻居 a 权重 0.5，乘积=0.5，直接找到 a，返回 0.5

查询 a / e：
e 不在图中，返回 -1.0

查询 a / a：
相等，返回 1.0

查询 x / x：
x 不在图中，返回 -1.0

结果：[6.0, 0.5, -1.0, 1.0, -1.0]

第七步：复杂度与优化

构建图 O(E)，E 为 equations 数量
每个查询 DFS 最坏 O(V)（如果图是链状），V 是变量数量
总复杂度 O(E + Q*V)，Q 是查询数量

优化：可以用带权并查集，每个节点记录相对于父节点的比值，这样查询可以接近 O(1)，但实现稍复杂。不过 DFS 已经足够清晰，适合理解问题本质。

第八步：边界情况

变量不存在图中 → -1.0
查询的两个变量相同 → 1.0
图中有多个连通分量，不同分量之间无法计算 → -1.0
注意浮点精度，题目接受一定误差

这样，我们就用建图 + DFS 搜索路径乘积的方法解决了这个“除法求值”问题。

LeetCode 399. 除法求值题目描述给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量（小写英文字母组成的字符串）的字符串。另给你一些查询数组 queries ，其中 queries[j] = [Cj, Dj] 表示第 j 个查询，请你计算 Cj / Dj 的结果，即根据已知条件，返回第 j 个查询的结果。如果存在某个无法确定的答案，则用 -1.0 替代。如果问题中出现了矛盾（即根据已知条件可以推导出冲突的结果），则不需要处理矛盾，直接返回 -1.0 即可。注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果（题目后半句是针对“没有矛盾”情况的假设，实际上代码要处理“无法确定”的情况）。示例输入：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 = (a / b) * (b / c) = 2.0 * 3.0 = 6.0 b / a = 1 / (a / b) = 1 / 2.0 = 0.5 a / e 无法确定（e 未出现过） → -1.0 a / a = 1.0 x / x （x 未出现过） → -1.0 解题过程循序渐进讲解第一步：问题理解与建模我们将每个变量（如 "a"、"b"）看作图中的一个节点。已知条件 a / b = 2.0 可以表示为两条有向边：从 a 到 b 的边，权值为 2.0（表示 a = 2.0 * b）从 b 到 a 的边，权值为 1/2.0 = 0.5（表示 b = 0.5 * a）这样，整个已知条件 equations 和 values 就构成了一张带权有向图，并且对于每一对已知关系，我们都添加了两条方向相反的边，权重互为倒数。查询 C / D 就相当于在图中找一条从节点 C 到节点 D 的路径，并将路径上的所有权重相乘，得到的结果就是 C / D 的值。第二步：选择数据结构我们需要快速查找某个变量是否存在，以及它有哪些邻居节点和对应的权重。使用哈希表（字典）来存储图： graph[node] = List[(neighbor, weight)] 例如，已知 a / b = 2.0，那么在 graph["a"] 中添加 ("b", 2.0) ，在 graph["b"] 中添加 ("a", 1/2.0) 。因为查询可能涉及没有直接边的两个变量，我们需要在图中搜索路径。这可以用 DFS（深度优先搜索）或 BFS（广度优先搜索）或并查集（带权）来实现。这里先用 DFS 讲解，更直观。第三步：图的构建遍历 equations 和 values：对于 equations[ i] = [ A, B ]，值 = val 在 graph[ A ] 中添加 (B, val) 在 graph[ B ] 中添加 (A, 1.0 / val) 注意：如果 A 或 B 第一次出现，需要在 graph 中初始化一个空列表。第四步：DFS 搜索路径计算比值对于一个查询 (C, D)：如果 C 或 D 不在图中，返回 -1.0（因为变量未出现过）如果 C == D，返回 1.0 否则，从 C 开始 DFS 找 D，并记录路径乘积。 DFS 过程：用 visited 集合记录当前路径已访问的节点，防止环路死循环。从起点 cur 开始，遍历它的每个邻居 (next_ node, weight)：如果 next_ node 是目标 D，则当前乘积 product * weight 就是答案。否则，如果 next_ node 未访问，递归进入 DFS(next_ node, D, product * weight, visited)。如果所有路径都走完没找到 D，返回 -1.0。注意：因为图是无向的（但用有向边双向表示），DFS 不会漏掉路径，visited 保证不会重复访问。第五步：整体流程构建图 graph（字典映射节点->列表(邻居,权重)）对每个查询 (C, D)：调用 dfs(C, D, 1.0, visited) 收集结果到答案列表返回结果第六步：示例推演 equations = [ [ "a","b"],[ "b","c"]], values = [ 2.0, 3.0 ] 构建图： a -> [ ("b", 2.0) ] b -> [ ("a", 0.5), ("c", 3.0) ] c -> [ ("b", 1/3.0) ] 查询 a / c： DFS(a, c)： a 的邻居 b，权重 2.0，乘积=2.0，递归 b b 的邻居 a（已访问跳过），邻居 c 权重 3.0，乘积=2.0* 3.0=6.0，找到 c，返回 6.0 查询 b / a： DFS(b, a)： b 的邻居 a 权重 0.5，乘积=0.5，直接找到 a，返回 0.5 查询 a / e： e 不在图中，返回 -1.0 查询 a / a：相等，返回 1.0 查询 x / x： x 不在图中，返回 -1.0 结果：[ 6.0, 0.5, -1.0, 1.0, -1.0 ] 第七步：复杂度与优化构建图 O(E)，E 为 equations 数量每个查询 DFS 最坏 O(V)（如果图是链状），V 是变量数量总复杂度 O(E + Q* V)，Q 是查询数量优化：可以用带权并查集，每个节点记录相对于父节点的比值，这样查询可以接近 O(1)，但实现稍复杂。不过 DFS 已经足够清晰，适合理解问题本质。第八步：边界情况变量不存在图中 → -1.0 查询的两个变量相同 → 1.0 图中有多个连通分量，不同分量之间无法计算 → -1.0 注意浮点精度，题目接受一定误差这样，我们就用建图 + DFS 搜索路径乘积的方法解决了这个“除法求值”问题。