题目描述
给你一个变量对数组 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]
思路
有向权重图+dfs
参考：399.Evaluate Division除法求值【LeetCode单题讲解系列】_哔哩哔哩_bilibili这个视频讲解的很清楚
1）先通过defaultdict创建一个图，a/b=v，b/a=1/v，都保存到字典中
2）遍历queries，创建一个数组，用来记录当前元素是否遍历过【因为尾是一样的，头在遍历，没有意义】
3）dfs函数：visited加入当前头元素；终止条件：如果当前节点没在图中，则返回-1；如果当前节点和结尾节点一样【说明a/a】返回1
3.1）遍历图中该节点的连接点，如果等于尾节点，则返回当前权重；如果不等于，则dfs深度优先遍历，当前节点和尾节点，找到其关系。
3.2）如果找到的权重值不为-1，则相乘，否则返回-1
4）用一个res保存每轮返回的结果
from collections import defaultdict
class Solution(object):
def dfs(self, start, end, visited, graph):
visited.append(start)
if start not in graph:
return -1
if start==end:
return 1
for i in graph[start]:
if i == end:
return graph[start][end]
elif i not in visited:
v = self.dfs(i,end,visited,graph)
if v!=-1:
return graph[start][i]*v
return -1
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
graph = defaultdict(dict)
for (x,y), v in zip(equations, values):
graph[x][y] = v
graph[y][x] = 1/v
res = []
for s,e in queries:
visited = []
res.append(self.dfs(s,e,visited,graph))
return res
if __name__=='__main__':
s=Solution()
equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"],["a", "a"], ["x", "x"]]
print(s.calcEquation(equations, values, queries))