465. 最优账单平衡 DFS 回溯

 465. 最优账单平衡

一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易，表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学（0, 1, 2 为人的标号），上述交易可以表示为 [[0, 1, 10], [2, 0, 5]]。

给定一群人之间的交易信息列表，计算能够还清所有债务的最小次数。

注意：

1. 一次交易会以三元组 (x, y, z) 表示，并有 x ≠ y 且 z > 0。
2. 人的标号可能不是按顺序的，例如标号可能为 0, 1, 2 也可能为 0, 2, 6。

示例 1：

输入：
[[0,1,10], [2,0,5]]

输出：
2

解释：
人 #0 给人 #1 共计 10 美元。
人 #2 给人 #0 共计 5 美元。

需要两次交易。一种方式是人 #1 分别给人 #0 和人 #2 各 5 美元。

示例 2：

输入：
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

输出：
1

解释：
人 #0 给人 #1 共计 10 美元。Person #0 gave person #1 $10.
人 #1 给人 #0 共计 1 美元。Person #1 gave person #0 $1.
人 #1 给人 #2 共计 5 美元。Person #1 gave person #2 $5.
人 #2 给人 #0 共计 5 美元。Person #2 gave person #0 $5.

因此，人 #1 需要给人 #0 共计 4 美元，所有的债务即可还清。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/optimal-account-balancing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功（差点失败了。遇到两次思路错误，第一次思路错误是写成贪心还改了两次，然后才意识到贪心错误是多项式；第二次是枚举只枚举了一边，因为正负集合长度是不等的，所以应该两边在使用时，都需要进行一次枚举，这里学到了，等长匹配的才可单侧枚举，否则要双侧枚举）

方法：DFS

1. 计算清楚每个人的金额的情况(x,y,z) , x 多 10 元， y 少 10 元【反过来也可以，保证计算的方向一致即可】
2. 0 元的平账忽略，剩下的人，正数分一组，负数分一组
3. DFS枚举所有情况：
   • 余额为0：正负金额同时消耗一个
   • 余额为负，正数消耗一个
   • 余额为正，负数消耗一个
   • 余额为0，且正负集合都已循环到结尾，结束，比较出最小答案

class Solution {
        public int minTransfers(int[][] transactions) {
            Map<Integer,Integer> map = new HashMap<>();
            for(int[] transaction:transactions){
                int a = transaction[0];
                int b = transaction[1];
                int c = transaction[2];
                map.put(a,map.getOrDefault(a,0)+c);
                map.put(b,map.getOrDefault(b,0)-c);
            }

            List<Integer> a = new ArrayList<>();
            List<Integer> b = new ArrayList<>();
            for(int money:map.values()){
                if(money>0) a.add(money);
                if(money<0) b.add(money);
            }
            dfs(a,b,0,0,0,0);
            return ans;
        }

        int ans = Integer.MAX_VALUE;

        private void dfs(List<Integer> a, List<Integer> b, int last, int ia, int ib,int time){
            if(ia == a.size() && ib == b.size()){
                ans = Math.min(time,ans);
                return;
            }

            if(last>0){
                for(int i = ib; i < b.size(); i++){
                    swap(b,ib,i);
                    dfs(a,b,last+b.get(ib),ia,ib+1,time+1);
                    swap(b,ib,i);
                }

                return;
            }

            for(int i = ia; i < a.size(); i++){
                swap(a,ia,i);
                if(last == 0){
                    dfs(a,b,last+a.get(ia)+b.get(ib),ia+1,ib+1,time+1);
                }else{
                    dfs(a,b,last+a.get(ia),ia+1,ib,time+1);
                }
                swap(a,ia,i);
            }
        }

        private void swap(List<Integer> a, int x, int y){
            int temp = a.get(x);
            a.set(x,a.get(y));
            a.set(y,temp);
        }
    }