関小君刷题记

题目大意：

有一群朋友去度假，度假期间，他们会相互借钱，比如 Alice 帮助Bill支付了他的午饭费用10美金，之后 Chris 帮助 Alice 支付了5美金的打车费。我们将每笔借款使用（x,y,z）来表示，即x借了z美金给y，假设Alice, Bill和Chris 的编号分别是0，1，2。那么上述所有的借款可以表示为 [[0, 1, 10], [2, 0, 5]]。

题目会给出一群人的所有借款情况，求将所有欠款还清最少需要多少次。

注意：

1. 每笔借款使用 (x, y, z) 的形式表示，其中x!=y, z>0。
2. 每个人的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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-465-optimal-account-balancing-解题思路分析/