Algorithms first

除法求值 · 交互式算法学习

根据变量比值图回答除法查询。

#399 · 图

除法求值

Evaluate Division

测试用例equations = [[a,b],[b,c]], values = [2,3], query = a/c

树 / 图3 个关键状态

进度 1 / 3速度

步骤 1初始化每个变量为独立集合。3 sets

批量查询优化

加权并查集

时间 近 O((E+Q)α(V))空间 O(V)

并查集同时维护节点到父节点的比例，查询同集合节点的权重比。

1function calcEquation(eq, val, qs) {2  const p = new Map(),3    w = new Map();4 5  function find(x) {6    if (p.get(x) !== x) {7      const old = p.get(x),8        root = find(old);9      w.set(x, w.get(x) * w.get(old));10      p.set(x, root)11    }12    return p.get(x)13  }14  eq.flat().forEach(x => {15    if (!p.has(x)) {16      p.set(x, x);17      w.set(x, 1)18    }19  });20  eq.forEach(([a, b], i) => {21    const ra = find(a),22      rb = find(b);23    p.set(ra, rb);24    w.set(ra, val[i] * w.get(b) / w.get(a))25  });26  return qs.map(([a, b]) => !p.has(a) || !p.has(b) || find(a) !== find(b) ? -1 : w.get(a) / w.get(b));27}

多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Solution {2    private Map<String, String> p;3    private Map<String, Double> w;4 5    public double[] calcEquation(6        List<List<String>> equations, double[] values, List<List<String>> queries) {7        int n = equations.size();8        p = new HashMap<>();9        w = new HashMap<>();10        for (List<String> e : equations) {11            p.put(e.get(0), e.get(0));12            p.put(e.get(1), e.get(1));13            w.put(e.get(0), 1.0);14            w.put(e.get(1), 1.0);15        }16        for (int i = 0; i < n; ++i) {17            List<String> e = equations.get(i);18            String a = e.get(0), b = e.get(1);19            String pa = find(a), pb = find(b);20            if (Objects.equals(pa, pb)) {21                continue;22            }23            p.put(pa, pb);24            w.put(pa, w.get(b) * values[i] / w.get(a));25        }26        int m = queries.size();27        double[] ans = new double[m];28        for (int i = 0; i < m; ++i) {29            String c = queries.get(i).get(0), d = queries.get(i).get(1);30            ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d))31                ? -1.032                : w.get(c) / w.get(d);33        }34        return ans;35    }36 37    private String find(String x) {38        if (!Objects.equals(p.get(x), x)) {39            String origin = p.get(x);40            p.put(x, find(p.get(x)));41            w.put(x, w.get(x) * w.get(origin));42        }43        return p.get(x);44    }45}

交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。

动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。

适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。

AlgoViz Lab

除法求值 · 解法对比

AlgoViz Lab2026-07-112026-07-12

根据变量比值图回答除法查询。

测试用例: equations = [[a,b],[b,c]], values = [2,3], query = a/c
题目分类: 图
解法对比: 2

方案 1

每次查询 DFS

把 a/b=2 建成 a→b 权重 2 与反向边，查询时搜索路径乘积。

时间: O(Q(V+E))
空间: O(V+E)

方案 2

加权并查集

并查集同时维护节点到父节点的比例，查询同集合节点的权重比。

时间: 近 O((E+Q)α(V))
空间: O(V)