Mündəricat
Problem bəyanat
Optimal Hesab Balanslaşdırması LeetCode Həlli – Sizə bir sıra əməliyyatlar verilir transactions hara transactions[i] = [fromi, toi, amounti] olan şəxs olduğunu göstərir ID = fromi Verdi amounti $ olan şəxsə ID = toi.
Qayıtmaq bu minimum sayı borcun ödənilməsi üçün tələb olunan əməliyyatlar.
Input: transactions = [[0,1,10],[2,0,5]] Output: 2 Explanation: Person #0 gave person #1 $10. Person #2 gave person #0 $5. Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Izahat
borcunu ödəmək nə deməkdir?
heç kim başqalarına borclu deyil
bir insanın başqalarına nə qədər borclu olduğunu necə təmsil edirik?
Biz hazırkı borc vəziyyətini qururuq debt[], məsələn borc[i] = 10 o deməkdir ki, bir adam başqalarına 10 borcludur? borcumuzu necə həll edək
[0, curId – 1] hesablanaraq,
üçün debt[curId],
hər curId + 1 <= i <debt.length belə debt[i] * debt[curId] < 0 həll edə bilər
idi
Balans üçün növbəti hesab, curId, vəziyyəti unikal şəkildə müəyyən edə bilər
dövlət funksiyası
state(debt[], curId) minimumdur əməliyyatlar borcları balanslaşdırmaq[curId…debtLength – 1] elə borclar[0…curId-1] balanslaşdırılsın.
məqsəd vəziyyəti
state(initial debt[], 0)
dövlət keçidi
indi: dövlət(borc[], curId)
növbəti: dövlət (balans curId, curId + 1-dən sonra borc[])
state(debt[], curId) = 1 + min(state (debt[] after balance curId, curId + 1))
Qeyd
- CurId hesabını kimin balanslaşdıra biləcəyinə necə qərar verə bilərik?
curId hesabını balanslaşdıra bilən bir çox insan var -person i behind curId with debt[i] * debt[curId] < 0.
Biz hər bir əməliyyatdan keçirik və hər bir şəxs üçün dəyərləri yeniləyirik.
- Bir adam başqasına pul veribsə, o qədər pulu geri alır. Beləliklə, həmin pulu onun hesabına əlavə edirik.
- Əgər adamın borcu varsa, o zaman onun hesabından pulu çıxarırıq.
Bizə üç cür insan qalacaq
- Pulunu geri alacaq insanlar (müsbət)
- Borcu olan insanlar. (Mənfi)
- Nə geri qaytaran, nə də borcu olmayan insanlar. Biz bu insanlara məskunlaşdıqca məhəl qoymayacağıq.
İndi müsbət məbləğləri mənfi məbləğlərlə uyğunlaşdırmalıyıq. Bütün müsbət və mənfi cəhətlər ləğv edildikdən sonra biz tələb olunan əməliyyatları yoxlayırıq və minimumu götürürük.
Minimum əməliyyatlar gətirəcək bu qalıqların uyğunlaşdırılma sırasını bilmirik. Beləliklə, bütün birləşmələri sınamalıyıq. Biz backtracking/dfs istifadə edirik.
Tranzaksiyaların sayı minimumdan çox olan df-ləri ləğv edəcəyik. (budama)
Kodu
Optimal hesab balansı üçün C++ kodu
class Solution {
public:
int minTransfers(vector<vector<int>>& trans)
{
unordered_map<int, long> bal; // each person's overall balance
for(auto& t: trans) {
bal[t[0]] -= t[2];
bal[t[1]] += t[2];
}
for(auto& p: bal) // only deal with non-zero debts
if(p.second) debt.push_back(p.second);
return dfs(0);
}
private:
int dfs(int s) // min number of transactions to settle starting from debt[s]
{
while (s < debt.size() && !debt[s]) ++s; // get next non-zero debt
int res = INT_MAX;
for (long i = s+1, prev = 0; i < debt.size(); ++i)
if (debt[i] != prev && debt[i]*debt[s] < 0) // skip already tested or same sign debt
{
debt[i] += debt[s];
res = min(res, 1+dfs(s+1));
prev = (debt[i]-=debt[s]);
}
return res < INT_MAX? res : 0;
}
vector<long> debt; // all non-zero debts
};
Optimal Hesab balansı üçün Java Kodu
class Solution {
public int minTransfers(int[][] transactions) {
int[] debt = buildDebtArray(transactions); // Debt amount to balance for each person.
return getMinTransfersAfter(0, debt);
}
private int getMinTransfersAfter(int curId, int[] debt) {
while (curId < debt.length && debt[curId] == 0)
curId++;
// Base case.
if (curId == debt.length)
return 0;
// Recursive case.
int minTransactions = Integer.MAX_VALUE;
for (int i = curId + 1; i < debt.length; i++) {
if (debt[i] * debt[curId] < 0) {
debt[i] += debt[curId];
minTransactions = Math.min(minTransactions, getMinTransfersAfter(curId + 1, debt) + 1);
debt[i] -= debt[curId];
}
}
return minTransactions;
}
private int[] buildDebtArray(int[][] transactions) {
Map<Integer, Integer> debtMap = new HashMap<>(); // Map person ID to debt amount.
for (int[] transaction : transactions) {
int giver = transaction[0];
int taker = transaction[1];
int amount = transaction[2];
debtMap.put(giver, debtMap.getOrDefault(giver, 0) + amount);
debtMap.put(taker, debtMap.getOrDefault(taker, 0) - amount);
}
int[] debt = new int[debtMap.size()];
int i = 0;
for (int amount : debtMap.values()) {
debt[i++] = amount;
}
return debt;
}
}
Optimal hesab balansı üçün Python kodu
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
tuplify = lambda balance: tuple(sorted((k, v) for k, v in balance.items()))
@lru_cache(None)
def dfs(balances):
if not balances:
return 0
res = math.inf
balances = {k: v for k, v in balances}
for size in range(2, len(balances) + 1):
for group in itertools.combinations(balances.keys(), size):
if sum(balances[k] for k in group) == 0:
remaining_balances = {k: v for k, v in balances.items() if k not in group}
res = min(res, size - 1 + dfs(tuplify(remaining_balances)))
return res
balances = collections.defaultdict(int)
for u, v, z in transactions:
balances[u] += z
balances[v] -= z
return dfs(tuplify({k: v for k, v in balances.items() if v}))
Optimal Hesab Balanslaşdırması üçün Mürəkkəblik Təhlili LeetCode Həlli
Zamanın mürəkkəbliyi
O(E+V)
Kosmik Mürəkkəblik
O (V)
