?LeetCode刷題實(shí)戰(zhàn)465：最優(yōu)賬單平衡

示例 1：

輸入：
[[0,1,10], [2,0,5]]
輸出：
2

解釋：
人 #0 給人 #1 共計(jì) 10 美元。
人 #2 給人 #0 共計(jì) 5 美元。

需要兩次交易。一種方式是人 #1 分別給人 #0 和人 #2 各 5 美元。

示例 2：

輸入：
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
輸出：
1

解釋：
人 #0 給人 #1 共計(jì) 10 美元。Person #0 gave person #1 $10.
人 #1 給人 #0 共計(jì) 1 美元。Person #1 gave person #0 $1.
人 #1 給人 #2 共計(jì) 5 美元。Person #1 gave person #2 $5.
人 #2 給人 #0 共計(jì) 5 美元。Person #2 gave person #0 $5.

因此，人 #1 需要給人 #0 共計(jì) 4 美元，所有的債務(wù)即可還清。

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
????????# 賬號(hào)
????????accounts = list(person.values())
???????
????????res = float("inf")

????????def?dfs(i, cnt):
????????????nonlocal?res
????????????# 全局變量退出遞歸
????????????if?cnt >= res: return?
????????????# 賬號(hào)為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