老卫带你学---leetcode刷题(399. 除法求值)

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
1
2
3
4
5
6
7
8
9

示例 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]
1
2
3
4

示例 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
2
3
4

提示：

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 由小写英文字母与数字组成
1
2
3
4
5
6
7
8
9
10
11

解决：

• 建立graph来保留相除的结果
• dfs搜索

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
      graph={}
      for (x,y),v in zip(equations,values): ## 建议graph便于后期直接O（1）查找value
        if x in graph:
          graph[x][y]=v
        else:
          graph[x]={y:v}
        if y in graph:
          graph[y][x]=1/v
        else:
          graph[y]={x:1/v}
      
      def dfs(s,t):
        if s not in graph:
          return -1 ##未graph过，-1
        if t==s:
          return 1 ##相等，相除为1
        for node in graph[s].keys():
          if node ==t:
            return graph[s][node] ## 如果之前已经graph了，直接输出
          elif node not in visited:
            visited.add(node) # 添加到已访问避免后续dfs重复遍历
            v=dfs(node,t) ## 这里是一种核心情况，比如有（a，b）（b，c）要求（a，c）就需要深度遍历
            if v!=-1:
              return graph[s][node]*v
        return -1
      res=[]
      for s,t in queries:
        visited=set()
        res.append(dfs(s,t))
      return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32