​LeetCode刷题实战465：最优账单平衡

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 最优账单平衡，我们先来看题面：

https://leetcode-cn.com/problems/optimal-account-balancing/

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill’s lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person’s ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.

Person’s IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

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

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

注意：

一次交易会以三元组 (x, y, z) 表示，并有 x ≠ y 且 z > 0。

人的标号可能不是按顺序的，例如标号可能为 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 美元，所有的债务即可还清。

解题

https://zhuanlan.zhihu.com/p/127316386

解题思路：

把整个借还钱过程，看成一个系统，你从上帝视角看这些过程。

一个人如果借出去和还出去钱相等，说明可以退出这个系统，比如你借小明2元，小红欠你2元，虽然是两个过程，但是你在这个系统，没有导致自己的收入变多或者变少，上帝会帮你平衡这一切，你的退出不好影响系统。所以，我们可以计算出每个账号上有多少钱，正负表示自己拥有的财产。

本身就是NP难问题，暴力回溯解决问题

直接看代码，很容易理解的！

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        from collections import defaultdict
        person = defaultdict(int)
        for x, y, z in transactions:
            person[x] -= z
            person[y] += z
        # 账号
        accounts = list(person.values())
       
        res = float("inf")

        def dfs(i, cnt):
            nonlocal res
            # 全局变量退出递归
            if cnt >= res: return 
            # 账号为0不考虑
            while i < len(accounts) and accounts[i] == 0: i += 1
            # 遍历完
            if i == len(accounts):
                res = min(res, cnt)
                return
            for j in range(i + 1, len(accounts)):
                if accounts[i] * accounts[j] < 0:
                    accounts[j] += accounts[i]
                    dfs(i + 1, cnt + 1)
                    accounts[j] -= accounts[i]

        dfs(0, 0)
        return res

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-460题汇总，希望对你有点帮助！

LeetCode刷题实战461：汉明距离

LeetCode刷题实战462：最少移动次数使数组元素相等 II

LeetCode刷题实战463：岛屿的周长

LeetCode刷题实战464：我能赢吗