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.0Python解法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 # 手动执行两次findx、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 ansJava解法import java.util.*; class Solution { // parent: key节点, value父节点 MapString, String parent new HashMap(); // weight[x] x / parent[x] MapString, 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(ListListString equations, double[] values, ListListString 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_mapstring, string parent; // weight[x] x / parent[x] unordered_mapstring, 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]; } vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring 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]; } } vectordouble 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/bval先分别找到 a 的根 ra、b 的根 rb。如果两个根不相同说明属于两个独立集合需要合并。 我们约定把 ra 的父节点设置为 rb通过数学推导算出根之间的比值赋值给 weight [ra]保证所有原有等式关系保持成立。处理每一条查询 x/y 先判断 x 或者 y 从未出现直接返回 - 1.0 主动调用 find (x)、find (y)完成路径压缩、更新权重 如果二者根节点不相同变量之间不存在连通的除法关系返回 - 1.0 如果根相同weight [x]x/rootweight [y]y/root两者相除得到 x/y作为查询结果。核心逻辑总结连通代表可以互相推导除法find 实现路径压缩并维护节点到根的比值查询时依靠「节点到同一个根的权重相除」算出最终商。