题目描述:
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:
- A transaction will be given as a tuple (x, y, z). Note that
x ≠ y
andz > 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.
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.
题目大意:
一群朋友去度假,有时会互相借钱。例如,Alice为Bill的午餐买单,花费$10。然后Chris给Alice $5打车费。我们可以将每一笔交易模型化为一个三元组 (x, y, z),意思是x给y花费$z。假设Alice, Bill和Chris分别标号0,1,2,以上交易可以表示为[[0, 1, 10], [2, 0, 5]]。
给定一群人的交易列表,返回结清债务关系的最小交易数。
注意:
交易以元组(x, y, z)的形式给出。x ≠ y 并且 z > 0
人员的ID不一定是线性的,例如,人员可以是0, 1, 2,也可以是0, 2, 6。
解题思路:
记忆化搜索
统计每个人借出/借入的金钱总数 将借出金钱的人放入集合rich,借入金钱的人放入集合poor 问题转化为计算从rich到poor的最小“债务连线”数 尝试用rich中的每个金额与poor中的每个金额做匹配 若存在差值,则将差值加入相应集合继续搜索 通过保存中间计算结果可以减少重复搜索
这道题目似乎是NP Hard
参考资料:http://www.mathmeth.com/tom/files/settling-debts.pdf
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)
本文链接:http://bookshadow.com/weblog/2016/11/21/leetcode-optimal-account-balancing/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
赤壁的火神 发布于 2016年11月24日 12:04 #
为什么记忆化搜索的第29行ans = min(solve(nrich, npoor) + 1, ans)是在内循环结束后继续搜索呢。。。这样子不是等于每次只会对当前的rich值和poor的最后一个值继续搜索吗。。。如果是这样子的话,完全可以去掉内循环,反正每次solve的目的只是处理poor中的一个值,个人理解。
在线疯狂 发布于 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匹配的顺序并不影响结果。暂时不知道如何证明这一点。