[Leetcode] 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 ≠ yandz > 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:
|
1 2 3 4 5 6 7 8 9 10 11 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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. |
Here are some easy to under solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Solution { public: int minTransfers(vector<vector<int>>& transactions) { unordered_map<int, int> mp; for (auto x : transactions) { mp[x[0]] -= x[2]; mp[x[1]] += x[2]; } vector<int> in; vector<int> out; for (auto x : mp) { if (x.second < 0) out.push_back(-x.second); else if (x.second > 0) in.push_back(x.second); } int amount = 0; for (auto x : in) amount += x; if (amount == 0) return 0; int res = (int)in.size() + (int)out.size() - 1; dfs(in, out, 0, 0, amount, 0, res); return res; } void dfs(vector<int> &in, vector<int> &out, int i, int k, int amount, int step, int &res) { if (step >= res) return; if (amount == 0) { res = step; return; } if (in[i] == 0) { ++i; k = 0; } for (int j = k; j < out.size(); j++) { int dec = min(in[i], out[j]); if (dec == 0) continue; in[i] -= dec; out[j] -= dec; dfs(in, out, i, j + 1, amount - dec, step + 1, res); in[i] += dec; out[j] += dec; } } }; |
from: https://discuss.leetcode.com/topic/75154/share-my-straightforward-c-solution-6ms
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
public int minTransfers(int[][] transactions) { if (transactions == null || transactions.length == 0 || transactions[0].length == 0) return 0; //calculate delta for each account Map<Integer, Integer> accountToDelta = new HashMap<Integer, Integer>(); for (int[] transaction : transactions) { int from = transaction[0]; int to = transaction[1]; int val = transaction[2]; if (!accountToDelta.containsKey(from)) { accountToDelta.put(from, 0); } if (!accountToDelta.containsKey(to)) { accountToDelta.put(to, 0); } accountToDelta.put(from, accountToDelta.get(from) - val); accountToDelta.put(to, accountToDelta.get(to) + val); } List<Integer> deltas = new ArrayList<Integer>(); for (int delta : accountToDelta.values()) { if (delta != 0) deltas.add(delta); } //since minTransStartsFrom is slow, we can remove matched deltas to optimize it //for example, if account A has balance 5 and account B has balance -5, we know //that one transaction from B to A is optimal. int matchCount = removeMatchDeltas(deltas); //try out all possibilities to get minimum number of transactions return matchCount + minTransStartsFrom(deltas, 0); } private int removeMatchDeltas(List<Integer> deltas) { Collections.sort(deltas); int left = 0; int right = deltas.size() - 1; int matchCount = 0; while (left < right) { if (-1 * deltas.get(left) == deltas.get(right)) { deltas.remove(left); deltas.remove(right - 1); right -= 2; matchCount++; } else if (-1 * deltas.get(left) > deltas.get(right)) { left++; } else { right--; } } return matchCount; } private int minTransStartsFrom(List<Integer> deltas, int start) { int result = Integer.MAX_VALUE; int n = deltas.size(); while (start < n && deltas.get(start) == 0) start++; if (start == n) return 0; for (int i = start + 1; i < n; i++) { if ((long) deltas.get(i) * deltas.get(start) < 0) { deltas.set(i, deltas.get(i) + deltas.get(start)); result = Math.min(result, 1 + minTransStartsFrom(deltas, start + 1)); deltas.set(i, deltas.get(i) - deltas.get(start)); } } return result; } |
from:https://discuss.leetcode.com/topic/69981/6ms-ac-easy-to-understand-java-solution-with-comments
Reference:
