-
Notifications
You must be signed in to change notification settings - Fork 0
/
evaluate-division.py
59 lines (50 loc) · 1.8 KB
/
evaluate-division.py
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
48
49
50
51
52
53
54
55
56
57
58
59
import collections
class Solution:
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
# 1 exit invalid variable(not exits in Equations) -1
# 2 two same variable in Equations 1.0
# 3 two variable
if len(equations) == 0:
return [-1.0 for _ in range(len(queries))]
tree = self.buildGraph(equations, values)
paths = self.bfs(tree)
res = []
for querie in queries:
q = " ".join(querie)
if q in paths:
res.append(paths[q])
elif q[::-1] in paths:
res.append(1 / paths[q[::-1]])
else:
res.append(-1.0)
return res
def buildGraph(self, equations, values):
graph = {}
for eq, v in zip(equations, values):
graph[eq[0]] = graph.get(eq[0], {})
graph[eq[0]][eq[1]] = graph[eq[0]].get(eq[1], v)
graph[eq[1]] = graph.get(eq[1], {})
graph[eq[1]][eq[0]] = graph[eq[1]].get(eq[0], 1 / v)
return graph
def bfs(self, graph):
res = {}
for n in graph.keys():
queue = collections.deque([[n, 1.0]])
visited = set()
while len(queue) != 0:
length = len(queue)
for _ in range(length):
node = queue.popleft()
visited.add(node[0])
res[n+' '+node[0]] = node[1]
for k, v in graph[node[0]].items():
if k not in visited:
# print(node[1],graph)
queue.append([k, node[1] * v])
return res