Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
👨💻 Алгоритм:
1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.
2⃣Собрать все ненулевые чистые балансы в массив balance_list.
3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).
😎 Решение:
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
from collections import defaultdict
credit_map = defaultdict(int)
for t in transactions:
credit_map[t[0]] += t[2]
credit_map[t[1]] -= t[2]
credit_list = [amount for amount in credit_map.values() if amount != 0]
n = len(credit_list)
def dfs(cur):
while cur < n and credit_list[cur] == 0:
cur += 1
if cur == n:
return 0
cost = float('inf')
for nxt in range(cur + 1, n):
if credit_list[nxt] * credit_list[cur] < 0:
credit_list[nxt] += credit_list[cur]
cost = min(cost, 1 + dfs(cur + 1))
credit_list[nxt] -= credit_list[cur]
return cost
return dfs(0)
Ставь 👍 и забирай 📚 Базу знаний