Проблема –
Вам даны уравнения в формате A/, где A и B являются переменными, представленными как строки, а K является действительным числом (номер с плавающей точкой). Учитывая некоторые запросы, верните ответы. Если ответ не существует, return -1.0.
Пример
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Интуиция – найдите путь от источника к назначению, умножьте решение Edge Sessions –
from collections import defaultdict
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
g = defaultdict(list)
for i in range(len(equations)):
eq = equations[i]
val = values[i]
s, d = eq
g[s].append((d, val))
g[d].append((s, 1/val))
head = (equations[0][0], 1)
# print(g)
def dfs(root, path, s, d):
nonlocal st
st.add(root[0])
path = path + [root]
if s in st and d in st:
return path
res = None
for child in g.get(root[0], []):
if child[0] not in st:
res = dfs(child, path, s, d)
if res is not None:
return res
ans = []
for s, d in queries:
if s == d:
if s in g:
ans.append(1)
else:
ans.append(-1)
continue
st = set()
path = dfs((s, 1), [], s, d)
if path is None:
st = set()
path = dfs((d, 1), [], s, d)
if path is None:
ans.append(-1)
else:
flag = False
res = 1
id_p = [el[0] for el in path]
s_i = id_p.index(s)
e_i = id_p.index(d)
if s_i <= e_i:
for i in range(s_i + 1, e_i + 1):
res*= path[i][1]
ans.append(res)
else:
for i in range(s_i, e_i, -1):
res *= 1/path[i][1]
ans.append(res)
return ans
Оригинал: “https://dev.to/skbhagat40/evaluate-division-leetcode-day-24-6e8”