399. 除法求值
给你一个变量对数组
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]
提示：
1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj由小写英文字母与数字组成
通过次数46,394提交次数78,439
法1 建图 + DFS
思路
参考剑指offer：专项突破版
将字母之间的关系建为图，然后在图上搜索路径
有向图采用字典建立
题解
class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: graph = self.buildGraph(equations, values) res = [-1 for _ in queries] for i in range(0, len(queries)): start, end = queries[i] if start not in graph or end not in graph: res[i] = -1 else: res[i] = self.dfs(start, end, graph, visited=set()) return res def dfs(self, start, end, graph, visited): # 返回从start 到 end 路径上的 权重乘积 if start == end: return 1.0 visited.add(start) for node, val in graph[start].items(): if node in visited: continue next_val = self.dfs(node, end, graph, visited) if next_val > 0: # -1 说明到不了 return next_val * val visited.remove(start) return -1 def buildGraph(self, equations, values): graph = {} for i in range(0, len(equations)): var1, var2 = equations[i] # 将键默认设置为 {} graph.setdefault(var1, {}) graph.setdefault(var2, {}) # 添加新的邻居节点 graph[var1].update({var2: values[i]}) graph[var2].update({var1: 1.0 / values[i]}) return graph
还有一种容易想到的
class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: res = [-1 for _ in queries] self.graph = collections.defaultdict(list) self.calc = {} for i in range(len(equations)): a, b = equations[i] self.graph[a].append(b) self.graph[b].append(a) self.calc[(a,b)] = values[i] self.calc[(b,a)] = 1/values[i] for i in range(0, len(queries)): start, end = queries[i] if start not in self.graph or end not in self.graph: continue temp = self.dfs(start, end, used=[start]) print(start, end, temp) res[i] = temp return res def dfs(self, start, end, used): if (start, end) in self.calc: return self.calc[(start, end)] for nxt in self.graph[start]: if nxt in used: continue used.append(nxt) temp = self.dfs(nxt, end, used) used.pop() if temp > 0: # 为了加速，将这个值存进去 self.graph[nxt].append(end) self.graph[end].append(nxt) self.calc[(nxt, end)] = temp self.calc[(end, nxt)] = 1/ temp return self.calc[(start, nxt)] * temp return -1