LeetCode 399. Evaluate Division  

题目描述

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

[](http://shaocheng.me/#%E5%B9%B6%E6%9F%A5%E9%9B%86-O “(并查集)

O()”)(并查集) 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  

—|—

上一篇: [ LeetCode 253. Meeting Rooms II

](http://shaocheng.me/2019/07/18/LeetCode-253-Meeting-Rooms-II/)

下一篇: [LeetCode 494. Target Sum

](http://shaocheng.me/2019/07/18/LeetCode-494-Target-Sum/)

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017