399. 除法求值

399. 除法求值

题目链接（中等）

题目描述

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [A_i, B_i] 和 values[i] 共同表示等式 A_i / B_i = values[i]。每个 A_i 或 B_i 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [C_j, D_j] 表示第 j 个问题，请你根据已知条件找出 C_j / D_j = ? 的结果作为答案。

返回 所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

数据范围：

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= A_i.length, B_i.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= C_j.length, D_j.length <= 5
  • A_i, B_i, C_j, D_j 由小写英文字母与数字组成

示例

示例 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]

核心思路

将变量视为图的节点，等式 A / B = k 视为一条从 A 到 B 权值为 k 的有向边，同时反向边 B → A 权值为 1/k。

于是问题转化为：在图中求任意两点之间的路径权值乘积。

  • 若两点连通，则路径乘积即为答案；
  • 若两点不连通或变量未出现，则答案为 -1.0。

四种解法：

  1. DFS：对每个查询独立做一次深度优先搜索，实时计算路径乘积；
  2. BFS：对每个查询独立做一次广度优先搜索，实时计算路径乘积；
  3. Floyd：预处理所有点对之间的比值，查询时直接查表；
  4. 带权并查集：维护每个节点到根的比值，查询时通过根节点计算。

方法一：DFS（深度优先搜索）

思路及解法

核心：把除法关系转成带权有向图，查询即寻找路径并累乘边权。

  1. 构建带权图：graph[a] 存储所有从 a 出发的 (邻居, 权重) 对；
  2. 对每个查询 [c, d]：
    • 若 c 或 d 不在图中，返回 -1.0；
    • 若 c == d，返回 1.0；
    • 否则从 c 出发做 DFS，递归查找通往 d 的路径，沿途累乘边权；
    • 若找到，返回累积乘积；否则返回 -1.0。

DFS 递归的设计：

def dfs(start, end, visited):
    if start == end:
        return 1.0
    visited.add(start)
    for neighbor, weight in graph[start]:
        if neighbor not in visited:
            res = dfs(neighbor, end, visited)
            if res is not None:
                return weight * res
    return None
  • 找到终点时返回 1.0（作为乘积的单位元）；
  • 递归返回后，将当前边权 weight 乘上去，逐层累积；
  • 用 visited 防止走回头路。

为什么用 None 表示未找到：因为合法的答案可能是 0.0（虽然本题除数不为 0，但用 None 更安全，与 -1.0 区分）。

示例验证：equations = [["a","b"],["b","c"]], values = [2.0,3.0]，图结构：

a → b (2.0)
b → a (0.5)
b → c (3.0)
c → b (1/3)

查询 a / c：

  • 从 a 出发 → b，累积 2.0；
  • 从 b 出发 → c，累积 2.0 × 3.0 = 6.0；
  • c == c，返回 6.0。✓

代码

from collections import defaultdict

class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        # 1. 构建带权图
        graph = defaultdict(list)
        for (a, b), v in zip(equations, values):
            graph[a].append((b, v))
            graph[b].append((a, 1.0 / v))

        # 2. DFS 查找从 start 到 end 的路径，返回累积乘积
        def dfs(start, end, visited):
            if start == end:
                return 1.0
            visited.add(start)
            for neighbor, weight in graph[start]:
                if neighbor not in visited:
                    res = dfs(neighbor, end, visited)
                    n
                        return weight * res
            return None

        # 3. 处理每个查询
        ans = []
        for c, d in queries:
            if c not in graph or d not in graph:
                ans.append(-1.0)
            elif c == d:
                ans.append(1.0)
            else:
                res = dfs(c, d, set())
                ans.append(res if res is not None else -1.0)

        return ans

复杂度分析

  • 时间复杂度：构建图 O(E)O(E)，其中 EE 是等式数量。每个查询做一次 DFS，最坏 O(V+E)O(V + E)，总查询数 QQ，总时间 O(Q⋅(V+E))O(Q \cdot (V + E))。题目中 E≤20E \le 20，Q≤20Q \le 20，非常小。
  • 空间复杂度：O(V+E)O(V + E)，存储图。DFS 递归栈深度最多 O(V)O(V)。

方法二：BFS（广度优先搜索）

思路及解法

与方法一思路完全相同，只是把 DFS 换成 BFS。

  1. 遍历 equations，用哈希表将每个变量名映射为整数编号；
  2. 构建邻接表：对于每个等式 A / B = v，添加边 A → B 权重 v，B → A 权重 1/v；
  3. 对于每个查询 [C, D]：
    • 若 C 或 D 未在映射中，返回 -1.0；
    • 若 C == D，返回 1.0；
    • 否则从 C 出发做 BFS，维护从 C 到各点的累积比值，直到找到 D 或队列为空；
    • 返回找到的比值或 -1.0。

代码

from collections import deque

class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        # 1. 变量名映射为整数
        var_id = {}
        nvars = 0
        for a, b in equations:
            if a not in var_id:
                var_id[a] = nvars
                nvars += 1
            if b not in var_id:
                var_id[b] = nvars
                nvars += 1

        # 2. 构建邻接表
        edges = [[] for _ in range(nvars)]
        for (a, b), v in zip(equations, values):
            ia, ib = var_id[a], var_id[b]
            edges[ia].append((ib, v))
            edges[ib].append((ia, 1.0 / v))

        # 3. 处理查询
        result = []
        for c, d in queries:
            if c not in var_id or d not in var_id:
                result.append(-1.0)
                continue
            ic, id_ = var_id[c], var_id[d]
            if ic == id_:
                result.append(1.0)
                continue

            # BFS
            ratios = [-1.0] * nvars
            ratios[ic] = 1.0
            q = deque([ic])
            while q and ratios[id_] < 0:
                x = q.popleft()
                for y, val in edges[x]:
                    if ratios[y] < 0:
                        ratios[y] = ratios[x] * val
                        q.append(y)
            result.append(ratios[id_])

        return result

复杂度分析

  • 时间复杂度：O(ML+Q⋅(L+M))O(M L + Q \cdot (L + M))，其中 MM 为边数，QQ 为查询数，LL 为字符串平均长度。构建图 O(ML)O(ML)，每次 BFS 最多遍历 O(M)O(M) 条边，共 QQ 次。
  • 空间复杂度：O(NL+M)O(N L + M)，NN 为变量数，MM 为边数。

方法三：Floyd 算法

思路及解法

预先计算任意两点之间的比值。

  1. 同样建立变量到整数的映射；
  2. 初始化二维矩阵 graph，大小为 nvars × nvars，初始值为 -1.0；
  3. 对于每个等式 A / B = v，设置 graph[ia][ib] = v，graph[ib][ia] = 1/v；对角线 graph[i][i] = 1.0；
  4. 三重循环 Floyd：若 graph[i][k] > 0 且 graph[k][j] > 0，则 graph[i][j] = graph[i][k] * graph[k][j]；
  5. 查询时直接查表，若值 > 0 则返回，否则 -1.0。

代码

class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        # 变量映射
        var_id = {}
        nvars = 0
        for a, b in equations:
            if a not in var_id:
                var_id[a] = nvars
                nvars += 1
            if b not in var_id:
                var_id[b] = nvars
                nvars += 1

        # 初始化矩阵
        graph = [[-1.0] * nvars for _ in range(nvars)]
        for i in range(nvars):
            graph[i][i] = 1.0

        for (a, b), v in zip(equations, values):
            ia, ib = var_id[a], var_id[b]
            graph[ia][ib] = v
            graph[ib][ia] = 1.0 / v

        # Floyd 预处理
        for k in range(nvars):
            for i in range(nvars):
                for j in range(nvars):
                    if graph[i][k] > 0 and graph[k][j] > 0:
                        graph[i][j] = graph[i][k] * graph[k][j]

        # 查询
        result = []
        for c, d in queries:
            if c not in var_id or d not in var_id:
                result.append(-1.0)
            else:
                val = graph[var_id[c]][var_id[d]]
                result.append(val if val > 0 else -1.0)
        return result

复杂度分析

  • 时间复杂度：O(ML+N3+QL)O(M L + N^3 + Q L)，构建图 O(ML)O(ML)，Floyd O(N3)O(N^3)，查询 O(QL)O(QL)。
  • 空间复杂度：O(NL+N2)O(N L + N^2)。

方法四：带权并查集

思路及解法

每个节点维护两个信息：

  • parent[x]：父节点；
  • weight[x]：节点 x 的值与父节点值的比值，即 v[x] / v[parent[x]]。

查找（find）：路径压缩时更新 weight，使其始终表示 x 到根的比值。

合并（union）：对于等式 A / B = k，找到 A 和 B 的根 ra、rb，将 ra 挂到 rb 下，并更新 weight[ra]。

查询：若两个变量根相同，则 A / B = weight[A] / weight[B]（因为 weight 是到根的比值）。

代码

class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        # 变量映射
        var_id = {}
        nvars = 0
        for a, b in equations:
            if a not in var_id:
                var_id[a] = nvars
                nvars += 1
            if b not in var_id:
                var_id[b] = nvars
                nvars += 1

        parent = list(range(nvars))
        weight = [1.0] * nvars   # weight[x] = v[x] / v[parent[x]]

        def find(x: int) -> int:
            if parent[x] != x:
                root = find(parent[x])
                weight[x] *= weight[parent[x]]
                parent[x] = root
            return parent[x]

        def union(x: int, y: int, val: float) -> None:
            # val = v[x] / v[y]
            rx, ry = find(x), find(y)
            if rx == ry:
                return
            parent[rx] = ry
            # 需要满足 v[x] / v[y] = val
            # v[x] = weight[x] * v[rx]
            # v[y] = weight[y] * v[ry]
            # 所以 weight[rx] = v[rx] / v[ry] = (v[x]/weight[x]) / (v[y]/weight[y])
            #                  = (v[x]/v[y]) * (weight[y]/weight[x])
            weight[rx] = val * weight[y] / weight[x]

        # 构建并查集
        for (a, b), v in zip(equations, values):
            union(var_id[a], var_id[b], v)

        # 查询
        result = []
        for c, d in queries:
            if c not in var_id or d not in var_id:
                result.append(-1.0)
            else:
                ic, id_ = var_id[c], var_id[d]
                if find(ic) == find(id_):
                    result.append(weight[ic] / weight[id_])
                else:
                    result.append(-1.0)
        return result

复杂度分析

  • 时间复杂度：O(ML+N+Mlog⁡N+Q(L+log⁡N))O(M L + N + M \log N + Q (L + \log N))，并查集操作近似常数。
  • 空间复杂度：O(NL)O(N L)。

四种方法对比

方法 时间 空间 特点
DFS O(Q(V+E))O(Q(V+E)) O(V+E)O(V+E) 最直观，代码最短，本题首选
BFS O(Q(V+E))O(Q(V+E)) O(V+E)O(V+E) 与 DFS 等价，换成队列
Floyd O(N3+QL)O(N^3 + QL) O(N2)O(N^2) 预处理所有点对，适合多次查询
带权并查集 近 O(ML+N+QL)O(M L + N + QL) O(NL)O(N L) 效率最高，但实现稍复杂

推荐：

  • 面试：首选 DFS，代码最短、思路最直观，本题数据规模小完全够用；
  • 查询很多：用 Floyd 或 带权并查集；
  • 追求最优：带权并查集，时间空间都最优。

关键细节

1. 图建模

等式 A / B = k 对应两条有向边：

  • A → B 权重 k；
  • B → A 权重 1/k。

路径上权值相乘，即可得到两端变量的比值。

2. DFS 中为什么用 None 而不是 -1.0 表示未找到

因为答案可能是合法的 0.0（虽然本题除数不为 0，但用 None 更安全），避免和「找不到」混淆。

3. BFS 中的 ratios 数组

ratios[i] 表示从起点 C 到节点 i 的累积比值。初始 ratios[C] = 1.0，未访问为 -1.0。BFS 扩展时 ratios[y] = ratios[x] * val。

4. Floyd 的对角线

graph[i][i] = 1.0 表示自己除以自己等于 1。Floyd 更新时只考虑 > 0 的边，避免无效的 -1.0 参与乘法。

5. 带权并查集的 weight 含义

weight[x] = v[x] / v[parent[x]]。路径压缩时，weight[x] *= weight[parent[x]]，使其指向根。合并时推导：

设 x 的根为 rx，y 的根为 ry，已知 v[x] / v[y] = val。
v[x] = weight[x] * v[rx]，v[y] = weight[y] * v[ry]。
所以 weight[rx] = v[rx] / v[ry] = val * weight[y] / weight[x]。

6. 未定义变量的处理

如果查询中的变量从未在 equations 中出现，直接返回 -1.0。

总结

  • 本质：带权图上的路径乘积问题；
  • DFS：每次查询独立搜索，代码最短，本题首选；
  • BFS：与 DFS 等价，用队列实现；
  • Floyd：预处理所有点对，适合多次查询；
  • 带权并查集：利用比值关系维护连通分量，效率最高；
  • 通用套路：变量比值 → 图建模 → 路径乘积 / 带权并查集。

相关题目

  • LC 990. 等式方程的可满足性（并查集）
  • LC 547. 省份数量（并查集求连通分量）
  • LC 200. 岛屿数量（图搜索）
  • LC 133. 克隆图（图的遍历）
刷题笔记 > Hot100 > 图论
#并查集 #图 #字符串 #深度优先搜索 #广度优先搜索 #Floyd
399. 除法求值
https://mingsm17518.github.io/2026/10/09/刷题笔记/Hot100/图/399. 除法求值/
作者
Ming
发布于
2026年10月9日
更新于
2026年10月9日
许可协议