摘要

这道题给了一组除法等式（比如 a/b=2.0、b/c=3.0）和一堆查询（比如问 a/c 等于多少），要你根据已知等式把每个查询的结果算出来。本质上是「带权图上的路径权值累乘」：把每个变量看成图上的点，每个等式看成两条有向边（a→b 权值 2.0，b→a 权值 0.5），查询 C/D 就相当于从 C 走到 D，把路径上的边权乘起来。用邻接表建图，对每个查询做一次 BFS 或 DFS，把沿路权值乘起来就能得到结果；如果 C、D 里有没出现过的变量，或者 C 到 D 根本不通，就返回 -1.0。下面用 Swift 实现并说明建图和查询的细节。

描述

题目会给你两个输入：一个是变量对数组 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 = ? → 由 a/b * b/c = 2*3 = 6.0；b / a = ? → 1/2 = 0.5；a / e = ? 中 e 未定义 → -1.0；a / a = ? → 1.0；x / x 中 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 <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai、Bi、Cj、Dj 由小写英文字母与数字组成

核心思路：把变量当作图的顶点，等式当作带权有向边（A/B=v 则 A→B 权 v，B→A 权 1/v），对每个查询在图上从分子走到分母，路径上边权相乘即为商；未出现变量或不可达则返回 -1.0。

题解答案

class Solution399 {
    func calcEquation(
        _ equations: [[String]],
        _ values: [Double],
        _ queries: [[String]]
    ) -> [Double] {
        var graph: [String: [(String, Double)]] = [:]
        for (i, eq) in equations.enumerated() {
            let a = eq[0], b = eq[1]
            let v = values[i]
            graph[a, default: []].append((b, v))
            graph[b, default: []].append((a, 1.0 / v))
        }

        func query(_ c: String, _ d: String) -> Double {
            if !graph.keys.contains(c) || !graph.keys.contains(d) {
                return -1.0
            }
            if c == d { return 1.0 }
            var visited: Set<String> = [c]
            var queue: [(String, Double)] = [(c, 1.0)]
            while !queue.isEmpty {
                let (node, product) = queue.removeFirst()
                for (neighbor, weight) in graph[node] ?? [] {
                    if neighbor == d { return product * weight }
                    if visited.insert(neighbor).inserted {
                        queue.append((neighbor, product * weight))
                    }
                }
            }
            return -1.0
        }

        return queries.map { query($0[0], $0[1]) }
    }
}

题解代码分析

为什么要用图来建模

题目里的等式本质上是在说「某些变量之间的倍数关系」。比如 a/b=2、b/c=3，我们虽然不知道 a、b、c 各自的具体数值，但可以推出 a/c = (a/b)*(b/c) = 6。这种「通过中间变量把两个变量连起来」的结构，天然适合用图表示：每个变量一个点，每给出一个 A/B=v，就从 A 连一条到 B 的边，权值为 v（表示「从 A 到 B 要乘上 v」），同时从 B 连一条到 A 的边，权值为 1/v。这样，查询 C/D 就变成：在图上从 C 出发找一条到 D 的路径，把路径上每条边的权值乘起来，得到的就是 C/D。用邻接表 graph: [String: [(String, Double)]] 存图，每个点对应一个「(邻居, 边权)」的列表，查边、遍历邻居都很方便。

建图时正反两条边

对于等式 A/B = v，我们既会用到「A 除以 B」也会用到「B 除以 A」。所以在建图时同时加两条边：A→B 权值 v（表示 A/B=v），B→A 权值 1/v（表示 B/A=1/v）。这样无论查询的是 a/c 还是 c/a，只要在图上从起点走到终点，沿路乘权值即可，不需要在查询时再区分方向。

查询时 BFS 在做什么

对单个查询 (C, D)，先做两个判断：若 C 或 D 不在图的顶点集里（即从未在任何等式中出现过），直接返回 -1.0；若 C == D，同一个变量除以自己，返回 1.0。否则从 C 开始 BFS：队列里存 (当前节点, 从 C 到当前节点为止的权值乘积)。初始为 (C, 1.0)。每次取出 (node, product)，遍历 node 的每条出边 (neighbor, weight)，若 neighbor 就是 D，说明找到了 C 到 D 的一条路径，乘积为 product * weight，即为 C/D，直接返回；若 neighbor 还没访问过，就标记访问并把它和 product * weight 入队。若 BFS 结束都没找到 D，说明 C 和 D 不在同一连通分量，无法通过已知等式建立关系，返回 -1.0。

为什么用 BFS 而不是 DFS

这道题只要求得到任意一条从 C 到 D 的路径的权值乘积。在无环图（题目保证无矛盾，等价于我们建的图在「变量关系」意义下不会出现环导致冲突）上，BFS 和 DFS 都能找到一条路径，且由于边权是确定的，任意一条路径的乘积都相同。用 BFS 可以保证找到的是「步数最少」的一条，逻辑清晰；用 DFS 写也可以，代码里把 queue 换成栈即可。这里用 BFS 便于理解「逐层扩展」的过程。

示例 1 的建图与查询过程

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)]。查询 a/c：从 a 出发，product=1.0；到 b 得 product=2.0，b≠c 继续；从 b 到 c 得 product=2.0*3.0=6.0，且 neighborc，返回 6.0。查询 b/a：从 b 到 a 一条边，权 0.5，返回 0.5。查询 a/e：e 不在图中，返回 -1.0。查询 a/a：cd，返回 1.0。查询 x/x：x 不在图中，返回 -1.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/c 通过 a→b→c 得到 2*3=6；b/a 为 1/2=0.5；a/e 中 e 未出现；a/a 为 1；x 未出现故 x/x 为 -1。

示例 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；bc/cd = 5.0；cd/bc = 1/5 = 0.2。

示例 3：单等式与未定义变量

equations = [[“a”,“b”]], values = [0.5]，queries = [[“a”,“b”],[“b”,“a”],[“a”,“c”],[“x”,“y”]]。结果 [0.5, 2.0, -1.0, -1.0]。a/b=0.5，b/a=2.0；a/c 中 c 未出现；x、y 都未出现，均为 -1。

自除与不连通

同一变量除以自己（且该变量在图中）应返回 1.0。若两个变量从未通过任何等式链相连（图里不连通），应返回 -1.0。

时间复杂度

设等式数量为 E，变量数为 V，查询数为 Q。建图需要遍历 equations 和 values，为 O(E)。单次查询的 BFS 最坏要访问所有顶点和边，为 O(V+E)。总共 Q 次查询，整体时间复杂度为 O(E + Q*(V+E))。在本题数据范围下 E、V、Q 都不超过 20，实际运行非常快。

空间复杂度

邻接表 graph 存的是所有边，每条等式对应两条边，空间 O(E)。每次查询的 visited 和 queue 最多 O(V)。总空间 O(E + V)，即与变量数和等式数同阶。

与实际场景的结合

这类「已知若干比例关系，求未知比例」的问题，在实际里很常见。比如汇率：已知 USD/CNY、EUR/USD，可以求 EUR/CNY；再比如单位换算：米/英尺、英尺/英寸已知，可以求米/英寸。还有化学里的摩尔比、金融里的资产相对估值，只要能把关系抽象成「A/B 等于多少」，并且关系可以传递，就可以用同一套建图 + BFS/DFS 的方式批量算查询。未出现或不可达的变量对应「没有报价」或「无法换算」，用 -1 表示很合理。

总结

LeetCode 399 除法求值的做法是：用邻接表建一张带权有向图，每个等式 A/B=v 对应 A→B 权 v、B→A 权 1/v；对每个查询 (C, D)，若 C 或 D 未出现过则返回 -1.0，若 C==D 则返回 1.0，否则从 C 开始 BFS，沿路径累乘边权，到达 D 时得到的乘积即为 C/D，若无法到达则返回 -1.0。思路清晰，实现简单，且和实际中的汇率、单位换算等场景一致，便于理解和复用。