目录

0399:除法求值(★)

力扣第 399 题

题目

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi]values[i] 共同表示等式 Ai / Bi = values[i] 。每个 AiBi 是一个表示单个变量的字符串。

另有一些以数组 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 由小写英文字母与数字组成

相似问题:

分析

#1

  • 将等式看作边 (a, b),value 看作边的权重,反向边 (b, a) 的权重为 1/value
  • 问题就相当于找到从 c 到 d 在图中的路径,计算路径的权重乘积
  • 可以用 bfs/dfs 查找每个问题的路径
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def bfs(c,d):
            if c not in g or d not in g:
                return -1.0
            Q = deque([(1.0,c)])
            vis = {c}
            while Q:
                w,u = Q.popleft()
                if u==d:
                    return w
                for v,w2 in g[u]:
                    if v not in vis:
                        vis.add(v)
                        Q.append((w*w2,v))
            return -1.0
        g = defaultdict(list)
        for (a,b),w in zip(equations,values):
            g[a].append((b,w))
            g[b].append((a,1/w))
        return [bfs(c,d) for c,d in queries]

33 ms

#2

  • 更节省时间的做法是并查集
  • 每个节点维护到父节点的权重
  • 注意路径压缩和合并时都要同步更新

解答

 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
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def find(x):
            if f.setdefault(x,x)!=x:
                fx = find(f[x])
                g[x] *= g[f[x]]
                f[x] = fx 
            return f[x]
        
        def union(x,y,w):
            fx,fy = find(x),find(y)
            if fx!=fy:
                f[fx] = fy
                g[fx] = g[y]*w/g[x]

        f,g = {},defaultdict(lambda:1.0)
        for (a,b),w in zip(equations,values):
            union(a,b,w)
        res = []
        for c,d in queries:
            if c not in f or d not in f or find(c)!=find(d):
                res.append(-1)
            else:
                res.append(g[c]/g[d])
        return res