<i class="mobile-toggle" style="display:none;"><img src="https://img.dazhuanlan.com/2019/11/26/5ddcf6326f021.png"></i>
			<div class="content-article-box">
				<article class="article  article-post">

<div class="article-con">
    
    <h3 id="题目描述">

题目描述

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


</div>

<div class="article-navgition">
    <div class="navgition-wrap">
        
            <div class="navgition-prev">
                <h2 class="navgition-title">上一篇: <a href="http://shaocheng.me/2019/07/18/LeetCode-253-Meeting-Rooms-II/"> LeetCode 253. Meeting Rooms II </a>