LeetCode LCR 111. 除法求值

Categories:

题目描述
思路分析
1. 解法一：图建模 + DFS/BFS 搜索（推荐）
相似题目

题目描述

✅ LCR 111. 除法求值

思路分析

解法一：图建模 + DFS/BFS 搜索（推荐）

核心思路：

将等式 a / b = k 看成图中的一条有向边 a -> b，权重为 k。

同时加入反向边 b -> a，权重为 1 / k。

对每个查询，从起点 DFS/BFS，沿路径累乘权重即可得到结果。

复杂度分析：

时间复杂度：O(Q · (V + E))，其中 Q 表示查询数量，V 表示变量数。

空间复杂度：O(V + E)，用于图存储与访问标记。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

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 v = values[i];

            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, v);
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / v);
        }

        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String src = queries.get(i).get(0);
            String dst = queries.get(i).get(1);

            if (!graph.containsKey(src) || !graph.containsKey(dst)) {
                res[i] = -1.0;
                continue;
            }

            res[i] = dfs(graph, src, dst, 1.0, new HashSet<>());
        }
        return res;
    }

    private double dfs(Map<String, Map<String, Double>> graph,
                       String cur,
                       String target,
                       double acc,
                       Set<String> visited) {
        if (cur.equals(target)) {
            return acc;
        }
        visited.add(cur);

        for (Map.Entry<String, Double> entry : graph.get(cur).entrySet()) {
            String next = entry.getKey();
            if (visited.contains(next)) {
                continue;
            }
            double res = dfs(graph, next, target, acc * entry.getValue(), visited);
            if (res != -1.0) {
                return res;
            }
        }
        return -1.0;
    }
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	graph := make(map[string]map[string]float64)

	for i, eq := range equations {
		a, b := eq[0], eq[1]
		v := values[i]

		if graph[a] == nil {
			graph[a] = make(map[string]float64)
		}
		if graph[b] == nil {
			graph[b] = make(map[string]float64)
		}

		graph[a][b] = v
		graph[b][a] = 1.0 / v
	}

	res := make([]float64, len(queries))
	for i, q := range queries {
		src, dst := q[0], q[1]
		if graph[src] == nil || graph[dst] == nil {
			res[i] = -1.0
			continue
		}
		visited := make(map[string]bool)
		res[i] = dfsCalc(graph, src, dst, 1.0, visited)
	}
	return res
}

func dfsCalc(graph map[string]map[string]float64, cur string, target string, acc float64, visited map[string]bool) float64 {
	if cur == target {
		return acc
	}
	visited[cur] = true

	for next, weight := range graph[cur] {
		if visited[next] {
			continue
		}
		res := dfsCalc(graph, next, target, acc*weight, visited)
		if res != -1.0 {
			return res
		}
	}
	return -1.0
}

相似题目

题目	难度	考察点
399. 除法求值	中等	图、DFS/BFS
207. 课程表	中等	图、拓扑排序
210. 课程表 II	中等	图、拓扑排序
684. 冗余连接	中等	图、并查集
785. 判断二分图	中等	图、染色
841. 钥匙和房间	中等	图、DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/57554043