Optimal Account Balancing 理解

Leetcode 465. Optimal Account Balancing

请问这个道题怎么理解？

网上有两个解答：
https://www.jianshu.com/p/a73a8d965579

class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = new HashMap();
        // build id -> debt
        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]);
        }        

        // ignore those who dont has debt
        List<Long> list = new ArrayList();
        for(long val: map.values()) {
            if(val != 0) list.add(val);
        }
        
        // list -> array, just for faster calc & convenient
        Long[] debts = new Long[list.size()];
        debts = list.toArray(debts);
        
        // to counteract 抵消
        return helper(debts, 0 , 0);
    }

    // dfs(backtracking)
    int helper(Long[] debts, int pos, int count) {
        while(pos < debts.length && debts[pos] == 0) pos++;
        int res = Integer.MAX_VALUE;
        long pre = 0;
        
        for(int i = pos + 1; i < debts.length; i++) {
            // look for other debts with opposite sign to debt[pos]
            // pre: avoid same debt
            if(debts[i] != pre && debts[i] * debts[pos] < 0) {
                debts[i] += debts[pos];
                res = Math.min(res, helper(debts, pos + 1, count + 1)); // enter recursive: debts[pos] has been taken care of
                debts[i] = debts[i] - debts[pos]; // backtrack
                pre = debts[i];
            }
        }
      return res == Integer.MAX_VALUE ? count : res;
    }
}

这个解答不明白为这几行
res = Math.min(res, helper(debts, pos + 1, count + 1));

return res == Integer.MAX_VALUE ? count : res;


另一个是
public class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> debt = new HashMap<>();
        for(int[] t : transactions){       //预处理收支情况
            debt.put(t[0], debt.getOrDefault(t[0], 0) - t[2]);
            debt.put(t[1], debt.getOrDefault(t[1], 0) + t[2]);
        }
        int[] account = new int[debt.size()];
        int len = 0;
        for(int v : debt.values()){         //去除收支平衡的人
            if(v != 0){
                account[len++] = v;
            }
        }
        
        if(len == 0)
          return 0;
        
        int[] dp = new int[1 << len];
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        for(int i = 1; i <  dp.length; i++){   //枚举每个子集
        
            int sum = 0, count = 0;
            for(int j = 0; j < len; j++){
                if((1<<j & i) != 0){         //这个子集里有第j个人
                    sum += account[j];             //加上他的收支情况
                    count++;                 //平衡这个子集需要的最大交易数
                }
            }
           
            if(sum == 0){                    //如果这个子集的收支平衡，那么它是一个子问题
                dp[i] = count - 1;           //这个子集需要的最大交易数
                for(int j = 1; j < i; j++){  //枚举这个子问题的子集
                    if(((i & j) == j) && dp[j] + dp[i-j] < dp[i]){
                        dp[i] = dp[j] + dp[i - j];  //求这个子问题的最优解
                    }
                }
            }
        }
        return dp[dp.length - 1];            //返回总问题的最优解
        
    }
}

这一种看到<<就晕了，请问这道题的解法怎么理解

就是一个DFS 其实方法非常naive....类似于brute force

杨超越 发表于 2019-3-10 02:55
就是一个DFS 其实方法非常naive....类似于brute force

为什么第一个方法要加pre呢？ https://www.jianshu.com/p/a73a8d965579

发现根本不需要pre, 我太迷信网上的解法了， ，大家帮忙有什么地方可以写的更好，谢谢

class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = new HashMap<>();
        //build id ->debt
        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> debts = new ArrayList<>();
        for(Long val: map.values()){
            if(val!=0){
                debts.add(val);
            }
        }
        return helper(debts,0,0);
    }
   
    int helper(List<Long> debts, int pos, int count){
        if(pos>debts.size()){
            return count;
        }
        int res = Integer.MAX_VALUE;
        while(pos<debts.size()&&debts.get(pos) == 0){
            pos++;
        }
        for(int i = pos+1; i<debts.size(); i++){
            if(debts.get(i)*debts.get(pos)<0){
                Long m = debts.get(i)+debts.get(pos) ;
                debts.set(i, m);
                res = Math.min(res, helper(debts, pos+1, count+1));
                Long n = debts.get(i) - debts.get(pos);
                debts.set(i, n);
            }
        }
        return res == Integer.MAX_VALUE? count : res;
    }
}

limao123 发表于 2019-3-10 03:01
为什么第一个方法要加pre呢？ https://www.jianshu.com/p/a73a8d965579

我觉得不用pre，你如果需要 我给你找找我之前写的c++版本