数据结构
网络
关系数据库管理系统
操作系统
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 次查看
