题目大意：
有一群朋友去度假，度假期间，他们会相互借钱，比如 Alice 帮助Bill支付了他的午饭费用10美金，之后 Chris 帮助 Alice 支付了5美金的打车费。我们将每笔借款使用（x,y,z）来表示，即x借了z美金给y，假设Alice, Bill和Chris 的编号分别是0，1，2。那么上述所有的借款可以表示为 [[0, 1, 10], [2, 0, 5]]。
题目会给出一群人的所有借款情况，求将所有欠款还清最少需要多少次。
注意：
- 每笔借款使用 (x, y, z) 的形式表示，其中x!=y, z>0。
- 每个人的id不一定是连续的，他们的id可能是0，1，2。也可能是0，2，6。
示例1：
输入: [[0,1,10], [2,0,5]] 输出: 2 解释: Person #0 借给 person #1 10美金. Person #2 借给 person #0 5美金. 我们需要2笔还款. 一种方式是 person #1 分别还给 person #0 和 #2 各5美金.
示例2：
输入: [[0,1,10], [1,0,1], [1,2,5], [2,0,5]] 输出: 1 解释: Person #0 gave person #1 $10. Person #1 gave person #0 $1. Person #1 gave person #2 $5. Person #2 gave person #0 $5. Therefore, person #1 only need to give person #0 $4, and all debt is settled.
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=465
解题思路分析：
本题我们需要对数据进行预处理，不论经过一轮怎么样的互相借钱，我们需要知道最终每个人的状态，也就是他们的财政状况到底是赤字还是黑字。我们在统计每个人最终状态时，比如a借给b，10美金，a的钱变成-10，而b变成10。最终每个人的状态会是一些正数，负数以及0组成的。余额为0的人显然没有债务问题，而余额是负的人需要找余额为正的人去讨债。
这样一来问题就变成了，给定一个数组，我们每一次操作可以将任意两数相加，求数组全变成0的最少操作次数。对于这个问题其实并没有什么比较好的方式，我们需要暴力尝试每一种还钱方案。其中，唯一能够优化的地方是，如果某人借出的数目与另一个人借入的数目相同时，在这两个人之间进行还款交易是最划算的。即我们将数组中绝对值相同但符合相反的所有数字先过滤出来，并记录下绝对值相同的数字对的个数，这是返回结果的一部分。而剩下的部分我们需要使用dfs暴力求解。
实现代码：
public int minTransfers(int[][] transactions) {
// 统计每个人最终的财务情况
Map<Integer, Integer> map = new HashMap<>();
for(int[] t : transactions){
int balance0 = map.getOrDefault(t[0],0);
map.put(t[0], balance0-t[2]);
int balance1 = map.getOrDefault(t[1],0);
map.put(t[1], balance1+t[2]);
}
// 将所有人的财政情况转化为list
List<Integer> list=new ArrayList<>();
// 返回结果
int res=0;
for(int val:map.values()) {
// 财务为0的人表示没有债务问题，跳过
if(val==0) continue;
// 如果list中存在与当前数绝对值相同但符号相反的数
if(list.contains(-val)){
// 优先这两个人进行交易
// 将这个人从list中删除
list.remove(Integer.valueOf(-val));
// 因进行了一笔还款，返回结果加一
res++;
}else{
// 将当前人的余额加入list
list.add(val);
}
}
// 为了提高效率，将list转为数组
int[] arr=new int[list.size()];
for(int i=0;i<list.size();i++) arr[i]=list.get(i);
// dfs暴力解剩下的债务
return res+dfs(arr,0);
}
int dfs(int[] arr, int index){
if(index==arr.length) return 0;
int current = arr[index];
if(current==0) return dfs(arr, index+1);
int res=Integer.MAX_VALUE;
for(int i=index+1;i<arr.length;i++){
int next=arr[i];
if(current*next<0){
int diff=current+next;
arr[i]=diff;
res=Math.min(res, dfs(arr, index+1)+1);
arr[i]=next;
}
}
if(res==Integer.MAX_VALUE) res=0;
return res;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Optimal Account Balancing.
Memory Usage: 36.6 MB, less than 76.92% of Java online submissions for Optimal Account Balancing.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-465-optimal-account-balancing-解题思路分析/