计算除法
# 📃 题目描述
题目链接:
- 剑指 Offer II 111. 计算除法 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 399. 除法求值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个变量对数组 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 ]
示例 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]
# 🔔 解题思路
用邻接表构造有向图,比如 a/b = 2.0,那么就构造两个节点 a 和 b,以及 a 指向 b 的这条边权重为 2.0

HashMap 的键是图中的节点(对应一个变量,是有向边的起始节点),值是与该节点相连的其他节点。与一个节点相连的其他节点也用 HashMap 表示,它的键是图中的节点(对应一个变量,是有向边的终止节点),值是边的权重(也就是两个变量进行除法运算得到的商)。
其中,DFS 直接套模板即可
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
// 构建有向图邻接表 key: 图中的节点,value(map):key 与之相邻的节点、value(权值): a/b 的值
Map<String, Map<String, Double>> graph = buildGraph(equations, values);
double[] res = new double[queries.size()];
// 遍历处理 queries
for (int i = 0; i < queries.size(); i ++) {
List<String> item = queries.get(i);
String source = item.get(0);
String end = item.get(1);
// 表示每个节点是否访问过
Set<String> visited = new HashSet<>();
// res[i] = source/end
res[i] = dfs(source, end, graph, visited);
}
return res;
}
// 返回 source -> end 这条边上的权值
private double dfs(String source, String end, Map<String, Map<String, Double>> graph, Set<String> visited) {
if (!graph.containsKey(source) || !graph.containsKey(end)) {
return -1.0;
}
if (source.equals(end)) {
return 1.0;
}
// 访问 source
visited.add(source);
Map<String, Double> map = graph.get(source);
// dfs 与 source 相邻的所有节点(有向图)
for (String neighboor : map.keySet()) {
if (!visited.contains(neighboor)) {
// neighboor -> end 这条边上的权值
double neighboorValue = dfs(neighboor, end, graph, visited);
if (neighboorValue > 0) {
// source -> end 这条边上的权值 = source -> neighboor 这条边上的权值 * neighboor -> end 这条边上的权值
return map.get(neighboor) * neighboorValue;
}
}
}
return -1.0;
}
// 构建有向图邻接表 key: 图中的节点,value(map):key 与之相邻的节点、value(权值): a/b 的值
private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
Map<String, Map<String, Double>> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i ++) {
List<String> item = equations.get(i);
double value = values[i];
// source -> end
graph.putIfAbsent(item.get(0), new HashMap<>());
graph.get(item.get(0)).put(item.get(1), value);
// end -> source
graph.putIfAbsent(item.get(1), new HashMap<>());
graph.get(item.get(1)).put(item.get(0), 1.0 / value);
}
return graph;
}
}
画个图配合理解:
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10