LeetCode 题解工作台
除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [A i , B i ] 和 values[i] 共同表示等式 A i / B i = values[i] 。每个 A i 或 B i 是一个表示单个变量的字符串。 另有一些以数…
7
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
class Solution: def calcEquation(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个变量对数组 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 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。
示例 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：
输入：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]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Dj由小写英文字母与数字组成
解题思路
方法一
class Solution:
def calcEquation(
self, equations: List[List[str]], values: List[float], queries: List[List[str]]
) -> List[float]:
def find(x):
if p[x] != x:
origin = p[x]
p[x] = find(p[x])
w[x] *= w[origin]
return p[x]
w = defaultdict(lambda: 1)
p = defaultdict()
for a, b in equations:
p[a], p[b] = a, b
for i, v in enumerate(values):
a, b = equations[i]
pa, pb = find(a), find(b)
if pa == pb:
continue
p[pa] = pb
w[pa] = w[b] * v / w[a]
return [
-1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d]
for c, d in queries
]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on DFS traversal for each query, potentially visiting all connected nodes, leading to O(Q * N) where Q is number of queries and N is number of variables. Space complexity includes graph storage and visited set, O(N + E) where E is number of edges. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you recognize that each variable can be represented as a node in a graph?
- question_mark
Could you use DFS to traverse paths and multiply values along edges?
- question_mark
How do you handle queries with variables not present in any equation?
常见陷阱
外企场景- error
Forgetting to add the inverse edge 1/value, which breaks paths in DFS.
- error
Not tracking visited nodes, causing infinite loops in cyclic graphs.
- error
Returning incorrect values for self-division or undefined variables.
进阶变体
外企场景- arrow_right_alt
Solve using BFS instead of DFS for each query to find shortest multiplicative path.
- arrow_right_alt
Use Union-Find with weighted edges to precompute connected component ratios.
- arrow_right_alt
Handle large datasets with memoization to cache intermediate division results.