LeetCode 399. 除法求值

约 6 分钟
文章信息 10 个分类 7 个标签
分类
LeetCode CodeTop 中等 已解决 5-10 LeetCode 75 面试经典 150 题 字节 阿里 美团
标签
数组 字符串 深度优先搜索 广度优先搜索 图 并查集 最短路

题目描述

✅ 399. 除法求值

image-20260928235737000

image-20260928235737001

题意分析

已知若干变量之间的除法等式，查询两个变量的比值。可以借助其他变量串联推导，不要求查询对应的等式直接出现在输入中。

若任一变量从未出现在等式中，或者两个已知变量之间没有关系链，结果都是 -1.0。因此未知变量除以自身也不能直接返回 1.0。

解法：建图加 BFS

核心思路

[!blue]

把变量作为图的节点。等式 a / b = v 给出两条有向边：a → b 的权重为 v，表示 a / b；b → a 的权重为 1 / v，表示反向比值。两边都建，才能沿任一方向推导。

对查询 start / target，从 start 开始 BFS。定义 ratio[x] 为已经推导出的 start / x，起点有 ratio[start] = 1。沿权重为 cur / next 的边扩展时，有 ratio[next] = ratio[cur] * weight，因为中间变量 cur 会在乘法中约掉。

题目保证已知等式不存在矛盾，所以同一个可达变量通过不同路径得到的比值一致。一个变量首次发现后，无需再经其他路径访问；用 ratio 是否已有该键兼作访问标记，可以阻止正反边造成的循环。

找到目标时，当前路径乘积就是答案；队列耗尽仍未找到，说明目标与起点不连通。ratio 以本次查询的起点为基准，因此每次查询重新建立队列和 ratio，只复用图。

解题步骤

  1. 遍历等式，为两个变量建立邻接表，写入正向比值和反向倒数。
  2. 对每个查询，先检查两个变量是否都存在；若有未知变量，返回 -1.0。检查通过后，同一变量相除返回 1.0。
  3. 起点入队，并令 ratio[start] = 1.0。每次取出一个节点，只扩展尚未记录比例的邻居。
  4. 用当前比例乘边权得到邻居比例；若邻居就是目标，立即返回。否则先记录比例，再将邻居入队，避免重复加入队列。
  5. 队列清空仍未命中则返回 -1.0，将各次查询结果按原顺序写入答案数组。

代码实现

class Solution {
    public double[] calcEquation(
            List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            double value = values[i];

            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, value);
            // 反向边使用倒数，保持比例方向一致
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / value);
        }

        double[] ans = new double[queries.size()];

        for (int i = 0; i < queries.size(); i++) {
            ans[i] = bfs(graph, queries.get(i).get(0), queries.get(i).get(1));
        }

        return ans;
    }

    private double bfs(Map<String, Map<String, Double>> graph, String start, String target) {
        // 先判断变量存在，未知变量除以自身也无结果
        if (!graph.containsKey(start) || !graph.containsKey(target)) {
            return -1.0;
        }

        if (start.equals(target)) {
            return 1.0;
        }

        Queue<String> queue = new ArrayDeque<>();
        Map<String, Double> ratio = new HashMap<>();

        queue.offer(start);
        ratio.put(start, 1.0);

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            double curValue = ratio.get(cur);

            for (Map.Entry<String, Double> entry : graph.get(cur).entrySet()) {
                String next = entry.getKey();

                if (ratio.containsKey(next)) {
                    continue;
                }

                double nextValue = curValue * entry.getValue();

                if (next.equals(target)) {
                    return nextValue;
                }

                // 记录起点到此处的乘积，同时标记已经发现
                ratio.put(next, nextValue);
                queue.offer(next);
            }
        }

        return -1.0;
    }
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    graph := make(map[string]map[string]float64)
    for i, equation := range equations {
        a, b := equation[0], equation[1]
        if graph[a] == nil {
            graph[a] = make(map[string]float64)
        }
        if graph[b] == nil {
            graph[b] = make(map[string]float64)
        }
        graph[a][b] = values[i]
        // 反向边使用倒数，保持比例方向一致
        graph[b][a] = 1.0 / values[i]
    }

    ans := make([]float64, len(queries))
    for i, query := range queries {
        ans[i] = eval(graph, query[0], query[1])
    }
    return ans
}

func eval(graph map[string]map[string]float64, start string, target string) float64 {
    // 先判断变量存在，未知变量除以自身也无结果
    if graph[start] == nil || graph[target] == nil {
        return -1.0
    }
    if start == target {
        return 1.0
    }

    queue := []string{
        start,
    }
    ratio := map[string]float64{start: 1.0}
    for head := 0; head < len(queue); head++ {
        cur := queue[head]
        for next, value := range graph[cur] {
            if _, ok := ratio[next]; ok {
                continue
            }
            nextValue := ratio[cur] * value
            if next == target {
                return nextValue
            }
            // 记录起点到此处的乘积，同时标记已经发现
            ratio[next] = nextValue
            queue = append(queue, next)
        }
    }
    return -1.0
}

复杂度分析

  • 时间复杂度：设变量数为 $V$、等式数为 $E$、查询数为 $Q$。建图为 $O(E)$，图中至多有 $2E$ 条有向边，每次查询最多访问所有节点和边，总计 $O(E+Q(V+E))$。
  • 空间复杂度：$O(V+E)$ 保存图，单次搜索的队列与比例表另用 $O(V)$；不计返回结果数组。

关键点总结

[!green]

  • 路径通过乘法连接比例，反向边必须取倒数。
  • BFS 只是寻找一条可达路径，不需要最小化边权或比较不同路径的乘积。
  • 图可以复用，访问记录和相对起点的比例每次查询重新建立。

易错点总结

[!yellow]

  • 未知变量自除不能直接返回一。
  • 把路径权重相加会得到错误比值。
  • 无访问记录会沿正反边重复扩展，产生无用搜索。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/62658590
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！