0399：除法求值（★）

2016-02-03 约 896 字预计阅读 2 分钟次阅读

力扣第 399 题

题目

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

另有一些以数组 queries 表示的问题，其中 queries[j] = [C_j, D_j] 表示第 j 个问题，请你根据已知条件找出 C_j / D_j = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -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 <= A_i.length, B_i.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= C_j.length, D_j.length <= 5
A_i, B_i, C_j, D_j 由小写英文字母与数字组成

分析

#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

目录

0399：除法求值（★）

题目

分析

#1

#2

解答