Сайт: https://easyoffer.ru/
Все каналы: t.me/+xGeAw6ckJ4liYzQy
Контакт для рекламы: @sendme_ads
Post #1271
116
Задача: 465. Optimal Account Balancing
Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
👨💻 Алгоритм:
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).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 {
var creditList = [Int]()
func minTransfers(_ transactions: [[Int]]) -> Int {
var creditMap = [Int: Int]()
for t in transactions {
creditMap[t[0], default: 0] += t[2]
creditMap[t[1], default: 0] -= t[2]
}
for amount in creditMap.values {
if amount != 0 {
creditList.append(amount)
}
}
let n = creditList.count
return dfs(0, n)
}
private func dfs(_ cur: Int, _ n: Int) -> Int {
var cur = cur
while cur < n && creditList[cur] == 0 {
cur += 1
}
if cur == n {
return 0
}
var cost = Int.max
for nxt in cur+1..<n {
if creditList[nxt] * creditList[cur] < 0 {
creditList[nxt] += creditList[cur]
cost = min(cost, 1 + dfs(cur + 1, n))
creditList[nxt] -= creditList[cur]
}
}
return cost
}
}Ставь 👍 и забирай 📚 Базу знаний
