LeetCode 399. 除法求值
目录
题目描述
题意分析
输入是若干条形如
a / b = value的已知比值，以及若干条询问x / y的请求。要求对每条询问给出答案，无法从已知条件推出时返回-1.0。已知的比值是可以传递的：知道
a / b和b / c，就能推出a / c；同一条等式反过来读也成立，b / a等于value的倒数。所以「能否回答」取决于两个变量之间是否存在一条由已知等式串起来的推导链。约束里有几个关键信号：所有
value严格大于 0，因此不会出现除以零，倒数总是合法；变量用字符串标识，数量不大（等式和询问各不超过 20 条）；题目保证给出的等式之间不矛盾，也就是同一对变量沿不同推导链算出的比值一定相同，不需要做一致性校验。边界上最容易漏的是「变量根本没出现过」的情况：询问
x / x时，若x从未在任何等式里出现，答案是-1.0而不是1.0——题目要求的是「能否推出」，一个没被定义过的量不能凭自反性直接给 1。
解法：建图加 BFS
核心思路
直接对每条询问做符号推导很难落地：等式可以任意组合、正用反用，穷举组合方式没有收敛的方向。
换个表示：把每个变量看成一个点，把等式
a / b = value看成一条从a指向b、权为value的边，同时补一条从b指向a、权为1 / value的反向边。这样「先用a / b、再用b / c」就是沿着a → b → c走两步，而推导结果恰好是路径上边权的乘积。这一步的收益在于把「组合等式」变成了「找路径」，而找路径有现成的线性做法。此时的不变量是：从起点走到任意点
v的路径边权乘积，等于start / v的值，且与选哪条路径无关（题目保证等式无矛盾，所以不同路径给出同一个值）。有了这个不变量，就可以对每条询问从起点做一次广度优先搜索，队列里除了变量名还要携带「从起点到它的累积比值」。用一张
ratio表同时充当访问标记和累积值记录：某个变量一旦被写进ratio，说明它已入队且比值已确定，不必再从别的路径重复扩展，这也顺带避免了环上的死循环。搜索开始前先做两处特判：任一端点不在图中，说明它从未被定义，直接返回
-1.0；两端点相同且都已定义，返回1.0。搜索结束仍未触及终点，说明两者不连通，返回-1.0。这里使用 BFS 不是为了找“最短路径”：题目保证等式无矛盾，同一对变量之间任意路径的乘积都相同，找到一条可达路径即可。选择 BFS 只是因为迭代写法直观，也不会遇到递归栈过深的问题。
解题步骤
- 遍历
equations与values，建立邻接表graph，对第i条等式写入graph[a][b] = values[i]和graph[b][a] = 1 / values[i]。反向边必须一起建，否则只能沿等式书写方向推导。- 逐条处理询问。先判断起点和终点是否都作为键出现在
graph中，只要有一个没出现就返回-1.0。这一步要放在自反判断之前，否则未定义变量会被误判成1.0。- 若起点与终点相同（且都已定义），返回
1.0，不必进入搜索。- 初始化队列只含起点，
ratio[start] = 1.0。ratio里有键就代表已访问，省掉一个额外的集合。- 循环取出队首变量
cur，遍历它的所有邻居next：next已在ratio中就跳过；否则算出nextValue = ratio[cur] * graph[cur][next]，若next就是终点立刻返回nextValue，否则写入ratio并入队。提前返回是因为无矛盾保证下，先到达的路径与其他路径答案一致。- 队列耗尽仍未命中终点，返回
-1.0。以
a / b = 2.0、b / c = 3.0为例：从a出发时先得到a / b = 1.0 × 2.0 = 2.0，再得到a / c = 2.0 × 3.0 = 6.0；反向查询b / a直接使用反向边得到0.5。查询a / e时e未定义，查询x / x时x也未定义，两者都返回-1.0。这组例子同时覆盖了路径乘积、反向边和未知变量自查询三个关键边界。
代码实现
import java.util.*;
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
}
复杂度分析
- 时间复杂度：$O(e + q(v + e))$，
e为等式数、v为变量数、q为询问数；建图一次扫完所有等式，每条询问最坏要遍历整张图的点和边。- 空间复杂度：$O(v + e)$，邻接表存下双向边；不计图和答案时，单次 BFS 的队列与
ratio表额外占用 $O(v)$。
关键点总结
- 「已知若干两两关系、求任意两者关系」是一类固定的建模信号：把对象当点、关系当边，问题就从代数推导变成路径搜索。
- 关系可逆时反向边必须显式建出来，权重取逆运算的结果；本题是倒数，若关系是加法差值则取相反数。
- BFS 状态必须携带从查询起点到当前点的路径乘积；
ratio同时保存这个值并充当访问标记，天然防住环上的重复扩展。- 存在性检查必须早于自反性检查，否则未定义变量的自查询会被错答成
1.0。这类「先验条件优先」的顺序问题在面试中很常被追问。- BFS 求的是任意可达路径，不是最短路；如果等式和查询规模很大且查询远多于建图，再考虑用带权并查集把查询降到近似常数时间。
易错点总结
- 错误写法：只建
graph[a][b] = value，不建反向边 →equations = [["a","b"]]、values = [2.0]，询问b / a：搜索从b出发无路可走，返回-1.0，正确答案是0.5。- 错误写法：先判断
start.equals(target)再判断变量是否存在 → 询问x / x而x从未出现：返回1.0，正确答案是-1.0。- 错误写法：搜索时不记录已访问变量 →
equations = [["a","b"],["b","c"],["c","a"]]这类成环的输入，a → b → c → a会无限循环，程序超时。- 错误写法：把累积比值存在一个单独变量里、而不是随节点入队 → 从
a出发有两条分支时，第二条分支会沿用第一条分支留下的乘积，equations = [["a","b"],["a","c"]]询问a / c会算成a/b × a/c，结果错误。- 错误写法：出队时才标记访问 → 同一个变量可能先被多条边重复入队，虽然不一定算错，却会造成无意义的重复状态；应在入队时立即写入
ratio。- 错误写法：认为「变量存在」就一定「可达」 →
equations = [["a","b"],["c","d"]]中查询a / c，两端都存在但分属两个连通块，仍应返回-1.0。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 111. 除法求值 | 中等 | 同题换皮，可直接用带权并查集重写一遍 |
| 990. 等式方程的可满足性 | 中等 | 只有相等与不等，判定矛盾而不求值 |
| 547. 省份数量 | 中等 | 纯连通块计数，边不带权 |
| 684. 冗余连接 | 中等 | 用并查集在加边过程中找出成环的那条边 |
| 721. 账户合并 | 中等 | 字符串节点的连通块合并，重点在映射与结果整理 |
| 743. 网络延迟时间 | 中等 | 边权参与加法且需取最小，要用最短路而非任意路径 |