LeetCode 399. Evaluate Division

topic
2.2k 词

题目描述

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

tag

DFS BFS 图 并查集

样例

1
2
3
4
5
6
7
8
9
10
11
12
示例 :
给定 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 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

算法1

(DFS) O()
思路

先构造图，使用dict实现，其天然的hash可以在in判断时做到O(1)复杂度。

对每个equation如”a/b=v”构造a到b的带权v的有向边和b到a的带权1/v的有向边，

之后对每个query，只需要进行dfs并将路径上的边权重叠乘就是结果了，如果路径不可达则结果为-1。

复杂度分析：
python 代码
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class :
    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):
            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
            if t == s:
                return 1
            for node in graph[s].keys():
                if node == t:
                    return graph[s][node]
                elif node not in visited:
                    visited.add(node) 
                    v = _dfs(node, t)
                    if v != -1:
                        return graph[s][node] * v
            return -1

        res = []
        for qs, qt in queries:
            visited = set()
            res.append(_dfs(qs, qt))
        return res

先构造图，使用dict实现，其天然的hash可以在in判断时做到O(1)复杂度。

对每个equation如"a/b=v"构造a到b的带权v的有向边和b到a的带权1/v的有向边，

之后对每个query，只需要进行dfs并将路径上的边权重叠乘就是结果了，如果路径不可达则结果为-1。

作者：mai-mai-mai-mai-zi
链接：https://leetcode-cn.com/problems/two-sum/solution/xian-gou-zao-tu-zai-dfsde-pythonshi-xian-by-mai-ma/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法2

(BFS) O()
思路

https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion

复杂度分析：
python 代码
1
2


算法3

(并查集) O()
思路

https://leetcode.com/problems/evaluate-division/discuss/162493/Python-Union-Find-Solution

https://leetcode.com/problems/evaluate-division/discuss/270993/Python-BFS-and-UF(detailed-explanation))

复杂度分析：
python 代码
1
2