05 August 2008
给一个交易数组，其中transactions[i] = [from_i, to_i, amount_i] 表示ID = from_i 的人给了ID = to_i 的人amount_i $。
返回清偿债务所需的最少交易次数。
DFS
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
class Solution {
/*
leetcode.com/problems/optimal-account-balancing/discuss/95355/11-liner-9ms-DFS-solution-(detailed-explanation)/99762
*/
public int minTransfers(int[][] transactions) {
Map<Integer, Long> map = new HashMap();
for (int[] t : transactions) {
long val1 = map.getOrDefault(t[0], 0L);
long val2 = map.getOrDefault(t[1], 0L);
map.put(t[0], val1 - t[2]);
map.put(t[1], val2 + t[2]);
}
List<Long> list = new ArrayList();
for (long val : map.values()) {
if (val != 0) list.add(val);
}
Long[] debts = new Long[list.size()];
debts = list.toArray(debts);
return dfs(debts, 0, 0);
}
private int dfs(Long[] debts, int pos, int count) {
while (pos < debts.length && debts[pos] == 0) {
pos++;
}
if (pos >= debts.length) {
return count;
}
int result = Integer.MAX_VALUE;
for (int i = pos + 1; i < debts.length; i++) {
if (debts[pos] * debts[i] < 0) {
debts[i] += debts[pos];
result = Math.min(result, dfs(debts, pos + 1, count + 1));
debts[i] = debts[i] - debts[pos];
}
}
return result;
}
}