LeetCode 399：除法求值高效解法-平芜编程栈

LeetCode399

给你一个变量对数组equations和一个实数值数组values作为已知条件，其中equations[i] = [Ai, Bi]和values[i]共同表示等式Ai / Bi = values[i]。每个Ai或Bi是一个表示单个变量的字符串。

另有一些以数组queries表示的问题，其中queries[j] = [Cj, Dj]表示第j个问题，请你根据已知条件找出Cj / Dj = ?的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用-1.0替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用-1.0替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：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 ]
注意：x 是未定义的 => -1.0

Python解法

class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # parent[x]：记录节点x的父节点 parent = dict() # weight[x] 固定定义： weight[x] = x / parent[x] weight = dict() def find(x): """ 查找x的根节点，附带【路径压缩】 递归回溯时更新权重，使 weight[x] = x / root（根节点） """ # 如果当前节点的父节点不是自己，说明不是根 if parent[x] != x: orig_father = parent[x] # 先保存原始父节点 root = find(parent[x]) # 递归找到父节点的根，同时父节点完成路径压缩 # 公式：x/root = (x / orig_father) * (orig_father / root) weight[x] *= weight[orig_father] # 路径压缩：x 直接指向根节点 parent[x] = root return parent[x] # 遍历所有等式，构建带权并查集 # 示例一组等式：a / b = 2.0 for (a, b), val in zip(equations, values): # 节点第一次出现：初始化，自己指向自己，自己÷自己=1 if a not in parent: parent[a] = a weight[a] = 1.0 if b not in parent: parent[b] = b weight[b] = 1.0 # 找到a、b各自的根（自动路径压缩、更新权重） ra = find(a) rb = find(b) # 两个节点根不一样 → 两个连通块，需要合并 if ra != rb: # 约定：把 ra 的父节点设置为 rb parent[ra] = rb # 数学推导得出： weight[ra] = ra / rb # a/b = val , weight[a]=a/ra , weight[b]=b/rb weight[ra] = val * weight[b] / weight[a] ans = [] # 处理所有查询【修复版本：提前对x,y都执行find，保证权重更新完成】 for x, y in queries: # 变量从未出现，直接无解 if x not in parent or y not in parent: ans.append(-1.0) continue # 手动执行两次find，x、y全部路径压缩，权重更新为 节点/根 rx = find(x) ry = find(y) # 根不相同，不在同一连通分量 if rx != ry: ans.append(-1.0) else: # weight[x] = x/root , weight[y] = y/root # x/y = (x/root) / (y/root) ans.append(weight[x] / weight[y]) return ans

Java解法

import java.util.*; class Solution { // parent: key=节点, value=父节点 Map<String, String> parent = new HashMap<>(); // weight[x] = x / parent[x] Map<String, Double> weight = new HashMap<>(); // 查找 + 路径压缩 private String find(String x) { if (!parent.get(x).equals(x)) { String origFather = parent.get(x); String root = find(parent.get(x)); // 更新权重 x/root = (x/origFather) * (origFather/root) weight.put(x, weight.get(x) * weight.get(origFather)); // 路径压缩，直接指向根 parent.put(x, root); } return parent.get(x); } public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { // 初始化所有节点 for (int i = 0; i < equations.size(); i++) { String a = equations.get(i).get(0); String b = equations.get(i).get(1); double val = values[i]; if (!parent.containsKey(a)) { parent.put(a, a); weight.put(a, 1.0); } if (!parent.containsKey(b)) { parent.put(b, b); weight.put(b, 1.0); } String ra = find(a); String rb = find(b); if (!ra.equals(rb)) { parent.put(ra, rb); weight.put(ra, val * weight.get(b) / weight.get(a)); } } double[] res = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { String x = queries.get(i).get(0); String y = queries.get(i).get(1); // 节点不存在 if (!parent.containsKey(x) || !parent.containsKey(y)) { res[i] = -1.0; continue; } String rx = find(x); String ry = find(y); if (!rx.equals(ry)) { res[i] = -1.0; } else { res[i] = weight.get(x) / weight.get(y); } } return res; } }

C++解法

#include <vector> #include <unordered_map> #include <string> using namespace std; class Solution { public: unordered_map<string, string> parent; // weight[x] = x / parent[x] unordered_map<string, double> weight; string find(string x) { if (parent[x] != x) { string origFather = parent[x]; string root = find(parent[x]); weight[x] *= weight[origFather]; parent[x] = root; } return parent[x]; } vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { // 构建并查集 for (int i = 0; i < equations.size(); ++i) { string a = equations[i][0]; string b = equations[i][1]; double val = values[i]; if (!parent.count(a)) { parent[a] = a; weight[a] = 1.0; } if (!parent.count(b)) { parent[b] = b; weight[b] = 1.0; } string ra = find(a); string rb = find(b); if (ra != rb) { parent[ra] = rb; weight[ra] = val * weight[b] / weight[a]; } } vector<double> ans; for (auto& q : queries) { string x = q[0]; string y = q[1]; if (!parent.count(x) || !parent.count(y)) { ans.push_back(-1.0); continue; } string rx = find(x); string ry = find(y); if (rx != ry) { ans.push_back(-1.0); } else { ans.push_back(weight[x] / weight[y]); } } return ans; } };

总体思路

本题使用带权并查集解决变量除法传递计算问题。我们把每个变量当作图中的节点，等式 a/b = value 代表节点之间存在带权关系：a 与 b 连通，权重代表二者比值。约定规则：weight [x] = x /parent [x]，也就是节点 x 除以它的父节点等于 weight [x]。

初始化节点遍历所有等式，遇到从未出现的变量，将它加入并查集：自己作为自己的父节点，权重设置为 1.0，因为变量除以自身等于 1。
查找函数 find（核心，附带路径压缩）查找节点 x 的根节点。如果 x 的父节点不是根，先递归找到父节点对应的根；递归返回后更新 x 的权重：新权重等于原权重乘以原父节点的权重，代表 x / 根节点；再修改 x 的父节点直接指向根，完成路径压缩。路径压缩目的：扁平化树结构，同时保证调用 find 后，weight [x] 恒等于 x / 根节点。
合并两个连通块对于等式 a/b=val，先分别找到 a 的根 ra、b 的根 rb。如果两个根不相同，说明属于两个独立集合，需要合并。我们约定把 ra 的父节点设置为 rb，通过数学推导算出根之间的比值，赋值给 weight [ra]，保证所有原有等式关系保持成立。
处理每一条查询 x/y 先判断 x 或者 y 从未出现，直接返回 - 1.0；主动调用 find (x)、find (y)，完成路径压缩、更新权重；如果二者根节点不相同，变量之间不存在连通的除法关系，返回 - 1.0；如果根相同，weight [x]=x/root，weight [y]=y/root，两者相除得到 x/y，作为查询结果。