Monday, November 21, 2016

LeetCode 465 - Optimal Account Balancing


http://bookshadow.com/weblog/2016/11/21/leetcode-optimal-account-balancing/
A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
  1. A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
  2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:
Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.
记忆化搜索(穷举)
统计每个人借出/借入的金钱总数

将借出金钱的人放入集合rich,借入金钱的人放入集合poor

问题转化为计算从rich到poor的最小“债务连线”数

尝试用rich中的每个金额与poor中的每个金额做匹配

若存在差值,则将差值加入相应集合继续搜索
这道题目似乎是NP Hard
参考资料:http://www.mathmeth.com/tom/files/settling-debts.pdf
def minTransfers(self, transactions): """ :type transactions: List[List[int]] :rtype: int """ vdict = collections.defaultdict(dict) def solve(rich, poor): rlen, plen = len(rich), len(poor) if min(rlen, plen) <= 1: return max(rlen, plen) ri = pi = 0 rich.sort() poor.sort() trich, tpoor = tuple(rich), tuple(poor) ans = vdict[trich].get(tpoor) if ans is not None: return ans ans = 0x7FFFFFFF for ri in range(rlen): for pi in range(plen): nrich = rich[:ri] + rich[ri+1:] npoor = poor[:pi] + poor[pi+1:] if rich[ri] == poor[pi]: ans = min(solve(nrich, npoor) + 1, ans) elif rich[ri] > poor[pi]: ans = min(solve(nrich + [rich[ri] - poor[pi]], npoor) + 1, ans) else: ans = min(solve(nrich, npoor + [poor[pi] - rich[ri]]) + 1, ans) vdict[trich][tpoor] = ans return ans loan = collections.defaultdict(int) for s, t, v in transactions: loan[s] += v loan[t] -= v rich = [v for k, v in loan.iteritems() if v > 0] poor = [-v for k, v in loan.iteritems() if v < 0] return solve(rich, poor)

https://discuss.leetcode.com/topic/68755/share-my-o-n-npc-solution-tle-for-large-case/2
public int minTransfers(int[][] transactions) {
    Map<Integer, Integer> net = new HashMap<>();
    for (int[] t : transactions) {
        net.put(t[0], net.getOrDefault(t[0], 0) - t[2]);
        net.put(t[1], net.getOrDefault(t[1], 0) + t[2]);
    }
    int[] a = new int[net.size()];
    int cnt = 0;
    for (int v : net.values()) {
        if (v != 0) a[cnt++] = v;
    }
    return helper(a, 0, cnt, 0);
}
int helper(int[] a, int start, int n, int num) {
    int ans = Integer.MAX_VALUE;
    while(start < n && a[start] == 0) start++;
    for (int i = start + 1; i < n; ++i) {
        if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
            a[i] += a[start];
            ans = Math.min(ans, helper(a, start + 1, n, num + 1));
            a[i] -= a[start];
        }
    }
    return ans == Integer.MAX_VALUE ? num : ans;
}
X.
https://discuss.leetcode.com/topic/68740/looks-that-this-is-a-wrong-question-the-expected-solution-didn-t-consider-this-case/14
I have found a paper talking about this.
The question can be transferred to a 3-partition problem, which is NP-hard.
http://www.mathmeth.com/tom/files/settling-debts.pdf
方法:用银行结算的思路,首先计算出每个人的最后盈亏,然后用随机的算法找到比较可能的最小值。
in the problem, construct an isolated system. It mean the total amount of money in the system keeps constant. Thus, what matters is the amount of extra money each person have after all transactions complete. For example, if id1 gave id2 5$, then after that transaction id1's money decreased to 5$, on the contrary id2's money increased to 5$. That way, we know how did change account of each person. For imagination let's consider the following input [[1,2,3],[2,3,5], [4,1,6]]:
           id|  trans |  total |
          ---------------------
           1 | -3 + 6 |   +3   |
          ---------------------
           2 | +3 - 5 |   -2   |
         ----------------------
           3 |    +5  |   +5   |
         ----------------------
           4 |    -6  |   -6   |
         ----------------------
Now, we have some negative account changes and positive account changes. By the way it is not hard to see that they compensate each other. Now, our task is to balance the accounts, by performing minimal amount of transactions. For instance we can balance these accounts, by performing the following transactions: [1,2,2], [3,4,5], [1,4,1]. After that, all accounts become balanced, i.e 0 extra money in total. But we have performed 3 transactions. Can we do better? May be. The number of transactions depend on the order of pairs taking part in each transaction. Consequently, the next question is, 'how to know which set of pairs give minimum number of transactions?'. One solution idea is just, brute force through all pairs and just take the minimum number of transactions. Another idea is just take some random combinations of pairs and take the minimum number of trans so far.
P.S: May be there are other elegant and exact solutions and this solution doesn't pretend to the best one, but it is quite reasonable. The more random shuffles you do, the more probability of hitting the answer. For that test cases 1000 is enough, may be less...
From your code here:
                if(n == p) continue;
                if(n>p){
                    stNeg.push(n-p);
                } else {
                    stPos.push(p-n);
                }
there are three cases (let's assume the persons are Person N and Person P):
  1. n == p: P pays N $p
  2. n > p: P pays N $p
  3. n < p: P pays N $n
    Basically, P pays N with all money he owns (n >= p), or P pays N in full (n < p).
However, this missed the case that P pays N $x, where $x < p and $x < n.
For example, the first person of (2, 50, 50, ..., 50) could pay $1 to both the first and last person of (51, 50, 50, ..., 50, 51), and get the minimal number of transactions. (This may not be a good example, but you know what I mean.)
I considered only the cases when some of the pairs pays off to close others account. Now, question is what if a pair makes transaction with some x$, where x<p and x< n and achieve minimal amount of transactions? Intuitively, such kind of transaction cannot decrease the total amount of transactions. Because, it doesn't change the state of the isolated system (total money flow doesn't change). But i think it is provable too.
    public int minTransfers(int[][] transactions) {
        if(transactions == null || transactions.length == 0) return 0;
        Map<Integer, Integer> acc = new HashMap<>();
        for(int i = 0;i<transactions.length;i++){
            int id1 = transactions[i][0];
            int id2 = transactions[i][1];
            int m = transactions[i][2];
            acc.put(id1, acc.getOrDefault(id1, 0)-m);
            acc.put(id2, acc.getOrDefault(id2, 0)+m);
        }
        List<Integer> negs = new ArrayList<>();
        List<Integer> poss = new ArrayList<>();
        for(Integer key:acc.keySet()){
            int m = acc.get(key);
            if(m == 0) continue;
            if(m<0) negs.add(-m);
            else poss.add(m);
        }
        int ans = Integer.MAX_VALUE;
        Stack<Integer> stNeg = new Stack<>(), stPos = new Stack<>();
        for(int i =0;i<1000;i++){
            for(Integer num:negs) stNeg.push(num);
            for(Integer num:poss) stPos.push(num);
            int cur = 0;
            while(!stNeg.isEmpty()){
                int n = stNeg.pop();
                int p = stPos.pop();
                cur++;
                if(n == p) continue;
                if(n>p){
                    stNeg.push(n-p);
                } else {
                    stPos.push(p-n);
                }
            }
            ans = Math.min(ans, cur);
            Collections.shuffle(negs);
            Collections.shuffle(poss);
        }
        return ans;
    }
{{1, 8, 1}, {1, 9, 1}, {2, 8, 10}, {3, 9, 20}, {4, 10, 30}, {5, 11, 40}, {6, 12, 50}, {7, 13, 60}, {20, 80, 10}, {30, 90, 20}, {40, 100, 30}, {50, 110, 40}, {60, 120, 50}, {70, 130, 60}}
Yes, I see. Thank you for pointing out! But I think the reason is randomization, not that type of transactions you mentioned. My solution takes 1000 random permutations. But actually, it worth considering all permutations. So in that case the algorithm would run O(n!) time. After i increased the number of iterations up 100000, My solution started to churning out answers from 18 - 14. Therefore I decided to add some simple correction to perform obvious transactions first:
        int base = 0;
        for(Integer key:negInts.keySet()){
            
            if(!posInts.containsKey(key) ||  posInts.get(key) == 0 || negInts.get(key) == 0) continue;
            int p = posInts.get(key);
            int n = negInts.get(key);
            base += Math.min(n,p);
            if(p == n){
                posInts.put(key, 0);
                negInts.put(key, 0);
                continue;
            }
            if(p>n){
                posInts.put(key, p-n);
                negInts.put(key, 0);
                continue;
            }
            if(n>p){
                posInts.put(key, 0);
                negInts.put(key, n-p);
                continue;
            }
        }
        for(Integer key:negInts.keySet()){
            if(negInts.get(key) == 0) continue;
            for(int i = 0;i<negInts.get(key);i++) negs.add(key);
        }
        for(Integer key:posInts.keySet()){
            if(posInts.get(key) == 0) continue;
            for(int i = 0;i<posInts.get(key);i++) poss.add(key);
        }  
The code above first makes transactions where we can balance two accounts by one transaction. It means where n == p. So the rest of the accounts are balanced randomly. Now the code gives correct answers with higher probability.
public class Solution {
    public int minTransfers(int[][] transactions) {
        if(transactions == null || transactions.length == 0) return 0;
        Map<Integer, Integer> acc = new HashMap<>();
        for(int i = 0;i<transactions.length;i++){
            int id1 = transactions[i][0];
            int id2 = transactions[i][1];
            int m = transactions[i][2];
            acc.put(id1, acc.getOrDefault(id1, 0)-m);
            acc.put(id2, acc.getOrDefault(id2, 0)+m);
        }
        // int neg = 0, pos = 0;
        List<Integer> negs = new ArrayList<>();
        List<Integer> poss = new ArrayList<>();
        HashMap<Integer, Integer> negInts = new HashMap<>();
        HashMap<Integer, Integer> posInts = new HashMap<>();
        for(Integer key:acc.keySet()){
            int m = acc.get(key);
            if(m == 0) continue;
            if(m<0) negInts.put(-m, negInts.getOrDefault(-m,0)+1);
            else posInts.put(m, posInts.getOrDefault(m,0)+1);
        }
        int base = 0;
        for(Integer key:negInts.keySet()){
            
            if(!posInts.containsKey(key) ||  posInts.get(key) == 0 || negInts.get(key) == 0) continue;
            int p = posInts.get(key);
            int n = negInts.get(key);
            base += Math.min(n,p);
            if(p == n){
                posInts.put(key, 0);
                negInts.put(key, 0);
                continue;
            }
            if(p>n){
                posInts.put(key, p-n);
                negInts.put(key, 0);
                continue;
            }
            if(n>p){
                posInts.put(key, 0);
                negInts.put(key, n-p);
                continue;
            }
        }
        for(Integer key:negInts.keySet()){
            if(negInts.get(key) == 0) continue;
            for(int i = 0;i<negInts.get(key);i++) negs.add(key);
        }
        for(Integer key:posInts.keySet()){
            if(posInts.get(key) == 0) continue;
            for(int i = 0;i<posInts.get(key);i++) poss.add(key);
        }
        int ans = Integer.MAX_VALUE;
        Stack<Integer> stNeg = new Stack<>(), stPos = new Stack<>();        
        for(int i =0;i<=1000;i++){
            for(Integer num:negs) stNeg.push(num);
            for(Integer num:poss) stPos.push(num);
            int cur = base;
            while(!stNeg.isEmpty()){
                int n = stNeg.pop();
                int p = stPos.pop();
                cur++;
                if(n == p) continue;
                if(n>p){
                    stNeg.push(n-p);
                } else {
                    stPos.push(p-n);
                }
            }
            ans = Math.min(ans, cur);
            Collections.shuffle(negs);
            Collections.shuffle(poss);
        }
        return ans;
    }
}
  1.     public int minTransfers(int[][] transactions) {  
  2.         Map<Integer, Integer> balances = new HashMap<>();  
  3.         for(int[] tran: transactions) {  
  4.             balances.put(tran[0], balances.getOrDefault(tran[0], 0) - tran[2]);  
  5.             balances.put(tran[1], balances.getOrDefault(tran[1], 0) + tran[2]);  
  6.         }  
  7.         List<Integer> poss = new ArrayList<>();  
  8.         List<Integer> negs = new ArrayList<>();  
  9.         for(Map.Entry<Integer, Integer> balance : balances.entrySet()) {  
  10.             int val = balance.getValue();  
  11.             if (val > 0) poss.add(val);  
  12.             else if (val < 0) negs.add(-val);  
  13.         }  
  14.         int min = Integer.MAX_VALUE;  
  15.         Stack<Integer> ps = new Stack<>();  
  16.         Stack<Integer> ns = new Stack<>();  
  17.         for(int i = 0; i < 10; i++) {  
  18.             for(int pos: poss) {  
  19.                 ps.push(pos);  
  20.             }  
  21.             for(int neg: negs) {  
  22.                 ns.push(neg);  
  23.             }  
  24.             int count = 0;  
  25.             while (!ps.isEmpty()) {  
  26.                 int p = ps.pop();  
  27.                 int n = ns.pop();  
  28.                 if (p > n) {  
  29.                     ps.push(p - n);  
  30.                 } else if (p < n) {  
  31.                     ns.push(n - p);  
  32.                 }  
  33.                 count++;  
  34.             }  
  35.             min = Math.min(min, count);  
  36.             Collections.shuffle(poss);  
  37.             Collections.shuffle(negs);  
  38.         }  
  39.         return min;  
  40.     }  

X. greedy - which not get best solution
https://discuss.leetcode.com/topic/68733/java-recursion
    public int minTransfers(int[][] transactions) {
        //I thought it's kind of network flow problem
        Map<Integer,Integer> map = new HashMap<>();
        for(int[] t : transactions){
            map.put(t[1],map.getOrDefault(t[1],0)-t[2]);
            map.put(t[0],map.getOrDefault(t[0],0)+t[2]);
        }
        int[] count = new int[1];
        helper(map,count);
        return count[0];
    }
//this getMax() and getMin() function is to get the index(key) of the MaxValue and MinValue
    private int getMax(Map<Integer,Integer> map){
        int max = -1;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(max == -1) max = entry.getKey();
            else if(entry.getValue() > map.get(max)){
                max = entry.getKey();
            }
        }
        return max;
    }
    private int getMin(Map<Integer,Integer> map){
        int min = -1;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(min == -1) min = entry.getKey();
            else if(entry.getValue() < map.get(min)){
                min = entry.getKey();
            }
        }
        return min;
    }

    private void helper(Map<Integer,Integer> map, int[] count){
        int max = getMax(map);
        int min = getMin(map);
//This means richest one and poorest one are both $0, means balance.
        if(map.get(max) == 0 && map.get(min) == 0) return;
        //Or we get the min abs value of max and min
        int minValue = Math.min(map.get(max),-map.get(min));
       //let the richest give the poorest the as much as possible money
        map.put(max, map.get(max)-minValue);
        map.put(min, map.get(min)+minValue);
      //after done this, add the count
        count[0]++;
        helper(map,count);
    }
http://www.1point3acres.com/bbs/thread-202132-1-1.html
这题是简化债务关系,就是给一堆人的账面交易记录,求最少交易次数使得账面平衡。

这题一般有两个思路,一个是把一个人当做中转站,所有人都跟他交易;第二个思路是把所有人的待结款项算出来,然后排序,用two pointer做。

然而这两个方法都不能保证所有情况下交易次数最少,这题实际上是一个NPC问题,可以归结为,在当前集合待结款项正数和负数两个集合中,找到两个不相交的最小子集,使得二者刚好能够结余。不停地寻找这样的子集,删掉,就能够得到最优。然而 subset sum 是NPC,我没想到这一层,结果跪了。

另外大家平时在做简单题的时候能够注意一下常数优化,比如减少不必要地循环次数,以及内外层循环计算等问题,我面试的时候这个被问了很多次。

假设有A, B, C D, E五个人,债务情况是
A, B, 2
A, C, 4
B, D, 5
C, D, 4
D, E, 7

那么债务结清之后每个人的结余应该是
A, -6
B, -3
C, 0
D, 2
E, 7
. 1point 3acres 璁哄潧
这时候C不用参与支付,省下A, B, D, E需要找到最少的支付次数来达到这个状态。最简单的情况是 A ->B -> D -> E (6, 9, 7),需要3次支付。但是如果最终的状态是. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
A -3,
B -2,
C, 0
D, 2
E, 3.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
那么只需要两次支付就能达到这个状态A -> E (3), B -> D (2)。

类似的,我们可以把所有结余为负的人看成一个集合,例如{A, B},同样的,所有结余为正的人看成一个集合{D, E}。对于正的集合,假设我们能找的一个划分,使得划分后的每一个小集合都能对应到负的集合的一个划分中的一个小集合,那么就能减少需要支付的次数。那么此题就转为求两个集合的最大数量的划分,使得划分中的所有子集都能找到另一个集合的划分里的一个子集。

例如集合{A, B}可以划分为{{A}, {B}}。如果能分别对应到{D, E}到划分{{D},{E}}中的两个子集,即A + E = 0 并且B + D = 0,那总的支付次数会少一次。到这里应该就是楼主说的NPC问题了。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
回到这道题,我能想到的一个搜索方法的方式是,对于正负两个集合,找到所有的子集的和,然后在这些和中寻找相等的一对子集。比如我们找到A+E = 0和B+D = 0。那么就可以递归的去求最多的划分次数。这里涉及到重复计算的子问题,可能自底向上更好解决。不知道有没有高手能想出更好的解法

这题的做法就是,算清各自应得/应付账款之后,分为正数负数两个集合,0扔掉,然后在正数里面找最小的子集,负数里面找另一个子集,使得存在两个不等于全集的子集,他们的和是相反数,然后合并这两个集合,这样一定是最优的。而找子集的过程就是subset sum,目前看只能穷举,要是你多项式时间做出来,那就图灵奖了。
    private List<int[]> transactions = new ArrayList<>();
    private List<int[]> finaltransactions = new ArrayList<>();
    private int number = Integer.MAX_VALUE;

    private void mintran(int[] a, int start){

        if(a.length < 2). 1point 3acres 璁哄潧
            return;
        else if(a.length == 2) {
            if(a[0] != 0){
                finaltransactions.add(a);
            }
            return;
        }else{
            int ind = -1;. From 1point 3acres bbs
            int max = Integer.MIN_VALUE;
            int i = start;
            for(; i < a.length; i++){.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
                if(Math.abs(a[i]) > max){. 鍥磋鎴戜滑@1point 3 acres
                    max = Math.abs(a[i]);.1point3acres缃�
                    ind = i;
                }.鏈枃鍘熷垱鑷�1point3acres璁哄潧
            }

            if(max == 0 || start == a.length){
                if(transactions.size() < number){. visit 1point3acres.com for more.
                    finaltransactions = new ArrayList<>(transactions);
                    number = transactions.size();
                }
                return;
            }

            int temp = a[ind];.鏈枃鍘熷垱鑷�1point3acres璁哄潧
            a[ind] = a[start];
            a[start] = temp;

            for(i = start + 1; i < a.length; i++){
                if(a[i] * a[start] < 0) {. 1point 3acres 璁哄潧
                    transactions.add(new int[]{a[i], a[start]});
                    temp = a[i];. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
                    a[i] += a[start];
                    mintran(a, start + 1);. 1point 3acres 璁哄潧
                    a[i] = temp;
                    transactions.remove(transactions.size()-1);
                }
            }

            temp = a[ind];. 1point 3acres 璁哄潧
            a[ind] = a[start];
            a[start] = temp;

        }
    }
payOnce每次产生的list长度应该是lender的个数*borrower的个数,即为a*b, a+b=n (总人数)。在pay函数里,queue的长度应该按a*b为等比数列增加吗?那最后不就是(a*b)^n? 
  1.         class Balance {
  2.                 int level;
  3.                 List<Integer> lender;
  4.                 List<Integer> borrower;
  5. . Waral 鍗氬鏈夋洿澶氭枃绔�,
  6.                 Balance(int level, List<Integer> posVals, List<Integer> negVals) {. 1point3acres.com/bbs
  7.                         this.level = level;
  8.                         lender = posVals;
  9.                         borrower = negVals;
  10.                 }

  11.                 public List<Balance> payOnce() {.1point3acres缃�
  12.                         List<Balance> ans = new ArrayList<>();
  13.                         for (int i = 0; i < lender.size(); i++)
  14.                                 for (int j = 0; j < borrower.size(); j++) {. From 1point 3acres bbs
  15.                                         int pos = lender.get(i);
  16.                                         int neg = borrower.get(j);
  17.                                         List<Integer> newLender = new ArrayList<>(lender);
  18.                                         List<Integer> newBorrower = new ArrayList<>(borrower);
  19.                                         newLender.remove(i);
  20.                                         newBorrower.remove(j);. 1point 3acres 璁哄潧

  21.                                         int diff = pos + neg;
  22.                                         if (diff > 0)
  23.                                                 newLender.add(pos + neg);
  24.                                         else if (diff < 0)
  25.                                                 newBorrower.add(pos + neg);

  26.                                         ans.add(new Balance(level + 1, newLender, newBorrower));
  27.                                 }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
  28.                         return ans;. Waral 鍗氬鏈夋洿澶氭枃绔�,
  29.                 }. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
  30. .鏈枃鍘熷垱鑷�1point3acres璁哄潧
  31.                 public boolean balanced() {
  32.                         return lender.isEmpty() && borrower.isEmpty();
  33.                 }
  34. .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
  35.                 public String toString() {
  36.                         return borrower.toString() + ", " + lender.toString()
  37.                                         + ", # of payments: " + level;
  38.                 }
  39.         }
  40. . 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
  41.         public int pay(int[] paid) {
  42.                 int n = paid.length;
  43.                 long total = 0;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
  44.                 for (int amount : paid) {
  45.                         total += amount;
  46.                 }
  47.                 if (total % n != 0).1point3acres缃�
  48.                         throw new IllegalArgumentException(
  49.                                         "Total amount can not be evenly divided.");. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
  50.                 int avg = (int) total / n;

  51.                 List<Integer> pos = new ArrayList<>();
  52.                 List<Integer> neg = new ArrayList<>();
  53.                 for (int amount : paid) {
  54.                         int diff = amount - avg;
  55.                         if (diff > 0)
  56.                                 pos.add(diff);
  57.                         else if (diff < 0)
  58.                                 neg.add(diff);
  59.                 }
  60. . From 1point 3acres bbs
  61.                 Balance initialBalance = new Balance(0, pos, neg);
  62.                 Queue<Balance> queue = new LinkedList<>();
  63.                 queue.offer(initialBalance);
  64.                 int ans = Integer.MAX_VALUE; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
  65.                 while (true) {
  66.                         Balance cur = queue.poll();
  67.                         System.out.println(cur);
  68.                         if (cur.balanced()) {. 1point 3acres 璁哄潧
  69.                                 ans = cur.level;
  70.                                 break;
  71.                         }
  72.                         List<Balance> nextLevel = cur.payOnce();
  73.                         for (Balance newBalance : nextLevel)
  74.                                 queue.offer(newBalance);. Waral 鍗氬鏈夋洿澶氭枃绔�,
  75.                 }

  76.                 return ans;
  77.         }


No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts