2016年10月27日星期四

437. Path Sum III

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11




O(n^2)
每个点作为起点,遍历结果
    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int findPath(TreeNode root, int sum){
        int res = 0;
        if(root == null)
            return res;
        if(sum == root.val)
            res++;
        res += findPath(root.left, sum - root.val);
        res += findPath(root.right, sum - root.val);
        return res;
    }

O(nlogn)  记录<preSum,Count>并且对每个点在preSum Map里找(sum-target)的值,sum是从root下来的path的总和,如果对于当前位置而言,(sum-target)出现过那么sum-前面对应位置的sum就是target,也就是说这两个位置之间的和是target。 对于preSum记录count 就能找到多个位置满足(当前sum-target == preSum)。 思路是如果这个点是end point 的话,count要加。

438. Find All Anagrams in a String



Sliding window 解法!!

一开始很纠结合适移动start pointer

m:当前状态下还要找几个character才能构成p
看了discussion。发现了因为要match,window size 固定。
当end >= p.length()-1就移动start到下个位置,以保持window大小固定。
对于出了window内的character,我们还原它的count: count[s.charAt(start++)-'a']++
如果start原来那个位置是给string p做了贡献的话,m++


  public List<Integer> findAnagrams(String s, String p) {  
     List<Integer> ans = new ArrayList<>();  
     int n = s.length(),m=p.length();  
     int[] count = new int[26];  
     for(int i = 0; i < m; i++){  
       count[p.charAt(i)-'a']++;  
     }  
     for(int start = 0, end = 0; end< n; end++){  
       int idx = s.charAt(end)-'a';  
       if(count[idx]-- > 0) m --;  
       if(m == 0)  
         ans.add(start);  
       //when the difference of left and end >= p.length() we move start pointer!  
       //if this pointer was point to sth in map, we count++  
       if(end - start + 1== p.length() && count[s.charAt(start++)-'a']++>=0) m++;  
     }  
     return ans;  
   }  

2016年10月24日星期一

397. Integer Replacement

Given a positive integer n and you can do operations as follow:
  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1
Example 2:
Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Recursive DFS

这个题的目的是把数字n尽快的通过去掉LSB 得到1

于偶数直接向右移动一位就可以,但是对于奇数来说,需要+1,或者-1来获得最右边bit为0从而移动。
对于2147483647(01111111 11111111 11111111 11111111)而言,加1会overflow。但是我们可以绕过+1. 通过先把+1和-1的两个偶数/2搞出来,然后加上cost(2)就可以了。


  public int integerReplacement(int n) {  
     if(n<= 1) return 0;  
     if(n%2==0) return 1+integerReplacement(n/2);  
     return 2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1));  
   }  


Tricky 的 iterative 做法

When n is even, the operation is fixed. The only unknown procedure is when it is odd
假设奇数n=2k+1, 那么  n+1 = 2k+2 and n-1 = 2k. 
(n+1)/2 = k+1 and (n-1)/2 = k.
说明下一步的两个数一个奇数,一个偶数。And the "best" case of this problem is to divide as much as possible. (Greedy)例如1110 和 10000 我们选10000
因此always pick n+1 or n-1 based on if it can be divided by 4
The only special case of that is when n=3 you would like to pick n-1 rather than n+1.
public int integerReplacement(int n) {
    if(n==Integer.MAX_VALUE) return 32; //n = 2^31-1;
    int count = 0;
    while(n>1){
        if(n%2==0) n/=2;
        else{
            if((n+1)%4==0&&(n-1!=2)) n+=1;
            else n-=1;
        }
        count++;
    }
    return count;
}

281. Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].


我的想法是维护(r,c)这个坐标,用一个list来存。在询问hasNext的时候需要注意!判断从这行往下能不能行,当走到底的时候,还要看从上头再下来能不能行。



 public class ZigzagIterator {  
   int r;  
   int c;  
   List<List<Integer>> list;  
   public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
     list = new ArrayList<>();  
     list.add(v1);  
     list.add(v2);  
     r= 0;c=0;  
   }  
   public int next() {  
     return list.get(r++).get(c);  
   }  
   public boolean hasNext() {  
     while(r < list.size() && list.get(r).size() <= c){  
       r++;  
     }  
     if(r == list.size()) {c++;r=0;}  
     while(r < list.size() && list.get(r).size() <= c){  
       r++;  
     }  
     return r!=list.size() && c < list.get(r).size();  
   }  
 }  


Better Solution

用linkedlist来做,这样拆list的cost只有O(1),每次把头拆下来,看一下能不能加到尾巴上就可以了。
next, hasNext 都是O(1)
Uses a linkedlist to store the iterators in different vectors. Every time we call next(), we pop an element from the list, and re-add it to the end to cycle through the lists.
public class ZigzagIterator {
    LinkedList<Iterator> list;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        list = new LinkedList<Iterator>();
        if(!v1.isEmpty()) list.add(v1.iterator());
        if(!v2.isEmpty()) list.add(v2.iterator());
    }

    public int next() {
        Iterator poll = list.remove();
        int result = (Integer)poll.next();
        if(poll.hasNext()) list.add(poll);
        return result;
    }

    public boolean hasNext() {
        return !list.isEmpty();
    }
}

2016年10月23日星期日

289. Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up
  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
对于这道题,因为不同的时刻的状态不能混淆,因此需要另开一个board 来存未来状态

但是由于状态只有两个0或1,1个bit,因此可以用第二个bit来表示下一个状态。算完之后,每个数字向右移动一位就可以了

1. in-place

 public class Solution {  
   public void gameOfLife(int[][] board) {  
     int m = board.length;  
     if(m == 0) return ;  
     int n = board[0].length;  
     for(int i = 0; i < m; i++){  
       for(int j = 0; j < n; j++){  
         int countLives = countLives(board,i,j);  
         System.out.println(countLives);  
         if((board[i][j] & 1) == 0 && countLives == 3){  
           board[i][j] |= 2;  
         }else if ((board[i][j] & 1) == 1 && (countLives== 3 || countLives == 2)){  
           board[i][j] |= 2;  
         }  
       }  
     }  
     for(int i = 0; i < m; i++)  
       for(int j = 0; j < n; j++)  
         board[i][j]>>=1;  
   }  
   public int countLives(int[][]board,int i,int j){  
     int m = board.length;  
     int n = board[0].length;  
     int[] dir = {-1,0,1};  
     int count = 0;  
     for(int dr: dir){  
       for(int dc:dir){  
         if(dr==0&&dc==0|| i+dr<0||j+dc<0||i+dr==m||j+dc==n)continue;  
         count += (board[i+dr][j+dc]&1);  
       }  
     }  
     return count;  
   }  
 }  




2. board is infinite:只存live 的点,算neighbors:neighbors[I, J] += 1
如果neighbors[I, J] == 3,说明这个点周围有且只有三个live,一定活下去,如果neighbors[I, J] == 2 说明这个点周围只有2个live,这种情况I, J一定要在原来live的List才能活下去。

def gameOfLifeInfinite(self, live):
    neighbors = collections.Counter()
    for i, j in live:
        for I in (i-1, i, i+1):
            for J in (j-1, j, j+1):
                if I != i or J != j:
                    neighbors[I, J] += 1
    new_live = set()
    for ij in neighbors.keys():
        if neighbors[ij] == 3 or neighbors[ij] == 2 and ij in live:
            new_live.add(ij)
    return new_live

319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on


int bulbSwitch(int n) {
    return sqrt(n);
}
A bulb ends up on iff it is switched an odd number of times.
Call them bulb 1 to bulb n. Bulb i is switched in round d if and only if d divides i. So bulb i ends up on if and only if it has an odd number of divisors.
Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except when i is a square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb i ends up on if and only if i is a square.
So just count the square numbers.
Let R = int(sqrt(n)). That's the root of the largest square in the range [1,n]. And 1 is the smallest root. So you have the roots from 1 to R, that's R roots. Which correspond to the R squares. So int(sqrt(n)) is the answer. (C++ does the conversion to int automatically, because of the specified return type).

440. K-th Smallest in Lexicographical Order

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

It's a complete (not full) denary tree. The BFS result is normal order and the DFS result is lexicographical order.
No need to run DFS because there isand all other children are full.













 public class Solution {  
   public int findKthNumber(int n, int k) {  
     String prefix = "";  
     while(k != 0){  
       //find each digit for nth number from most significant to least significant  
       //each digit range from 0 to 9  
       int i = 0;   
       for(;i <= 9; i++){  
         //we count numbers in the same tree, when count is bigger than n for the first time  
         //we found the digit   
         int count = countPrefix(n,prefix+i);  
         if(count < k){  
           k -= count;  
         }else{  
           break;  
         }  
       }  
       prefix = prefix + i;  
       k--;  
     }  
     return Integer.valueOf(prefix);  
   }  
   public int countPrefix(int n, String prefix){  
     long a = Long.valueOf(prefix);  
     if(a == 0||a>n) return 0;  
     long b = a + 1;  
     int count = 1;//a   
     a*=10;b*=10;// next level  
     while(a <= n){  
       count += Math.min(n+1,b) - a;  
       a*=10;b*=10;// next level    
     }  
     return count;  
   }  
 }  

255 Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?



Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.
维护一个单调递减的stack,当遇到递增的时候说明已经到了某个parent 的right subtree,并且不会在走比parent小的点,因此维护一个pre 值,来记录去right subtree之前的转折点。
  public boolean verifyPreorder(int[] preorder) {  
     Stack<Integer> desc = new Stack<>();  
     int pre = Integer.MIN_VALUE;  
     for(int i = 0; i < preorder.length; i++){  
       if(preorder[i] < pre) return false;  
       while(!desc.empty()&&preorder[i] > desc.peek()){  
           pre = desc.pop();  
       }  
       desc.push(preorder[i]);  
     }  
     return true;  
   }  


Solution 2 ... O(1) extra space
Same as above, but abusing the given array for the stack.
把preorder这个array当作stack来维护,用一个指针,如果是push,那么就是copy val到指针位置,并且向右移动指针,如果是pop 就像左移动指针。
public boolean verifyPreorder(int[] preorder) {
    int min = Integer.MIN_VALUE, i = -1;
    for (int val : preorder) {
        if (val < min)
            return false;
        while (i >= 0 && val > preorder[i])
            min = preorder[i--];
        preorder[++i] = val;
    }
    return true;
}

Super Ugly Number


任何一个ugly number都是由primes[] 里边的数字相乘得到。
如果我们用当前的ugly number 乘以 所有primes,放到priority queue 里边去,下次拿出来的就是下一个值。但是这中间会有重复。而且会产生很多不必要的值,因为小的primes*当前ugly 可能远小于大的primes*当前ugly。因此会产生memory limit exceeded

Memory Limit Exceeded
  public int nthSuperUglyNumber(int n, int[] primes) {  
     if(primes.length == 0) return 0;  
     PriorityQueue<Long> pq = new PriorityQueue<>();  
     pq.offer(1l);  
     while(n-->1){  
       long min = pq.poll();  
       while(!pq.isEmpty() && min == pq.peek()) pq.poll();  
       for(int i = 0 ; i < primes.length; i++)  
         if(min*primes[i] > min)  
           pq.offer(min*primes[i]);  
     }  
     return pq.poll().intValue();  
   }  

Ugly Number II 的 HINT:(primes={2,3,5})
  1. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
  2. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
因为An ugly number must be multiplied by任意一个primes里的值。因此对于下一个ugly number而言一定是一个之前的某个ugly number ✖️ primes[i]

因此要记录之前的ugly list 以及每个primes对应哪儿个ugly number
 public int nthSuperUglyNumber(int n, int[] primes) {  
     if(primes.length == 0) return 0;  
     int[] index = new int[primes.length];  
     int[] ans = new int [n+1];  
     ans[0] = 1;  
     for(int i = 1; i < n; i++){  
       int min = Integer.MAX_VALUE;  
       for(int j = 0; j < primes.length; j++){  
         min = Math.min(min, primes[j]*ans[index[j]]);  
       }  
       ans[i] = min;  
       for(int j = 0; j < primes.length; j++){  
         if(primes[j]*ans[index[j]] == min){  
           index[j]++;  
         }  
       }  
     }  
     return ans[n-1];  
   }  

318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.


这个题是bit manipulation的题。一开始看的时候就觉得是O(n^2) 的题但是没有仔细想。因为string compare也是要花时间的。因此如果把string compare 转换成O(1)就会节约出来string compare的复杂度。因为题目要求是两个string没有共同的character,那么我们可以用两个数字表示它们各自的character情况(类似set),然后我们比较两个数字即可!

 public int maxProduct(String[] words) {  
     int n = words.length;  
     if(n == 0) return 0;  
     int[] values = new int[n];  
     for(int i =0; i < n; i++){  
       for(int j = 0; j < words[i].length(); j++){  
         int d = words[i].charAt(j) - 'a';  
         values[i] |= 1 << d;// trick  
       }  
     }  
     int max = 0;  
     for(int i = 0; i < n; i++){  
       for(int j = i+1; j < n; j++){  
         if((values[i] & values[j]) == 0 && max < words[i].length() *words[j].length()){  
           max = words[i].length() *words[j].length();  
         }  
       }  
     }  
     return max;  
   }  

439. Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9?:T and F (T and F represent True and False respectively).
Note:
  1. The length of the given string is ≤ 10000.
  2. Each number will contain only one digit.
  3. The conditional expressions group right-to-left (as usual in most languages).
  4. The condition will always be either T or F. That is, the condition will never be a digit.
  5. The result of the expression will always evaluate to either a digit 0-9T or F.
Example 1:
Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.
Example 2:
Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"
Example 3:
Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

从右往左看,这个表达式我们可以试着看一看。
每次计算都是以‘?’ 为标志,当我们碰到'?'的时候,我们计算local result,并不需要区分trueStack VS. falseStack 因为我们碰到?的时候只需要看最近的三个点就可以了。即使是
?():() 这样的表达式,因为我们已经算过local的结果,因此还是比较最近的三个点。



 public String parseTernary(String expression) {  
     // why only judge on ?  
     // we look from right to left, think how we do it when we compute  
     // we ignore things except '?', when we meet '?', we look at nearby three elements  
     // event through ?():(), this situation, we've already calculated result for things inside()  
     // use stack to preserve previous solutions  
     Stack<Character> stack = new Stack<>();  
     for(int i = expression.length()-1; i>=0; i--){  
       if(expression.charAt(i) == '?'){  
         char t = stack.pop();  
         stack.pop();  
         char f = stack.pop();  
         if(expression.charAt(i-1) == 'F'){  
           stack.push(f);  
         }else {  
           stack.push(t);  
         }  
         i--;  
       }else{  
         stack.push(expression.charAt(i));  
       }  
     }  
     return stack.pop()+"";  
   }  

Java Interview

Q) What all memory areas are allocated by JVM?
Heap, Stack, Program Counter Register and Native Method Stack


Types of polymorphism in java- Runtime and Compile time polymorphism

Q) Can we override a static method?
No, we cannot override a static method.
Overriding depends on having an instance of a class. The point of polymorphism is that you can subclass a class and the objects implementing those subclasses will have different behaviors for the same methods defined in the superclass (and overridden in the subclasses). A static method is not associated with any instance of a class so the concept is not applicable.

Q) Is it possible to overload main() method of a class?
Yes, we can overload main() method as well.

private and final methods can be overloaded but they cannot be overridden.

An overridden method may have a more specific return type. That is, as long as the new return type is assignable to the return type of the method you are overriding, it's allowed.
For example:
class ShapeBuilder {
    ...
    public Shape build() {
    ....
}

class CircleBuilder extends ShapeBuilder{
    ...
    @Override
    public Circle build() {
    ....
}

2016年10月22日星期六

348. Design Tic-Tac-Toe

You may assume the following rules:
  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves is allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|







Could you trade extra space such that move() operation can be done in O(1)?
只有两个player

如果一个player想要赢,那么整行或者整列或者整个对角线都得是他的点。怎么O(1) move 实现这个呢?
就是说每次move的时候就要O(1) check 是否win。

You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

player1 positive score
player2 negative score
每个cell 存score 只有score == n的时候才win



 public class TicTacToe {  
   int[] rows;  
   int[] cols;  
   int diagonal;  
   int anti_diagonal;  
   int n;  
   /** Initialize your data structure here. */  
   public TicTacToe(int n) {  
     //if move to ith row, if ith row already has some thing, fail  
     rows = new int[n];  
     cols = new int[n];  
     diagonal = 0;  
     anti_diagonal = 0;  
     this.n = n;  
   }  
   /** Player {player} makes a move at ({row}, {col}).  
     @param row The row of the board.  
     @param col The column of the board.  
     @param player The player, can be either 1 or 2.  
     @return The current winning condition, can be either:  
         0: No one wins.  
         1: Player 1 wins.  
         2: Player 2 wins. */  
   public int move(int row, int col, int player) {  
     //player1 positive score  
     //player2 negative score  
     int score = player == 1 ? 1:-1;  
     rows[row]+=score;  
     cols[col]+=score;  
     if(row == col)  
       diagonal+=score;  
     if(row+col == n-1)  
       anti_diagonal += score;  
     if(rows[row] == n || cols[col] == n ||diagonal==n||anti_diagonal==n) return 1;   
     if(rows[row] == -n || cols[col] == -n ||diagonal==-n||anti_diagonal==-n) return 2;  
     return 0;  
   }  
 }  

331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:
"1,#"
Return false
Example 3:
"9,#,#,1"
Return false

   class Node{  
     String val;  
     boolean left;  
     public Node(String s){  
       left = false;  
       val = s;  
     }  
   }  
   public boolean isValidSerialization(String preorder) {  
     //use stack to store parent when we hit '#', '#' we pop parent  
     //when we hit '#', we know parent has gone through one part, if we went left before we pop  
     if(preorder.equals("#")) return true;  
     Stack<Node> stack = new Stack<>();  
     String s = "";  
     for(int i = 0 ; i < preorder.length(); i++){  
       char c = preorder.charAt(i);  
       if(c == ','){  
         stack.push(new Node(s));  
         s="";   
       }else if(c == '#'){  
         i++;  
         if(stack.empty()) return false;  
         while(!stack.empty() && stack.peek().left){  
           stack.pop();  
         }  
         if(!stack.empty())  
           stack.peek().left = true;  
         if(stack.empty() && i < preorder.length()-1)  
           return false;  
       }else{  
         s += c;  
       }  
     }  
     return stack.empty()&&s.equals("");  
   }  

存‘#’当作flag表示左边已经走完
public class Solution {
    public boolean isValidSerialization(String preorder) {
        // using a stack, scan left to right
        // case 1: we see a number, just push it to the stack
        // case 2: we see #, check if the top of stack is also #
        // if so, pop #, pop the number in a while loop, until top of stack is not #
        // if not, push it to stack
        // in the end, check if stack size is 1, and stack top is #
        if (preorder == null) {
            return false;
        }
        Stack<String> st = new Stack<>();
        String[] strs = preorder.split(",");
        for (int pos = 0; pos < strs.length; pos++) {
            String curr = strs[pos];
            while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) {
                st.pop();
                if (st.isEmpty()) {
                    return false;
                }
                st.pop();
            }
            st.push(curr);
        }
        return st.size() == 1 && st.peek().equals("#");
    }
}
NO Stack
https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution/2

Some used stack. Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we consider null as leaves, then
  • all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
  • all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).
Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diff by 1, because the node provides an in degree. If the node is notnull, we increase diff by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.
public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}