MY AC code


  • 0
    K

    I am not sure whether my code is correct....
    The complexity is O(2^N) I think.

    import java.util.*;
    
    public class Solution {
        private int ans = Integer.MAX_VALUE;
        
        public int minTransfers(int[][] transactions) {
                HashMap<Integer, Integer> map = new HashMap<>();
                for (int[] x : transactions) {
                    if (!map.containsKey(x[0])) 
                        map.put(x[0], -x[2]);
                    else
                        map.put(x[0], map.get(x[0])-x[2]);
                    
                    if (!map.containsKey(x[1]))
                        map.put(x[1], x[2]);
                    else
                        map.put(x[1], map.get(x[1])+x[2]);
                }
                
                ArrayList<Integer> lender = new ArrayList<>();
                ArrayList<Integer> receiver = new ArrayList<>();
                for (int x : map.keySet()) {
                    int money = map.get(x);
                    if (money < 0)
                        lender.add(-money);
                    else if (money > 0)
                        receiver.add(money);
                }
                
                helper(lender, receiver, 0);
                return ans;
        }
        
        private void helper(ArrayList<Integer> lender, ArrayList<Integer> receiver, int count) {
            boolean flag = true;
            
            for (int i = 0; i < lender.size(); i++) {
                if (lender.get(i) != 0) { 
                    flag = false;
                    for (int j = 0; j < receiver.size(); j++) {
                        if (receiver.get(j) != 0) {
                            int x = lender.get(i);
                            int y = receiver.get(j);
                            if (x > y) {
                                lender.set(i, x - y);
                                receiver.set(j, 0);
                            }
                            else if (x < y) {
                                lender.set(i, 0);
                                receiver.set(j, y - x);
                            }
                            else {
                                lender.set(i, 0);
                                receiver.set(j, 0);
                            }
                            helper(lender, receiver, count + 1);
                            lender.set(i, x);
                            receiver.set(j, y);
                        }   
                    }
                }
            }
            if (flag)
                ans = Math.min(ans, count);
        }
    }
    

  • 0
    F

    O(2^N) is the best possible, I guess, I also find some other code which is straightforward and easier to understand as well:
    https://github.com/MaskRay/LeetCode/blob/master/optimal-account-balancing.cc

    // Optimal Account Balancing
    #define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
    #define REP(i, n) FOR(i, 0, n)
    
    class Solution {
    public:
      int minTransfers(vector<vector<int>>& t) {
        unordered_map<int, int> m;
        int r = 0, c = 0;
        for (auto& x: t) {
          m[x[0]] += x[2];
          m[x[1]] -= x[2];
        }
        vector<int> a;
        for (auto& x: m)
          if (x.second)
            a.push_back(x.second);
        if (a.empty()) return 0;
        vector<int> dp(1<<a.size(), INT_MAX/2), cir;
        FOR(i, 1, 1<<a.size()) {
          int t = 0, c = 0;
          REP(j, a.size())
            if (i>>j & 1)
              t += a[j], c++;
          if (! t) {
            dp[i] = c-1;
            for (int t: cir)
              if ((i & t) == t)
                dp[i] = min(dp[i], dp[t]+dp[i-t]);
            cir.push_back(i);
          }
        }
        return dp.back();
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.