optimal-account-balancing

一群朋友去度假，有时互相借钱。

例如，爱丽丝为比尔的午餐支付了 10 美元。后来克里斯给爱丽丝 5 美元搭出租车。我们可以假设每笔交易为一个三元组(X,Y,Z)，这意味着第 X 个人借给第 Y 个人 Z 美元。假设 Alice，Bill 和 Chris 是第0，1，2 个人（0，1，2是他们的ID），他们之间的交易可以表示为[ [ 0，1，10 ]，[ 2，0，5 ] ]。

给定一组人之间的交易清单，返回结算所需的最低交易数量。

九章算法一篇置顶题目挺有意思第一次看到这种需要指数级复杂度的面试题

下面的解法非常具有局限性如果 debt非零的人多于32 或 64 下面的方法是行不通的

 public class Solution {

       public int minTransfer(int[][] transactions){

            Map<Integer, Integer> debts = new HashMap<Integer, Integer>();

            for(int[] t: transactions){

                    debts.put(t[0], getOrDefault(t[0], 0)-t[2]);

                    debts.put(t[1], getOrDefault(t[1], 0)+t[2]);

            }

            int len = 0;

            int[] account =  new int[debts.size()];

            for(int total: debts.values()){

                if(total!=0){

                   account[len++] = total;

                }

            }

            if(len ==0) return 0;

            int dp = new int[1<<len];

            Arrays.fill(dp, Integer.MAX_VALUE);

            for(int l =1; l <dp.length; l++){

                    int sum =0;

                    int count =0;

                    for(int i=0; i<len;i++){

                           if((1<<i&l)!=0){

                                 sum + = account[i];

                                 count ++;

                           }

                    }

                    if(sum ==0){

                            dp[l] = count-1;

                            for(int i =1; i<l;i++){

                                  if((i&l)==i &&(dp[i]+dp[l-i])< dp[l]){

                                         dp[l] = dp[i]+dp[l-i];

                                  }

                            }

                    }

            }

            return dp[len-1];

       }

 }

巴特西

optimal-account-balancing

最新文章

热门文章