Evaluate Division

Средняя№399граф

Даны уравнения вида x / y = k между переменными и запросы x / y. На каждый запрос нужно ответить по уравнениям или вернуть -1, если из них ничего не следует (переменной нет ни в одном уравнении или две переменные не связаны цепочкой уравнений). Наши уравнения: p / r = 5, r / u = 0.5, r / s = 4; запросы: p / s, s / p, p / q. Ответы — [20, 0.05, -1].

399 Evaluate DivisionРазбор · 1×

Пример: уравнения p / r = 5, r / u = 0.5, r / s = 4; найти p / s, s / p и p / q.

p / r = 5, r / u = 0.5, r / s = 4prsuqueriesp/ss/pp/qanswers—вызовы dfsвершина справа—
не посещенана пути, ждёттекущий вызовend, куда идёмвернула node / end, ↑ рядомтупик, вернула -1

graph = пустой словарь: для каждой переменной — её стрелки

01/68
сначала · назад · пуск · шаг
Скорость
1function calcEquation(equations, values, queries):
2 graph = empty map // variable → its (next, weight)
3 for each equation x / y = k:
4 graph[x].add((y, k))
5 graph[y].add((x, 1 / k))
6 answers = []
7 for each query start / end:
8 if start not in graph or end not in graph:
9 answers.add(-1)
10 else:
11 answers.add(dfs(start, end, empty set))
12 return answers
13
14function dfs(node, end, visited):
15 if node == end:
16 return 1
17 visited.add(node)
18 for (next, weight) in graph[node]:
19 if next not in visited:
20 rest = dfs(next, end, visited)
21 if rest != -1:
22 return weight * rest
23 return -1
состояние
start
–
end
–
node
–
next
–
weight
–
rest
–
visited
–
answers
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Стрелка x → y с весом k значит x / y = k, а обратная — y / x = 1 / k. Вдоль пути дроби сокращаются: (p / r) × (r / s) = p / s, поэтому произведение весов и есть ответ.
  2. Поиск в глубину пробует стрелки по одной; ветка, из которой до end не дойти, как u здесь, возвращает -1, и обход идёт по следующей стрелке. visited не даёт ходить по кругу.
  3. В графе есть только переменные из уравнений, поэтому запрос про любую другую — сразу -1.

Сложность

Время O(q × (n + m)), где n — число переменных, m — уравнений, q — запросов: каждый запрос — один обход, который заходит в переменную не больше одного раза. Память O(n + m) на граф и visited.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.