题目描述

给出方程式 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