除法求值
难度:
标签:
题目描述
给你一个变量对数组 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 的情况，且不存在任何矛盾的结果。
注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。
示例 1：
输入：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
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] 输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Dj由小写英文字母与数字组成
代码结果
运行时间: 20 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用并查集（Union-Find）数据结构来记录变量之间的关系。
* 2. 我们将每个变量表示为图中的节点，边的权重为它们的比值。
* 3. 对于每个查询，我们尝试在图中查找两个变量之间的路径，如果找不到则返回 -1.0。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
private class UnionFind {
private Map<String, String> parent;
private Map<String, Double> ratio;
public UnionFind() {
parent = new HashMap<>();
ratio = new HashMap<>();
}
public void union(String x, String y, double value) {
parent.putIfAbsent(x, x);
parent.putIfAbsent(y, y);
ratio.putIfAbsent(x, 1.0);
ratio.putIfAbsent(y, 1.0);
String rootX = find(x);
String rootY = find(y);
if (!rootX.equals(rootY)) {
parent.put(rootX, rootY);
ratio.put(rootX, value * ratio.get(y) / ratio.get(x));
}
}
public String find(String x) {
if (!x.equals(parent.get(x))) {
String originalParent = parent.get(x);
parent.put(x, find(parent.get(x)));
ratio.put(x, ratio.get(x) * ratio.get(originalParent));
}
return parent.get(x);
}
public Double isConnected(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 ratio.get(x) / ratio.get(y);
} else {
return -1.0;
}
}
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
UnionFind uf = new UnionFind();
IntStream.range(0, equations.size())
.forEach(i -> uf.union(equations.get(i).get(0), equations.get(i).get(1), values[i]));
return queries.stream()
.mapToDouble(q -> uf.isConnected(q.get(0), q.get(1)))
.toArray();
}
}
解释
方法:
这个题解基于图的广度优先搜索(BFS)算法。首先构建一个图，其中节点表示变量，边表示变量之间的除法关系。对于每个等式 a/b=v，添加一条从 a 到 b 的有向边，权重为 v，同时添加一条从 b 到 a 的反向边，权重为 1/v。对于每个查询 x/y，从 x 开始进行 BFS 搜索，同时记录路径上的权重乘积，直到找到 y 或搜索完整个连通分量。最后将搜索结果存入答案数组。
时间复杂度:
O(M*N)
空间复杂度:
O(N)
代码细节讲解
🦆
在构建图的过程中，为何每个变量对都需要添加反向边，并设置权重为原权重的倒数？
▷🦆
如何确保在BFS过程中，路径权重乘积的计算不会因浮点数精度问题而导致结果不准确？
▷🦆
在BFS搜索中使用了队列，为什么选择BFS而不是DFS？BFS在这种情况下有什么优势？
▷🦆
如果查询中的两个变量位于不同的连通分量，算法是如何处理这种情况？
▷