在问 · 算法题解

399. 除法求值

中等图论建图 + 广度优先搜索力扣原题 ↗
在线写代码并运行看动画推演问 AI 讲解

题目描述

输入已知条件 equations 和 values：equations[i] = [A, B] 与 values[i] 一起表示 A / B = values[i]。每个变量是一个字符串。

另给若干询问 queries，queries[j] = [C, D] 要求计算 C / D 的值。

返回一个与 queries 等长的浮点数数组，按询问顺序给出答案。如果某个结果无法由已知条件推出，答案记为 -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.0,0.5,-1.0,1.0,-1.0]

解释：由 a / b = 2、b / c = 3 推出 a / c = 6、b / a = 0.5；e 和 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.75,0.4,5.0,0.2]

解释：a / c = 1.5 × 2.5 = 3.75，c / b = 1 / 2.5 = 0.4。

示例 3
输入：equations = [["a","b"]]
values = [0.5]
queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.5,2.0,-1.0,-1.0]

解释：c、x、y 没有出现在已知条件里。

数据范围

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= A.length, B.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= C.length, D.length <= 5
  • 变量名只含小写英文字母和数字

解题思路：建图 + 广度优先搜索

把每个变量看作图的节点，A / B = v 建两条有向边：A→B 权 v，B→A 权 1/v。求 C / D 就是从 C 出发找一条到 D 的路径，把沿途边权乘起来：(C/X)·(X/Y)·(Y/D) = C/D。每个查询做一次 BFS，队列里带上到当前节点的乘积。变量没出现过或不连通就是 -1。

为什么正确

队列中的 (node, prod) 满足 prod = src / node。

复杂度分析

每个查询 O(V + E)，总时间 O(Q·(V + E))；空间 O(V + E)。

易错点

未出现过的变量即使是 x / x 也要返回 -1.0，必须先判断是否在图中；反向边的权是倒数 1/v，不是 v。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}
        for (a, b), v in zip(equations, values):
            graph.setdefault(a, {})[b] = v
            graph.setdefault(b, {})[a] = 1 / v
        ans = []
        for src, dst in queries:
            if src not in graph or dst not in graph:
                ans.append(-1.0)
                continue
            seen = {src}
            queue = [(src, 1.0)]
            res = -1.0
            head = 0
            while head < len(queue):
                node, prod = queue[head]
                head += 1
                if node == dst:
                    res = prod
                    break
                for nxt, w in graph[node].items():
                    if nxt not in seen:
                        seen.add(nxt)
                        queue.append((nxt, prod * w))
            ans.append(res)
        return ans

载入编辑器，自己跑一遍 →

其他解法

广度优先搜索每次查询都重新搜图，实现直观；Floyd 先算出所有点对的比值，查询最快但预处理是立方级；带权并查集在合并与查找时维护比值，整体效率最高。

解法 2：Floyd 预处理 时间 O(n³ + q)，空间 O(n²)

设 n 为变量个数，e 为等式个数，q 为查询个数。把变量编号，用矩阵 d 记录已知比值，d[i][i] = 1，未知记为 -1。按 Floyd 算法枚举中转点 k，若 d[i][k] 和 d[k][j] 都已知，就令 d[i][j] = d[i][k]·d[k][j]。查询时直接读矩阵，变量不存在时返回 -1。

预处理后每次查询 O(1)，适合查询很多、变量较少的情况。变量多时 O(n³) 预处理和 O(n²) 空间代价很大。

class Solution:
    def calcEquation(self, equations, values, queries):
        idx = {}
        for a, b in equations:
            for x in (a, b):
                if x not in idx:
                    idx[x] = len(idx)
        n = len(idx)
        d = [[-1.0] * n for _ in range(n)]
        for i in range(n):
            d[i][i] = 1.0
        for (a, b), v in zip(equations, values):
            d[idx[a]][idx[b]] = v
            d[idx[b]][idx[a]] = 1 / v
        for k in range(n):
            for i in range(n):
                if d[i][k] < 0:
                    continue
                for j in range(n):
                    if d[k][j] > 0 and d[i][j] < 0:
                        d[i][j] = d[i][k] * d[k][j]
        ans = []
        for a, b in queries:
            if a not in idx or b not in idx:
                ans.append(-1.0)
            else:
                ans.append(d[idx[a]][idx[b]])
        return ans

解法 3：带权并查集 时间 O((e + q)·α(n))，空间 O(n)

每个变量记录父节点 parent 和权值 weight，weight[x] 表示 x 除以 parent[x] 的值。查找根时做路径压缩，并把沿途权值相乘。合并 a / b = v 时，把 a 的根挂到 b 的根下，权值设为 v·weight[b] / weight[a]。查询时两个变量同根则答案是 weight[a] / weight[b]，否则返回 -1。

建图和查询都接近线性，是三种方法里最快的。权值随路径压缩更新的推导是难点，写错不易发现。

class Solution:
    def calcEquation(self, equations, values, queries):
        parent = {}
        weight = {}

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

        for (a, b), v in zip(equations, values):
            for x in (a, b):
                if x not in parent:
                    parent[x] = x
                    weight[x] = 1.0
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                weight[ra] = v * weight[b] / weight[a]
        ans = []
        for a, b in queries:
            if a not in parent or b not in parent or find(a) != find(b):
                ans.append(-1.0)
            else:
                ans.append(weight[a] / weight[b])
        return ans

图论 专题的其他题目

查看 图论 全部题目 →