## 题目描述：

LeetCode 465. 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:

1. A transaction will be given as a tuple (x, y, z). Note that `x ≠ y` and `z > 0`.
2. 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.

Example 1:

```Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 \$10.
Person #2 gave person #0 \$5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 \$5 each.
```

Example 2:

```Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
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.
```

## 解题思路：

```统计每个人借出/借入的金钱总数

## Python代码：

``````class Solution(object):
def minTransfers(self, transactions):
"""
:type transactions: List[List[int]]
:rtype: int
"""
vdict = collections.defaultdict(dict)

def solve(rich, poor):
rlen, plen = len(rich), len(poor)
if min(rlen, plen) <= 1:
return max(rlen, plen)
rich.sort()
poor.sort()
trich, tpoor = tuple(rich), tuple(poor)
ans = vdict[trich].get(tpoor)
if ans is not None:
return ans
ans = 0x7FFFFFFF
for ri in range(rlen):
nrich = rich[:ri] + rich[ri+1:]
npoor = poor[1:]
if rich[ri] < poor[0]:
npoor.append(poor[0] - rich[ri])
elif rich[ri] > poor[0]:
nrich.append(rich[ri] - poor[0])
ans = min(solve(nrich, npoor) + 1, ans)
vdict[trich][tpoor] = ans
return ans

loan = collections.defaultdict(int)
for s, t, v in transactions:
loan[s] += v
loan[t] -= v
rich = [v for k, v in loan.iteritems() if v > 0]
poor = [-v for k, v in loan.iteritems() if v < 0]
return solve(rich, poor)
``````

Pingbacks已关闭。

1. 赤壁的火神 发布于 2016年11月24日 12:04 #

为什么记忆化搜索的第29行ans = min(solve(nrich, npoor) + 1, ans)是在内循环结束后继续搜索呢。。。这样子不是等于每次只会对当前的rich值和poor的最后一个值继续搜索吗。。。如果是这样子的话，完全可以去掉内循环，反正每次solve的目的只是处理poor中的一个值，个人理解。

2. 在线疯狂 发布于 2016年11月24日 22:14 #

非常感谢帮我指出这个问题 :) LeetCode OJ新增了测试用例 [[1,8,1],[1,13,21],[2,8,10],[3,9,20],[4,10,61],[5,11,61],[6,12,59],[7,13,60]] 第29行其实是笔误，少了一个缩进。之前的写法返回TLE，已无法通过系统测试。 从目前的测试用例来看，内循环似乎的确可以去掉，poor和rich匹配的顺序并不影响结果。暂时不知道如何证明这一点。