LeetCode 399. 除法求值：用图论思维解决变量关系问题

在实际开发和算法面试中，我们经常会遇到需要处理变量间关系的问题。LeetCode 399题“除法求值”就是一个典型的例子——它表面上看是一个数学问题，但本质上却是一个图论建模的经典案例。

🧩 题目回顾

给定：

equations[i] = [Ai, Bi] 表示变量对
values[i] 表示 Ai / Bi =values[i]
queries[j] = [Cj, Dj]表示要查询 Cj /Dj = ?

要求：

若能通过已知等式推导出结果，返回该值；
若变量未出现过，或无法推导，返回-1.0。

🔍 核心思想：把除法关系建模成图

关键洞察：
每个等式 A/ B = v 可以看作一条有向边：

从 A 到 B 的边权重为 v
从 B到 A 的边权重为1/v

这样，求 C /D 就变成了：在图中找从 C到 D 的路径，并将路径上所有边的权重相乘。

例如：

a / b= 2→ 边 a→b 权重 2，b→a权重 0.5
b / c= 3 →边 b→c权重 3，c→b 权重 1/3
求 a / c：路径 a→b→c，结果= 2 ×3 = 6

这就把一个代数问题转化为了图上的路径搜索问题！

✅ 解法一：DFS（深度优先搜索）

思路

构建邻接表表示图
对每个 query，从起点开始 DFS，记录当前累积的乘积
遇到终点就返回结果；若遍历完没找到，返回 -1

Java 实现

import java.util.*;

public class Solution {
   public double[] calcEquation(List<List<String>> equations, 
                               double[] values, 
                               List<List<String>> queries) {
      // 1.构建图（邻接表）
       Map<String, Map<String, Double>> graph = new HashMap<>();
       
       for (int i = 0;i < equations.size(); i++) {
           String u = equations.get(i).get(0);
           String v = equations.get(i).get(1);
           double val = values[i];
           
           graph.computeIfAbsent(u, k ->new HashMap<>()).put(v, val);
           graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / val);
      }
       
       // 2. 处理每个查询
       double[] res= new double[queries.size()];
       for (int i = 0;i < queries.size(); i++) {
           String start= queries.get(i).get(0);
           String end= queries.get(i).get(1);
           
           if(!graph.containsKey(start) || !graph.containsKey(end)) {
               res[i]= -1.0;
           } else if(start.equals(end)) {
               res[i] = 1.0;
           }else {
               Set<String> visited = new HashSet<>();
               res[i] = dfs(graph, start,end, visited);
           }
       }
      return res;
   }
   
   private double dfs(Map<String, Map<String, Double>> graph, 
                    String cur, String target, Set<String> visited){
       if (cur.equals(target)) return 1.0;
      visited.add(cur);
       
      Map<String, Double> neighbors = graph.get(cur);
       for (String next : neighbors.keySet()) {
           if (visited.contains(next)) continue;
           
           double subResult = dfs(graph, next, target,visited);
           if (subResult != -1.0) {
               return neighbors.get(next) * subResult;
           }
       }
       return -1.0;
   }
}

时间复杂度

建图：O(E)
每次查询最坏 O(V + E)，共 Q 次 →O(Q ×(V + E))

✅ 解法二：BFS（广度优先搜索）

思路

同样建图

对每个 query 使用 BFS找最短路径（其实任意路径都行，因为题目保证无矛盾）
队列中存储 (当前节点,当前累积值)

Java 实现（关键部分）

private double bfs(Map<String, Map<String, Double>> graph,String start, String end) {
   Queue<Pair<String, Double>>queue = new LinkedList<>();
   Set<String> visited= new HashSet<>();
   
   queue.offer(new Pair<>(start, 1.0));
   visited.add(start);
   
   while(!queue.isEmpty()) {
      Pair<String, Double> cur = queue.poll();
       String node = cur.getKey();
       double val = cur.getValue();
       
       if (node.equals(end)) return val;
       
       for (Map.Entry<String, Double> neighbor: graph.get(node).entrySet()) {
           String next= neighbor.getKey();
           double weight = neighbor.getValue();
           if (!visited.contains(next)) {
              visited.add(next);
               queue.offer(new Pair<>(next,val * weight));
           }
       }
   }
   return -1.0;
}

注：Java 中可自定义 Pair 或使用 AbstractMap.SimpleEntry

BFS 和 DFS 在本题中效果相当，但 BFS 更适合找“最短路径”（虽然这里路径唯一性由题目保证）。

✅ 解法三：带权并查集（Union-Find with Weights）

高阶思路

并查集通常用于判断连通性，但我们可以扩展它来维护相对权重。

每个节点 x维护：

parent[x]：父节点
weight[x]：表示 x /parent[x]的值

当合并两个集合时，根据已知等式更新权重。

查询时，通过路径压缩同时更新权重，最终得到 x /root 和 y/ root，从而计算x / y =(x/root) / (y/root)。

Java实现（精简版）

class UnionFind {
   Map<String, String> parent = new HashMap<>();
   Map<String, Double> weight = new HashMap<>(); // x / parent[x]

   public void add(String x) {
      if (!parent.containsKey(x)) {
           parent.put(x, x);
           weight.put(x, 1.0);
       }
   }

  public String find(String x) {
       if (!parent.get(x).equals(x)) {
           String origin = parent.get(x);
           String root = find(origin);
           //路径压缩 +权重更新
           parent.put(x,root);
           weight.put(x, weight.get(x)* weight.get(origin));
       }
       return parent.get(x);
   }

  public void union(String x, String y, double value) {
       add(x); add(y);
       String rootX = find(x);
       String rootY= find(y);
       if(!rootX.equals(rootY)) {
          parent.put(rootX, rootY);
           //weight[rootX] =(y / rootY) / (x /rootX) * value
           // 因为 x/ y = value =>x = value * y
           // x / rootX= w[x], y /rootY = w[y]
           // 所以 rootX / rootY =(x / w[x]) / (y /w[y]) = (value* y / w[x])/ (y / w[y]) = value * w[y] / w[x]
          // 但我们存的是 rootX / parent[rootX] = rootX/ rootY
           weight.put(rootX,weight.get(y) * value/ weight.get(x));
       }
   }

  public double query(String x, String y) {
       if (!parent.containsKey(x) || !parent.containsKey(y)) return -1.0;
       String rootX =find(x);
       String rootY = find(y);
      if (!rootX.equals(rootY)) return -1.0;
       return weight.get(x) / weight.get(y);
   }
}

// 主函数调用
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
   UnionFind uf =new UnionFind();
   for(int i = 0; i < equations.size();i++) {
       uf.union(equations.get(i).get(0),equations.get(i).get(1), values[i]);
  }
   double[] res =new double[queries.size()];
   for (int i =0; i < queries.size(); i++) {
      res[i] = uf.query(queries.get(i).get(0), queries.get(i).get(1));
  }
   return res;
}

优势

预处理后，每次查询接近 O(α(n))（阿克曼反函数，近乎常数）
适合大量查询的场景

📊 三种解法对比

方法	预处理时间	单次查询时间	空间	适用场景
DFS	O(E)	O(V+E)	O(V+E)	查询少，实现简单
BFS	O(E)	O(V+E)	O(V+E)	同上，避免递归栈溢出
并查集	O(E α(V))	O(α(V))	O(V)	大量查询，性能最优

💡 总结

LeetCode 399 题教会我们一个重要思维转换：

不要只看到“除法”，而要看到“关系图”。

通过将代数关系转化为图结构，我们就能用图论的标准工具（DFS/BFS）解决问题。而进一步使用带权并查集，则体现了数据结构设计的巧妙性——在维护连通性的同时，还能携带额外信息（权重）。

这种“建模能力”正是算法高手与普通程序员的分水岭。下次遇到类似“变量间传递关系”的问题，不妨先问自己：能不能画成一张图？