Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 465. Optimal Account Balancing #465

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 465. Optimal Account Balancing #465

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

@grandyang grandyang commented May 30, 2019

 

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.

 

这道题给了一堆某人欠某人多少钱这样的账单,问经过优化后最少还剩几个。其实就相当于一堆人出去玩,某些人可能帮另一些人垫付过花费,最后结算总花费的时候可能你欠着别人的钱,其他人可能也欠你的欠,需要找出简单的方法把所有欠账都还清就行了。这道题的思路跟之前那道 Evaluate Division 有些像,都需要对一组数据颠倒顺序处理。这里使用一个 HashMap 来建立每个人和其账户的映射,其中账户若为正数,说明其他人欠你钱;如果账户为负数,说明你欠别人钱。对于每份账单,前面的人就在 HashMap 中减去钱数,后面的人在哈希表中加上钱数。这样每个人就都有一个账户了,接下来要做的就是合并账户,看最少需要多少次汇款。先统计出账户值不为0的人数,因为如果为0了,表明你既不欠别人钱,别人也不欠你钱,如果不为0,把钱数放入一个数组 accnt 中,然后调用递归函数。在递归函数中,首先跳过为0的账户,然后看若此时 start 已经是 accnt 数组的长度了,说明所有的账户已经检测完了,用 cnt 来更新结果 res。否则就开始遍历之后的账户,如果当前账户和之前账户的钱数正负不同的话,将前一个账户的钱数加到当前账户上,这很好理解,比如前一个账户钱数是 -5,表示张三欠了别人5块钱,当前账户钱数是5,表示某人欠了李四5块钱,那么张三给李四5块,这两人的账户就都清零了。然后调用递归函数,此时从当前改变过的账户开始找,cnt 表示当前的转账数,需要加1,后面别忘了复原当前账户的值,典型的递归写法,参见代码如下:

 

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        int res = INT_MAX;
        unordered_map<int, int> m;
        for (auto t : transactions) {
            m[t[0]] -= t[2];
            m[t[1]] += t[2];
        }
        vector<int> accnt;
        for (auto a : m) {
            if (a.second != 0) accnt.push_back(a.second);
        }
        helper(accnt, 0, 0, res);
        return res;
    }
    void helper(vector<int>& accnt, int start, int cnt, int& res) {
        int n = accnt.size();
        while (start < n && accnt[start] == 0) ++start;
        if (start == n) {
            res = min(res, cnt);
            return;
        }
        for (int i = start + 1; i < n; ++i) {
            if ((accnt[i] < 0 && accnt[start] > 0) || (accnt[i] > 0 && accnt[start] < 0)) {
                accnt[i] += accnt[start];
                helper(accnt, start + 1, cnt + 1, res);
                accnt[i] -= accnt[start];
            }
        }
    }
};

 

Github 同步地址:

#465

 

类似题目:

Evaluate Division

 

参考资料:

https://leetcode.com/problems/optimal-account-balancing/

https://leetcode.com/problems/optimal-account-balancing/discuss/95369/share-my-on-npc-solution-tle-for-large-case

https://leetcode.com/problems/optimal-account-balancing/discuss/95355/11-liner-9ms-DFS-solution-(detailed-explanation)

 

LeetCode All in One 题目讲解汇总(持续更新中...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.