最优账单平衡

/*
 * 思路：
 * 1. 首先计算每个帐户的净余额。
 * 2. 将余额非零的账户存入列表。
 * 3. 使用递归和Stream API来计算最少的交易次数以平衡账户。
 */
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = Arrays.stream(transactions).flatMapToInt(Arrays::stream)
            .collect(HashMap::new, (m, t) -> {
                m.put(t[0], m.getOrDefault(t[0], 0L) - t[2]);
                m.put(t[1], m.getOrDefault(t[1], 0L) + t[2]);
            }, HashMap::putAll);
        List<Long> debt = map.values().stream().filter(amount -> amount != 0).collect(Collectors.toList());
        return dfs(0, debt);
    }
    private int dfs(int start, List<Long> debt) {
        while (start < debt.size() && debt.get(start) == 0) start++;
        if (start == debt.size()) return 0;
        int result = Integer.MAX_VALUE;
        for (int i = start + 1; i < debt.size(); i++) {
            if (debt.get(i) * debt.get(start) < 0) {
                debt.set(i, debt.get(i) + debt.get(start));
                result = Math.min(result, 1 + dfs(start + 1, debt));
                debt.set(i, debt.get(i) - debt.get(start));
            }
        }
        return result;
    }
}