[LeetCode]Optimal Account Balancing

题目描述:

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.

题目大意:

一群朋友去度假,有时会互相借钱。例如,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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

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匹配的顺序并不影响结果。暂时不知道如何证明这一点。

张贴您的评论