leetcode回顾——[384] Shuffle an Array

LeetCode

题目

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

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

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

equations(方程式) = [ [“a”, “b”], [“b”, “c”] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

题解

将题目给的数据转为有向带权图，假设a与b有一关系a / b = 2.0，那么该图有a、b两个点，方向为a -> b，这条边的权值为a / b的值，同理，既然有a / b，那么也有b / a，这样图又多了一条边

1
2
3
4
5
6

-----      2.0     -----      3.0      -----
|   |------------->|   |-------------->|   |
| A |              | B |               | C |
|   |<-------------|   |<--------------|   |
-----      0.5     -----    0.33...    -----

AC代码

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
class Solution(object):
    def calcEquation(self, equations, values, queries):
        from collections import defaultdict
        self.graph = defaultdict(set)
        self.weight = defaultdict()
        for idx, equ in enumerate(equations):
            self.graph[equ[0]].add(equ[1])
            self.graph[equ[1]].add(equ[0])
            self.weight[tuple(equ)] = values[idx]
            self.weight[(equ[1], equ[0])] = 1 / values[idx]
        res = []
        for que in queries:
            t = self.dfs(start=que[0], end=que[1], visited=set())
            if t == 0:
                t = -1.0
            res.append(t)
        return res

    def dfs(self, start, end, visited):
        if (start, end) in self.weight:
            return self.weight[(start, end)]
        if start not in self.graph or end not in self.graph:
            return 0
        if start in visited:
            return 0
        visited.add(start)
        res = 0
        for tmp in self.graph[start]:
            res = (self.dfs(tmp, end, visited) * self.weight[(start, tmp)])
            if res != 0:
                self.weight[(start, end)] = res
                break
        visited.remove(start)
        return res

if __name__ == '__main__':
    s = Solution()
    equations = [["a","e"],["b","e"]]
    values = [4.0,3.0]
    queries = [["a","b"],["e","e"],["x","x"]]
    print(s.calcEquation(equations=equations, values=values, queries=queries))