56 lines
2.0 KiB
Python
56 lines
2.0 KiB
Python
class Solution:
|
|
def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
|
|
vs = []
|
|
for equation in equations:
|
|
first_var = equation[0]
|
|
second_var = equation[1]
|
|
if first_var not in vs:
|
|
vs.append(first_var)
|
|
if second_var not in vs:
|
|
vs.append(second_var)
|
|
index_map = {}
|
|
for ind, var in enumerate(vs):
|
|
index_map[var] = ind
|
|
ls = []
|
|
vs_len = len(vs)
|
|
for ind, var in enumerate(vs):
|
|
ls.append([])
|
|
for i in range(vs_len):
|
|
if i == ind:
|
|
ls[ind].append(1)
|
|
else:
|
|
ls[ind].append(-1)
|
|
for ind, equation in enumerate(equations):
|
|
first_ind = index_map[equation[0]]
|
|
second_ind = index_map[equation[1]]
|
|
ls[first_ind][second_ind] = values[ind]
|
|
ls[second_ind][first_ind] = 1.0 / values[ind]
|
|
flag = 1
|
|
while flag == 1:
|
|
flag = 0
|
|
for i in range(vs_len):
|
|
for j in range(vs_len):
|
|
for k in range(vs_len):
|
|
if ls[i][j] != -1 : continue
|
|
if ls[i][k] == -1 or ls[k][j] == -1: continue
|
|
flag = 1
|
|
ls[i][j] = ls[i][k] * ls[k][j]
|
|
ls[j][i] = 1.0/ls[i][j]
|
|
output = []
|
|
for query in queries:
|
|
if query[0] not in vs or query[1] not in vs:
|
|
output.append(-1)
|
|
continue
|
|
first_ind = index_map[query[0]]
|
|
second_ind = index_map[query[1]]
|
|
output.append(ls[first_ind][second_ind])
|
|
return output
|
|
|
|
|
|
|
|
|
|
sol = Solution()
|
|
print(sol.calcEquation([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]))
|
|
print(sol.calcEquation([["a", "c"], ["b", "e"],["c", "d"], ["e", "d"]], [2.0, 3.0,0.5,5.0], [["a", "b"]]))
|
|
|