資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 最佳賬戶餘額
假設一群朋友去度假，有時他們會互相借錢。例如，Amit 為 Bikram 的午餐支付了 10 美元。然後後來 Chandan 給 Amit 5 美元作為計程車費。我們必須設計一個模型，其中每個交易都被視為一個元組 (x, y, z)，這意味著 x 人給了 y 人 z 美元。
假設 Amit、Bikram 和 Chandan 分別是第 0、1 和 2 個人，則交易可以表示為 [[0, 1, 10], [2, 0, 5]]。如果我們有一組人之間的交易列表，我們必須找到結算債務所需的最小交易次數。
因此，如果輸入類似於 [[0,1,10], [2,0,5]]，則輸出將為 2，因為第 0 個人給了第 1 個人 10 美元。然後第 2 個人給了第 0 個人 5 美元。這裡需要兩次交易。一種結算債務的方法是第 1 個人分別向第 0 個人和第 2 個人支付 5 美元。
為了解決這個問題，我們將遵循以下步驟：
定義一個數組 v
定義一個函式 dfs()，它將接收 idx 作為引數，
ret := inf
當 (idx < v 的大小並且 v[idx] 不為零) 時，執行以下操作：
(將 idx 增加 1)
對於初始化 i := idx + 1，當 i − v 的大小，更新 (將 i 增加 1)，執行以下操作：
如果 v[i] * v[idx] < 0，則執行以下操作：
v[i] := v[i] + v[idx]
ret := ret 和 1 + dfs(idx + 1) 的最小值
v[i] := v[i] - v[idx]
返回 (如果 ret 等於 inf，則返回 0，否則返回 ret)
從主方法執行以下操作：
定義一個對映 m
n := t 的大小
對於初始化 i := 0，當 i < n，更新 (將 i 增加 1)，執行以下操作：
u := t[i, 0], v := t[i, 1]
bal := t[i, 2]
m[u] := m[u] + bal
m[v] := m[v] - bal
對於 m 中的每個鍵值對 i，執行以下操作：
如果 i 的值存在，則執行以下操作：
將 i 的值插入到 v 的末尾
(將 i 增加 1)
返回 dfs(0) 和 v 的大小的最小值
示例
讓我們檢視以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> v;
int dfs(int idx) {
int ret = INT_MAX;
while (idx < v.size() && !v[idx])
idx++;
for (int i = idx + 1; i < v.size(); i++) {
if (v[i] * v[idx] < 0) {
v[i] += v[idx];
ret = min(ret, 1 + dfs(idx + 1));
v[i] -= v[idx];
}
}
return ret == INT_MAX ? 0 : ret;
}
int minTransfers(vector<vector<int>>&t) {
map<int, int> m;
int n = t.size();
for (int i = 0; i < n; i++) {
int u = t[i][0];
int v = t[i][1];
int bal = t[i][2];
m[u] += bal;
m[v] -= bal;
}
map<int, int>::iterator i = m.begin();
while (i != m.end()) {
if (i->second)
v.push_back(i->second);
i++;
}
return min(dfs(0), (int)v.size());
}
};
main() {
Solution ob;
vector<vector<int>> v = {{0,1,10},{2,0,5}};
cout << (ob.minTransfers(v));
}輸入
{{0,1,10},{2,0,5}}輸出
2
432 次檢視
