DeepSeek LeetCode 399. 除法求值 Java实现

发布时间：2026/10/24 2:24:32
DeepSeek LeetCode 399. 除法求值 Java实现

LeetCode 399. 除法求值

题目描述

给出方程式 A / B = k，其中 A 和 B 均为代表字符串的变量，k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例：给定 a / b = 2.0, b / c = 3.0，问题 a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?，返回 [6.0, 0.5, -1.0, 1.0, -1.0]。

思路：构建带权有向图

把每个变量看作图的节点，A / B = k 表示：

· 边 A → B，权重 k
· 边 B → A，权重 1/k

对每个查询 (x, y)，只需在图中从 x 找到 y 的一条路径，把路径上所有边的权重累乘即为答案；若 x 或 y 不在图中，或两者不连通，返回 -1.0。

解法一：DFS（推荐，简洁）

classSolution{publicdouble[]calcEquation(List<List<String>>equations,double[]values,List<List<String>>queries){// 构建带权图：a -> {b: v}, b -> {a: 1/v}Map<String,Map<String,Double>>graph=newHashMap<>();for(inti=0;i<equations.size();i++){Stringa=equations.get(i).get(0);Stringb=equations.get(i).get(1);doublev=values[i];graph.computeIfAbsent(a,k->newHashMap<>()).put(b,v);graph.computeIfAbsent(b,k->newHashMap<>()).put(a,1.0/v);}double[]res=newdouble[queries.size()];for(inti=0;i<queries.size();i++){Stringa=queries.get(i).get(0);Stringb=queries.get(i).get(1);if(!graph.containsKey(a)||!graph.containsKey(b)){res[i]=-1.0;continue;}Doubleans=dfs(graph,a,b,newHashSet<>());res[i]=(ans==null)?-1.0:ans;}returnres;}// 返回 cur -> target 的累乘值；不可达返回 null（用 null 避免与真实结果 -1.0 混淆）privateDoubledfs(Map<String,Map<String,Double>>graph,Stringcur,Stringtarget,Set<String>visited){if(cur.equals(target))return1.0;visited.add(cur);for(Map.Entry<String,Double>e:graph.get(cur).entrySet()){Stringnext=e.getKey();if(visited.contains(next))continue;Doublerest=dfs(graph,next,target,visited);if(rest!=null){returne.getValue()*rest;}}returnnull;}}

注意：这里用 Double 的 null 表示"不可达"，而不是用 -1.0，因为除法结果完全可能恰好等于 -1.0，两者会冲突。

解法二：BFS（避免递归栈溢出）

classSolution{publicdouble[]calcEquation(List<List<String>>equations,double[]values,List<List<String>>queries){Map<String,Map<String,Double>>graph=newHashMap<>();for(inti=0;i<equations.size();i++){Stringa=equations.get(i).get(0);Stringb=equations.get(i).get(1);doublev=values[i];graph.computeIfAbsent(a,k->newHashMap<>()).put(b,v);graph.computeIfAbsent(b,k->newHashMap<>()).put(a,1.0/v);}double[]res=newdouble[queries.size()];for(inti=0;i<queries.size();i++){Stringa=queries.get(i).get(0);Stringb=queries.get(i).get(1);if(!graph.containsKey(a)||!graph.containsKey(b)){res[i]=-1.0;continue;}res[i]=bfs(graph,a,b);}returnres;}privatedoublebfs(Map<String,Map<String,Double>>graph,Stringsrc,Stringdst){// 队列存 [节点, 从 src 到该节点的累乘值]Deque<Object[]>queue=newArrayDeque<>();Set<String>visited=newHashSet<>();queue.offer(newObject[]{src,1.0});visited.add(src);while(!queue.isEmpty()){Object[]cur=queue.poll();Stringnode=(String)cur[0];doubleval=(Double)cur[1];if(node.equals(dst))returnval;for(Map.Entry<String,Double>e:graph.get(node).entrySet()){if(visited.contains(e.getKey()))continue;visited.add(e.getKey());queue.offer(newObject[]{e.getKey(),val*e.getValue()});}}return-1.0;}}

解法三：带权并查集（多次查询更优）

核心定义：parent[x] 为 x 的根，weight[x] = x / parent[x]（x 到根的比值）。路径压缩时同步累乘权重。

classSolution{privateMap<String,String>parent=newHashMap<>();privateMap<String,Double>weight=newHashMap<>();// weight[x] = x / parent[x]publicdouble[]calcEquation(List<List<String>>equations,double[]values,List<List<String>>queries){// 初始化：每个变量自成一棵树for(List<String>eq:equations){parent.putIfAbsent(eq.get(0),eq.get(0));parent.putIfAbsent(eq.get(1),eq.get(1));weight.putIfAbsent(eq.get(0),1.0);weight.putIfAbsent(eq.get(1),1.0);}// 合并for(inti=0;i<equations.size();i++){union(equations.get(i).get(0),equations.get(i).get(1),values[i]);}// 查询double[]res=newdouble[queries.size()];for(inti=0;i<queries.size();i++){Stringa=queries.get(i).get(0);Stringb=queries.get(i).get(1);if(!parent.containsKey(a)||!parent.containsKey(b)){res[i]=-1.0;continue;}Stringra=find(a);Stringrb=find(b);res[i]=ra.equals(rb)?weight.get(a)/weight.get(b):-1.0;}returnres;}// 查找根 + 路径压缩，同时更新 weight[x] = x / rootprivateStringfind(Stringx){if(!parent.get(x).equals(x)){Stringp=parent.get(x);// 原来的直接父节点Stringroot=find(p);// 递归压缩，p 的 weight 变为 p / rootweight.put(x,weight.get(x)*weight.get(p));// x/root = (x/p) * (p/root)parent.put(x,root);}returnparent.get(x);}// 合并：已知 a / b = vprivatevoidunion(Stringa,Stringb,doublev){Stringra=find(a);Stringrb=find(b);if(ra.equals(rb))return;// a = weight[a] * ra, b = weight[b] * rb// a/b = v => ra/rb = v * weight[b] / weight[a]weight.put(ra,v*weight.get(b)/weight.get(a));parent.put(ra,rb);}}

复杂度对比

解法 构建 单次查询 适用场景
DFS O(E) O(V + E) 查询少、图不深，代码最简洁
BFS O(E) O(V + E) 图较深、递归可能栈溢出
带权并查集 O(E·α(V)) O(α(V)) 查询很多，性能最优

关键点提醒：

  1. 用 null 而非 -1.0 表示"不可达"，避免与真实结果 -1.0 冲突。
  2. 变量可能不出现在 equations 中，需要先判断 graph.containsKey(…)。
  3. 图中可能有多个连通分量，x 和 y 不连通时返回 -1.0。
  4. 并查集 find 中必须先取原父节点 p 再递归，否则权重累乘会错。