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 and z > 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.
题意：这一题要想明白好多点。
首先，要想明白，我们可以不关心，到底谁转给了谁，只关心每个人的债务即可。
其次，如果一个人的债务为0， 那么可以不用考虑这个人
然后，如果两个人的债务相加为0， 那么我们可以把其相互抵消用一次操作。因为没有比这样做更优的解法了。
最后，对所有持有债务的人，进行暴搜，回溯，看看最少能够进行多少次的债务
代码
class Solution {
public int helper(int[] arr, int index) {
if(index == arr.length) return 0;
int ret = arr.length;
if(arr[index] == 0) return helper(arr, index + 1);
for(int i = index + 1; i < arr.length; i++) {
if(arr[i] * arr[index] < 0) {
arr[i] += arr[index];
ret = Math.min(helper(arr, index + 1) + 1, ret);
arr[i] -= arr[index];
}
}
return ret;
}
public int minTransfers(int[][] transactions) {
//build debt;
Map<Integer, Integer> map = new HashMap<>();
for(int[] t : transactions) {
map.putIfAbsent(t[0], 0);
map.putIfAbsent(t[1], 0);
map.put(t[0], map.get(t[0]) - t[2]);
map.put(t[1], map.get(t[1]) + t[2]);
}
//pre compute
List<Integer> list = new ArrayList<>();
int ret = 0;
for(int val : map.values()) {
if(val == 0) continue;
if(list.contains(-val)) {
list.remove(Integer.valueOf(-val));
ret++;
} else {
list.add(val);
}
}
int[] arr = new int[list.size()];
for(int i = 0; i < list.size(); i++) arr[i] = list.get(i);
return ret + helper(arr, 0);
}
}