LeetCode LCR 111. 除法求值

2026-03-28 HGNULB 约 14 分钟

文章信息 5 个分类 7 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 111. 除法求值

题意分析

给一组形如 a / b = k 的已知等式（变量用字符串表示），再给一组询问 c / d = ?。能由已知等式推出结果就返回该值，推不出来（变量没出现过，或两个变量之间没有关系链）就返回 -1.0。

「能推出来」的含义要说清楚：如果已知 a / b = 2、b / c = 3，那么 a / c = 2 × 3 = 6。也就是说除法关系是可以沿着链条相乘传递的，并且反向走时要取倒数。这条乘法传递性是整道题的数学基础。

把变量看成节点、把 a / b = k 看成一条从 a 到 b、权值为 k 的边（反向边权为 1/k），询问就变成了「求两点之间某条路径上的权值乘积」。因为已知等式是自洽的（题目保证不存在矛盾），同一连通分量内任意两条路径的乘积必然相等，所以随便找一条路径都行。

由此得到一条极其重要的推论：只要 c 和 d 在同一个连通分量里，答案就存在；不在同一分量（或某个变量根本没出现过），答案就是 -1。判断连通性正是并查集最擅长的事，只不过这里的并查集要额外携带「比值」这个权。

约束里等式数量与询问数量都不超过 20，变量长度不超过 5，规模极小，所以效率不是考点——考点是如何把带比例的关系压进并查集，或者说如何维护「每个节点相对于它的代表元的倍率」。

边界：询问中出现从未在等式里露过面的变量，即使形如 x / x 也必须返回 -1（因为 x 的值未定义）；而如果 a 出现过，a / a 应当返回 1.0；题目保证 values[i] > 0，所以除法不会出现除零，也不必担心符号。

解法：并查集维护连通性

核心思路

最直观的做法是建图跑搜索：把变量当节点、等式当带权边，每次询问从 c 出发做一次 DFS/BFS，沿途把边权连乘，走到 d 就返回乘积。这个做法完全正确，也是很多人第一反应写出来的答案。

它的问题在于每次询问都要重新走一遍图，$q$ 次询问就是 $q$ 次遍历。更本质的问题是：它没有把「同一个分量内的比例关系」这个结构沉淀下来，每次都在重复推导相同的链条。

换个角度想：如果能给每个连通分量选一个「基准变量」（也就是并查集的代表元/根），并且记录下每个变量相对于基准的倍率，那么任意两个同分量变量的比值就可以一步算出——因为 $\dfrac{c}{d} = \dfrac{c/root}{d/root}$，两个倍率一除，中间的基准被约掉了。

这就是带权并查集：在普通并查集的父指针 p[x] 之外，再维护一个 w[x]，其含义是 $w[x] = \dfrac{x \text{ 的值}}{p[x] \text{ 的值}}$，即当前节点相对于它父节点的倍率。

有了这个定义，两个操作要相应地改造。

find(x) 在做路径压缩时，把 x 直接挂到根上，那么 w[x] 的语义就必须从「相对父亲」升级成「相对根」。做法是先记下旧父亲 origin = p[x]，递归压缩它（递归返回后 w[origin] 已经变成「origin 相对根」的倍率），然后执行 w[x] *= w[origin]——两段倍率相乘，正是 $\dfrac{x}{origin} \times \dfrac{origin}{root} = \dfrac{x}{root}$。这一行必须写在递归之后，因为它依赖递归把 w[origin] 先更新好。

union(a, b, v)（表示 $a / b = v$）要把 a 所在的根 pa 挂到 b 所在的根 pb 下，同时算出 w[pa]，也就是 $\dfrac{pa}{pb}$。推导过程是：调用完两次 find 后有 $w[a] = \dfrac{a}{pa}$、$w[b] = \dfrac{b}{pb}$，于是 $\dfrac{pa}{pb} = \dfrac{a / w[a]}{b / w[b]} = \dfrac{a}{b} \cdot \dfrac{w[b]}{w[a]} = v \cdot \dfrac{w[b]}{w[a]}$。代码里就是 w[pa] = w[b] * v / w[a]。

不变量贯穿全程：任何时刻，w[x] 恒等于「x 的值除以 p[x] 的值」；经过一次 find(x) 之后，p[x] 是根且 w[x] 是 x 相对根的倍率。所有的赋值都只是在维持这条不变量。

询问时先对 c、d 各做一次 find 把它们压到根上，若根不同则返回 -1，否则返回 $\dfrac{w[c]}{w[d]}$。变量没在等式中出现过时连编号都没有，直接返回 -1。

解题步骤

给每个出现过的变量分配一个整数编号。为什么要编号：并查集用数组实现最简洁，而变量是字符串；用哈希表做「字符串 → 下标」的映射，既完成了编号，又天然记录了「这个变量是否出现过」，一举两得。

数组开到 2 * equations.size()。为什么这个大小够用：每条等式最多引入两个新变量，n 条等式最多有 2n 个不同变量，再大就浪费了。

初始化 p[i] = i、w[i] = 1.0。为什么 w 初值是 1：初始时每个节点自成一集、自己就是根，$\dfrac{x}{x} = 1$，这与不变量完全吻合。

遍历等式，先给两端变量分配编号（若尚未分配）。为什么必须先分配再查找：find 要用下标索引数组，没编号的变量无法参与合并。

求出两端的根 pa = find(A)、pb = find(B)；若相同则跳过。为什么相同就跳过：说明这条关系此前已被推出，题目保证数据自洽，重复的信息不会带来新约束，强行合并反而会破坏已有的 w。

否则执行 p[pa] = pb 与 w[pa] = w[B] * values[i] / w[A]。为什么用两端节点的 w 而不是根的：find 刚刚把 A、B 压到了各自的根上，此刻 w[A]、w[B] 正好是相对根的倍率，代入前面推出的公式即可。为什么两句的顺序无关紧要：w[pa] 的计算只依赖 w[A]、w[B]，不依赖 p[pa]，但写在一起便于阅读。

find 用递归实现路径压缩，并在递归返回后执行 w[x] *= w[origin]。为什么要先保存 origin = p[x]：递归里 p[x] 会被改写成根，事后再读就拿不到原来的父亲了。为什么乘法必须在递归之后：递归返回时 w[origin] 才被更新为「相对根」，提前相乘会用到过时的值。

处理询问时先查两个变量是否有编号，没有则直接填 -1。为什么不能跳过这一步：未出现过的变量在数组里没有位置，find 会越界或访问到无意义的初始值，还可能误判成「与某个分量连通」。

两个变量都有编号时，比较 find 的结果；根相同返回 w[c] / w[d]，否则返回 -1。为什么必须先调用 find 再读 w：w[c] 只有在 c 被压缩到根之后才是「相对根」的倍率，直接读可能拿到「相对某个中间父亲」的旧值。

以 equations = [["a","b"],["b","c"]]、values = [2.0, 3.0]、queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 走一遍。

初始化：n = 2，数组长度 4，p = [0,1,2,3]，w = [1,1,1,1]，映射为空。

处理 a / b = 2：a 编号 0、b 编号 1。find(0) = 0、find(1) = 1，根不同。执行 p[0] = 1，w[0] = w[1] * 2.0 / w[0] = 1 × 2 / 1 = 2。此时 w[0] = 2 的含义正是 $\dfrac{a}{b} = 2$，与不变量吻合。

处理 b / c = 3：c 编号 2。find(1) = 1、find(2) = 2，根不同。执行 p[1] = 2，w[1] = w[2] * 3.0 / w[1] = 1 × 3 / 1 = 3，即 $\dfrac{b}{c} = 3$。此刻结构是 a → b → c，w = [2, 3, 1, 1]。

询问 a / c：先 find(0)。p[0] = 1 ≠ 0，记下 origin = 1，递归 find(1)：p[1] = 2 ≠ 1，记下 origin = 2，递归 find(2) = 2（c 是根），于是 p[1] = 2（不变），w[1] *= w[2] = 1，仍是 3。返回 2。回到外层：p[0] = 2，w[0] *= w[origin=1] = 2 × 3 = 6——链条被压平，w[0] = 6 恰好是 $\dfrac{a}{c}$。再 find(2) = 2，两根相同，返回 $\dfrac{w[0]}{w[2]} = \dfrac{6}{1} = 6$。

询问 b / a：find(1) = 2、find(0) = 2，根相同，返回 $\dfrac{w[1]}{w[0]} = \dfrac{3}{6} = 0.5$。可以验证：$\dfrac{b}{a} = \dfrac{1}{2}$，正确。这里也体现了「两个相对根的倍率一除、根被约掉」的核心思想。

询问 a / e：e 从未在等式中出现，映射里查不到，直接返回 -1。

询问 a / a：a 有编号，find(0) = find(0)，返回 $\dfrac{w[0]}{w[0]} = 1$。

询问 x / x：x 没有编号，返回 -1。注意它与上一条的区别——同样是「自己除以自己」，变量是否被定义决定了答案是 1 还是 -1。

最终结果 [6.0, 0.5, -1.0, 1.0, -1.0]。

如果把 w[x] *= w[origin] 写在递归之前：find(0) 时 w[origin=1] 还是「b 相对 c」之前的旧值 3（此例恰好相同），但在更深的链条上（比如 a → b → c → d）就会用到尚未压缩的中间倍率，w[0] 得到的乘积会缺一段，询问结果直接偏小。

代码实现

class Solution {
    private int[] p;
    private double[] w;

    public double[] calcEquation(
        List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n = equations.size();
        // 每条等式最多引入两个新变量。
        p = new int[n << 1];
        w = new double[n << 1];
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
            // 初始时自己是根，x / x = 1。
            w[i] = 1.0;
        }
        Map<String, Integer> mp = new HashMap<>(n << 1);
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            List<String> e = equations.get(i);
            String a = e.get(0), b = e.get(1);
            if (!mp.containsKey(a)) {
                mp.put(a, idx++);
            }
            if (!mp.containsKey(b)) {
                mp.put(b, idx++);
            }
            int pa = find(mp.get(a)), pb = find(mp.get(b));
            if (pa == pb) {
                continue;
            }
            p[pa] = pb;
            // pa / pb = (a / b) * (w[b] / w[a])。
            w[pa] = w[mp.get(b)] * values[i] / w[mp.get(a)];
        }
        int m = queries.size();
        double[] res = new double[m];
        for (int i = 0; i < m; ++i) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            Integer id1 = mp.get(c), id2 = mp.get(d);
            // 变量从未出现过，值未定义。
            if (id1 == null || id2 == null) {
                res[i] = -1.0;
            } else {
                int pa = find(id1), pb = find(id2);
                res[i] = pa == pb ? w[id1] / w[id2] : -1.0;
            }
        }
        return res;
    }

    private int find(int x) {
        if (p[x] != x) {
            int origin = p[x];
            p[x] = find(p[x]);
            // 递归返回后 w[origin] 已是「相对根」，此处两段倍率相乘。
            w[x] *= w[origin];
        }
        return p[x];
    }
}

var p []int
var w []float64

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    n := len(equations)
    p = make([]int, (n<<1)+10)
    w = make([]float64, (n<<1)+10)
    for i := 0; i < (n<<1)+10; i++ {
        p[i] = i
        // 初始时自己是根，x / x = 1。
        w[i] = 1.0
    }
    mp := make(map[string]int)
    // 下标从 1 开始，0 用来表示「未出现过」。
    idx := 1
    for i, e := range equations {
        a, b := e[0], e[1]
        if mp[a] == 0 {
            mp[a] = idx
            idx++
        }
        if mp[b] == 0 {
            mp[b] = idx
            idx++
        }
        pa, pb := find(mp[a]), find(mp[b])
        if pa == pb {
            continue
        }
        p[pa] = pb
        // pa / pb = (a / b) * (w[b] / w[a])。
        w[pa] = w[mp[b]] * values[i] / w[mp[a]]
    }
    var res []float64
    for _, q := range queries {
        c, d := q[0], q[1]
        // 变量从未出现过，值未定义。
        if mp[c] == 0 || mp[d] == 0 {
            res = append(res, -1.0)
        } else {
            pa, pb := find(mp[c]), find(mp[d])
            if pa == pb {
                res = append(res, w[mp[c]]/w[mp[d]])
            } else {
                res = append(res, -1.0)
            }
        }
    }
    return res
}

func find(x int) int {
    if p[x] != x {
        origin := p[x]
        p[x] = find(p[x])
        // 递归返回后 w[origin] 已是「相对根」，此处两段倍率相乘。
        w[x] *= w[origin]
    }
    return p[x]
}

复杂度分析

时间复杂度：$O((n + q) \cdot \alpha(n))$，其中 $n$ 是等式数、$q$ 是询问数，$\alpha$ 是反阿克曼函数。凭什么：初始化是 $O(n)$；每条等式做常数次 find 与一次合并；每个询问做两次 find 与一次除法。路径压缩把单次 find 的均摊代价压到接近常数，字符串哈希的额外开销是变量长度（本题不超过 5）的常数倍。

空间复杂度：$O(n)$。凭什么：父数组、权数组各是 $2n$ 量级，哈希表最多存 $2n$ 个变量；find 的递归深度在压缩后趋于常数，最坏（首次压缩前）不超过树高。

关键点总结

「关系可传递、可求逆」的题目要往并查集想；普通并查集只能回答「是否同类」，要回答「差多少倍 / 差多少」就升级成带权并查集，权表示「当前节点相对父节点的量」。

带权并查集的全部难点都在两处公式：路径压缩时 w[x] *= w[origin]（两段关系复合），合并时 w[pa] = w[b] * v / w[a]（用两端相对根的量反推两根之间的量）。面试时能当场推导这两条，比背下来更有说服力。

w[x] *= w[origin] 必须写在递归之后，因为它依赖递归先把 w[origin] 更新成「相对根」；这是所有带权并查集实现最容易写反的一行。

查询前必须先对两个变量各做一次 find，否则 w 可能还停留在「相对某个中间节点」的旧语义上。

「变量是否出现过」这一层判断不能省：未定义变量即使形如 x / x 也要返回 -1，而已定义变量的 a / a 要返回 1，两者的区别只能靠映射表回答。

面试视角：本题也可以用「建图 + 每次询问跑一次 DFS/BFS 连乘边权」来解，思路更直白、更好现场写；而带权并查集在询问次数远大于等式数时更优。两种都能说、并给出选择依据，是这道题的满分答案。

易错点总结

w[x] *= w[origin] 写在递归调用之前：equations = [["a","b"],["b","c"],["c","d"]]、values = [2,3,4] 查询 a / d 会得到 6 而不是 24，因为压缩时用到了尚未更新的中间倍率。

忘记保存 origin = p[x]，直接写 w[x] *= w[p[x]]：递归已把 p[x] 改成根，w[根] 恒为 1，同一用例的 a / d 会退化成 2。

合并时写成 w[pa] = values[i]：equations = [["a","b"],["b","c"]] 中第二次合并会丢掉 a 已积累的倍率，查询 a / c 得到 3 而不是 6。

查询时不先调用 find 就直接读 w：equations = [["a","b"],["b","c"]] 查询 a / c 时 w[a] 仍是「相对 b」的 2，结果返回 2 而不是 6。

未出现过的变量不做判断直接 find：queries = [["x","x"]] 会用哈希表的默认值 0 去索引数组，Java 中 mp.get(c) 返回 null 触发拆箱空指针，Go 里则会误判成与 0 号变量连通并返回 1.0，而正确答案是 -1。

误以为 x / x 一律返回 1：equations = [["a","b"]]、queries = [["x","x"]] 的正确答案是 -1，只有已定义的变量才有 a / a = 1。

pa == pb 时仍执行合并：重复或冗余的等式（如再给一条 a / b = 2）会把根自己挂到自己下面并改写 w，破坏已建立的比例关系，后续查询全部失真。

数组开得不够大：只按 equations.size() 开而不是 2 * equations.size()，equations = [["a","b"],["c","d"]] 就会在给第三、第四个变量编号时越界。

用 == 比较 Java 的 Integer 编号：变量数超过 128 时装箱缓存失效，id1 == id2 恒为假，本题规模小不会触发，但同样写法在大数据版本会静默出错。

担心浮点精度而对结果做四舍五入：题目允许 $10^{-5}$ 的误差，倍率连乘的天然精度已经足够，多余的取整反而可能让 a / c = 6 输出成 5.99999 之外的错误值。

相似题目

题目	难度	考察点
399. 除法求值	中等	与本题同题，可直接套用同一份代码
990. 等式方程的可满足性	中等	关系只有「相等」没有倍率，退化成普通并查集，但必须先处理等式再验不等式
684. 冗余连接	中等	用并查集检测成环并返回该边，考察「先查后合」而非权值维护
547. 省份数量	中等	只数连通分量个数，是并查集最基础的形态，可用来对照带权版的额外负担
721. 账户合并	中等	同样要给字符串编号，但合并后还需按根聚合并排序输出
1202. 交换字符串中的元素	中等	下标之间的可交换关系构成连通块，每块内部排序，考察分组后的重排
785. 判断二分图	中等	需要表达「异类」关系，用扩展域并查集或染色搜索，是带权思想的另一分支