难度: Hard
Submission
运行时间: 40 ms
内存: 0.0 MB
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
Explain
这个题解通过将每一个人的债务和债权计算出来，然后通过深度优先搜索（DFS）来找到最小的交易次数来平衡所有的账户。首先，通过遍历所有的交易来计算每个人的最终的债务或债权。接下来把这些债务/债权值存储在一个数组中，然后使用递归的DFS来尝试所有的可能的交易组合，以找到可以使所有账户平衡的最小交易次数。在DFS中，我们跳过余额为0的账户，并尝试将当前账户的债务/债权通过交易转移给其他账户。如果当前的交易次数已经超过了之前找到的最佳解，那么就提前终止这条路径的探索。
时间复杂度: O(n!)
空间复杂度: O(n)
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 # 减去x需要支付的金额
person[y] += z # 增加y收到的金额
# 账号
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] # 尝试交易以平衡i账户
dfs(i + 1, cnt + 1) # 递归处理下一个账户
accounts[j] -= accounts[i] # 撤销交易
dfs(0, 0)
return res
Explore
`res`代表目前为止找到的最小交易次数，而`cnt`代表当前DFS路径上的交易次数。如果`cnt`已经等于或超过`res`，则继续当前路径的探索不会得到更优解，因此可以提前终止，以节省计算资源并提高算法效率。
使用`defaultdict(int)`可以自动为未初始化的键提供默认的整数值0，这在处理债务或债权时简化了代码，因为不需要检查和初始化键值。这种方法提高了代码的清晰度和执行效率，因为少了很多条件判断和键初始化的步骤。
尝试将债务或债权完全转移是为了简化问题的复杂度和决策过程。部分转移会导致状态空间显著增加，因为每次转移都有多种选择，这会使得DFS探索的路径和时间复杂度大幅增加。全额转移使得每个决策点的选择减少，从而可以更快地找到最小交易次数的解决方案。