LeetCode 399. 除法求值

LeetCode 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 ]
注意：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 <= 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 由小写英文字母与数字组成

干了一天

class Solution:def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:vars = {}for x, y in equations:if x not in vars:vars[x] = len(vars)if y not in vars:vars[y] = len(vars)graph = [[None] * len(vars) for _ in range(len(vars))]print(vars)from decimal import Decimalfor i in range(len(equations)):x, y = equations[i]graph[vars[x]][vars[y]] = Decimal(values[i])graph[vars[y]][vars[x]] = Decimal(1) / Decimal(values[i])for k in range(len(vars)):for i in range(len(var s)):for j in range(len(vars)):if graph[i][k] and graph[k][j]:   # and not graph[i][j]  评论区有提到加上这个条件可以恰好避免卡精度，我使用decimal彻底解决该问题graph[i][j] = graph[i][k] * graph[k][j];  # 由于题目特殊性，此处相比弗洛伊德算法可以进行简化res = []for x, y in queries:if x not in vars or y not in vars:res.append(-1)elif x == y:res.append(1)elif graph[vars[x]][vars[y]]:res.append(graph[vars[x]][vars[y]])else:res.append(-1)return res

来看看我在评论区找到的大佬的解法

# DFSdef calcEquation(self, equations, values, queries):""":type equations: List[List[str]]:type values: List[float]:type queries: List[List[str]]:rtype: List[float]"""from collections import defaultdictgraph = defaultdict(set)weight = defaultdict()lookup = {}# 建图for idx, equ in enumerate(equations):graph[equ[0]].add(equ[1])graph[equ[1]].add(equ[0])weight[tuple(equ)] = values[idx]weight[(equ[1], equ[0])] = float(1 / values[idx])# 深度遍历(DFS)def dfs(start, end, vistied):# 当图中有此边,直接输出if (start, end) in weight:return weight[(start, end)]# 图中没有这个点if start not in graph or end not in graph:return 0# 已经访问过if start in vistied:return 0vistied.add(start)res = 0for tmp in graph[start]:res = (dfs(tmp, end, vistied) * weight[(start, tmp)])# 只要遍历到有一个不是0的解就跳出if res != 0:# 添加此边,以后访问节省时间weight[(start, end)] = resbreakvistied.remove(start)return resres = []for que in queries:# 用集合记录是否已经访问节点tmp = dfs(que[0], que[1], set())if tmp == 0:tmp = -1.0res.append(tmp)return res
# BFSdef calcEquation(self, equations, values, queries):from collections import defaultdict, dequegraph = defaultdict(set)weight = defaultdict()lookup = {}# 建图for idx, equ in enumerate(equations):graph[equ[0]].add(equ[1])graph[equ[1]].add(equ[0])weight[tuple(equ)] = values[idx]weight[(equ[1], equ[0])] = float(1 / values[idx])res = []for start, end in queries:if (start, end) in weight:res.append(weight[(start, end)])continueif start not in graph or end not in graph:res.append(-1)continueif start == end:res.append(1.0)continuestack = deque()# 将从start点可以到达下一个节点压入栈内for tmp in graph[start]:stack.appendleft((tmp, weight[(start, tmp)]))# 记录访问节点visited = {start}# 为了跳出双循环flag = Falsewhile stack:c, w = stack.pop()if c == end:flag = Trueres.append(w)breakvisited.add(c)for n in graph[c]:if n not in visited:weight[(start, n)] = w * weight[(c, n)]stack.appendleft((n, w * weight[(c, n)]))if flag:continueres.append(-1.0)return res

另外一个更加精简的dfs

class Solution:def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:graph=defaultdict(dict)for (a,b),v in zip(equations,values):graph[a][b]=vgraph[b][a]=1/vdef dfs(s,e):if s not in graph or e not in graph:return -1if s==e:return 1visited.add(s)for i in graph[s]:if i==e:return graph[s][i]if i not in visited:ans=dfs(i,e)if ans!=-1:return graph[s][i]*ansreturn -1res=[]for a,b in queries:visited=set()res.append(dfs(a,b))return res