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(ListListStringequations,double[]values,ListListStringqueries){// 构建带权图a - {b: v}, b - {a: 1/v}MapString,MapString,DoublegraphnewHashMap();for(inti0;iequations.size();i){Stringaequations.get(i).get(0);Stringbequations.get(i).get(1);doublevvalues[i];graph.computeIfAbsent(a,k-newHashMap()).put(b,v);graph.computeIfAbsent(b,k-newHashMap()).put(a,1.0/v);}double[]resnewdouble[queries.size()];for(inti0;iqueries.size();i){Stringaqueries.get(i).get(0);Stringbqueries.get(i).get(1);if(!graph.containsKey(a)||!graph.containsKey(b)){res[i]-1.0;continue;}Doubleansdfs(graph,a,b,newHashSet());res[i](ansnull)?-1.0:ans;}returnres;}// 返回 cur - target 的累乘值不可达返回 null用 null 避免与真实结果 -1.0 混淆privateDoubledfs(MapString,MapString,Doublegraph,Stringcur,Stringtarget,SetStringvisited){if(cur.equals(target))return1.0;visited.add(cur);for(Map.EntryString,Doublee:graph.get(cur).entrySet()){Stringnexte.getKey();if(visited.contains(next))continue;Doublerestdfs(graph,next,target,visited);if(rest!null){returne.getValue()*rest;}}returnnull;}}注意这里用 Double 的 null 表示不可达而不是用 -1.0因为除法结果完全可能恰好等于 -1.0两者会冲突。解法二BFS避免递归栈溢出classSolution{publicdouble[]calcEquation(ListListStringequations,double[]values,ListListStringqueries){MapString,MapString,DoublegraphnewHashMap();for(inti0;iequations.size();i){Stringaequations.get(i).get(0);Stringbequations.get(i).get(1);doublevvalues[i];graph.computeIfAbsent(a,k-newHashMap()).put(b,v);graph.computeIfAbsent(b,k-newHashMap()).put(a,1.0/v);}double[]resnewdouble[queries.size()];for(inti0;iqueries.size();i){Stringaqueries.get(i).get(0);Stringbqueries.get(i).get(1);if(!graph.containsKey(a)||!graph.containsKey(b)){res[i]-1.0;continue;}res[i]bfs(graph,a,b);}returnres;}privatedoublebfs(MapString,MapString,Doublegraph,Stringsrc,Stringdst){// 队列存 [节点, 从 src 到该节点的累乘值]DequeObject[]queuenewArrayDeque();SetStringvisitednewHashSet();queue.offer(newObject[]{src,1.0});visited.add(src);while(!queue.isEmpty()){Object[]curqueue.poll();Stringnode(String)cur[0];doubleval(Double)cur[1];if(node.equals(dst))returnval;for(Map.EntryString,Doublee: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{privateMapString,StringparentnewHashMap();privateMapString,DoubleweightnewHashMap();// weight[x] x / parent[x]publicdouble[]calcEquation(ListListStringequations,double[]values,ListListStringqueries){// 初始化每个变量自成一棵树for(ListStringeq: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(inti0;iequations.size();i){union(equations.get(i).get(0),equations.get(i).get(1),values[i]);}// 查询double[]resnewdouble[queries.size()];for(inti0;iqueries.size();i){Stringaqueries.get(i).get(0);Stringbqueries.get(i).get(1);if(!parent.containsKey(a)||!parent.containsKey(b)){res[i]-1.0;continue;}Stringrafind(a);Stringrbfind(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)){Stringpparent.get(x);// 原来的直接父节点Stringrootfind(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){Stringrafind(a);Stringrbfind(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)) 查询很多性能最优关键点提醒用 null 而非 -1.0 表示不可达避免与真实结果 -1.0 冲突。变量可能不出现在 equations 中需要先判断 graph.containsKey(…)。图中可能有多个连通分量x 和 y 不连通时返回 -1.0。并查集 find 中必须先取原父节点 p 再递归否则权重累乘会错。
