Regular Expression Matching (Advanced)

def Match(string, pattern):
        '*' star matches zero or more preceding characters
       '.' each dot matches exactly one character
       '^' prefix match, meaning that input string must start with exactly the same string following '^', e.g., '^abc' will match 'abcdefg', but 'cdefg' doesn't.
        '$' suffix match, meaning that input string must end with exactly the same string following '$', e.g., '$abc' will match 'cdefgabc', but 'abcdefg' doesn't
        without any special character: return True if pattern is in string (contains, not exactly same), and False otherwise
    # Your code here

Naive Way: This question is really hard in that it requires to match exactly part of the string. And it doesn't need to start from beginning of the string. I am assuming that ^ and $ will always appear as the first character of pattern and either of them will appear or nor of them appear.

My brute force way to match from every possible position. Use a recursive matching.

 public class Solution{  
   
      public static void main(String args[]){  
           Solution s = new Solution();  
           System.out.println(s.match("aabab",".*bab"));  
      }  
   
      public boolean match(String string, String pattern){  
           // edge case  
           if(pattern==null || pattern.length()==0) return string==null || string.length()==0;  
           if(string==null || string.length()==0) return pattern==null || pattern.length()==0;  
   
           // get suffix and prefix  
           boolean isPrefixed = false, isSuffixed = false;  
           if(pattern.charAt(0)=='^') isPrefixed = true;  
           if(pattern.charAt(0)=='$') isSuffixed = true;  
   
           // main process  
           char[] s = string.toCharArray();  
           char[] p = pattern.toCharArray();  
           if(isPrefixed) return match(s, 0, p, 1, -1);  
           else if(isSuffixed){  
                for(int i = 1;i < s.length;i++)  
                     if(match(s,i,p,1,1)) return true;  
           }else{  
                for(int i = 0;i < s.length;i++){  
                     if(i==0 && match(s,i,p,0,-1)) return true;  
                     else if(i!=0 && match(s,i,p,0,0)) return true;  
                }  
           }  
           return false;  
      }  
   
      private boolean match(char[] string, int index1, char[] pattern, int index2, int matchEnd){  
           // ending case  
           if(index2 == pattern.length){  
                if(matchEnd==1) return index1==string.length;  
                else if(matchEnd==-1) return index1 < string.length;  
                else return true;  
           }  
           if(index1 < 0 || index1 >= string.length || index2 >= pattern.length) return false;  
             
   
           int i = index1, j = index2;  
           if(string[i] == pattern[j] || pattern[j] == '.') return match(string, i+1, pattern, j+1, matchEnd);  
           else if(j+1 < pattern.length && pattern[j+1] == '*') return match(string, i, pattern, j+2, matchEnd);  
           else if(pattern[j] == '*'){  
                int u = i-2;  
                while(u < string.length && (u==i-2 || string[u] == pattern[j-1] || pattern[j-1] == '.'))  
                     if(match(string, u++, pattern, j+1, matchEnd)) return true;  
           }  
           return false;  
      }  
 }  

Conway's Game of Life

From wiki
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

The class interface is as follows.

class GameOfLife:
def __init__(self, board_width):
""" Your code here """

def set_alive(self, row, column):
""" Your code here """

def set_dead(self, row, column):
        """ Your code here """.

def step(self):
  """ Your code here """.
# more stuffs if you want to add.

Naive Thinking: Follow the rule to accomplish these functions. To update the board, I need a temporary board to store next state information.
 

 public class GameOfLife{  
      private int board[][];  
      GameOfLife(){init(10,10);}  
      GameOfLife(int row, int column){init(row, column);}  
      public void init(int L, int W){  
           assert L > 0;  
           assert W > 0;  
           board = new int[L][W];  
      }  
      public void set_alive(int row, int column){  
           if(!isInitialized()) return;  
           if(row > board.length && column > board[0].length) return;  
           board[row][column] = 1;  
      }  
      public void set_dead(int row, int column){  
           if(!isInitialized()) return;  
           if(row > board.length && column > board[0].length) return;  
           board[row][column] = 0;  
      }  
      public void step(){  
           if(!isInitialized()) return;  
           int temp[][] = new int[board.length][board[0].length];  
           // make a temporary board to store next state  
           for(int i = 0; i < board.length;i++)  
                for(int j = 0;j < board[0].length;j++)  
                     if(board[i][j]==1){  
                          if(getAliveNeighbor(i,j) < 2 || getAliveNeighbor(i,j) > 3)  
                               temp[i][j] = 0;  
                          else  
                               temp[i][j] = 1;  
                     }else if(getAliveNeighbor(i,j) == 3)  
                          temp[i][j] = 1;  
           // copy the temp board to main board  
           for(int i = 0;i < board.length;i++)  
                for(int j = 0;j < board[0].length;j++)  
                     board[i][j] = temp[i][j];  
      }  
      private int getAliveNeighbor(int x, int y){  
           int sum = 0;  
           for(int i = -1;i <= 1;i++)  
                for(int j = -1;j <= 1;j++)  
                     if(x+i >= 0 && x+i < board.length && y+j >= 0 && y+j < board[0].length && !(i==0 && j==0))  
                          sum += board[x+i][y+j]==1?1:0;  
           return sum;  
      }  
      private boolean isInitialized(){return !(board == null || board.length == 0);}  
      public void print(){  
           if(!isInitialized()) return;  
           for(int i = 0;i < board.length;i++){  
                for(int j = 0;j < board[0].length;j++)  
                     System.out.print(board[i][j]+" ");  
                System.out.println();  
           }  
           System.out.println();  
      }  
 }  

To test the game:

 public class Test{  
      public static void main(String args[]){  
           GameOfLife g = new GameOfLife();  
           for(int i = 0;i < 10;i++)  
                for(int j = 0;j < 10;j++)  
                     if(j%2==0 && i%2==0 || i%3==0) g.set_alive(i,j);  
           int loop = 5;  
           for(int i = 0;i < loop;i++){  
                g.print();  
                g.step();  
           }  
      }  
 }  

Output:

 1 1 1 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   
 1 0 1 0 1 0 1 0 1 0   
 1 1 1 1 1 1 1 1 1 1   
 1 0 1 0 1 0 1 0 1 0   
 0 0 0 0 0 0 0 0 0 0   
 1 1 1 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   
 1 0 1 0 1 0 1 0 1 0   
 1 1 1 1 1 1 1 1 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 1 0 1 0 1 0 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 1 1   
 1 0 0 0 0 0 0 0 0 0   
 1 0 0 0 0 0 0 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 1 1 1 1 1 1 1 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 0 0   
 0 0 0 0 0 0 0 0 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 1 1 1 1 1 0 0 1   
 1 1 0 0 0 0 0 0 1 1   
 1 1 0 0 0 0 0 0 0 0   
 1 1 0 0 0 0 0 0 1 1   
 1 0 1 1 1 1 1 0 0 0   
 1 0 1 1 1 1 1 1 0 1   
 1 0 1 1 1 1 1 1 0 1   
 0 0 0 0 0 0 0 0 1 1   
 0 0 0 0 0 0 0 0 0 0   
   
 0 1 0 0 0 0 0 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 0 0 0 1 1 1 0 0 1 1   
 0 0 1 0 0 0 0 0 0 0   
 0 0 0 1 1 1 0 0 0 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 0 0   
 0 0 1 0 0 0 0 0 0 1   
 0 0 0 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   

Minesweeper

Use a 2D board to represent the board. Given length (L) and width (W) and the number of mines (M). Randomly put mines into the L-by-W cells and mark the cell by number of surrounding mines. Must be absolutely random and no collision.
Naive Way: What does collision mean? I never met collision when I was playing minesweeper. I assume collision means no two mines are in the same position.
 

 public class Solution{  
      public static void main(String args[]){  
           Solution s = new Solution();  
           int b[][];  
           b = s.generateBoard(10, 10, 20);  
           printArray(b);  
      }  
      /**  
      * 9 means there is a mine in that particular cell  
      */  
      public int[][] generateBoard(int L, int W, int M){  
           // edge case  
           if( M > L*W) return null;  
           int[][] board = new int[L][W];  
           int row, col;  
           // generate mines in random position  
           for(int i = 0;i < M;i++){  
                // generate row index  
                do{  
                     row = (int)Math.floor(Math.random()*L);  
                     col = (int)Math.floor(Math.random()*W);  
                }while(board[row][col] == 9);  
                board[row][col] = 9;  
           }  
           // scan the board, put numbers on safe cells  
           for(int i = 0;i < L;i++){  
                for(int j = 0;j < W;j++){  
                     if(board[i][j]!=9){  
                          int sum = 0;  
                          // surronding area  
                          for(int x = -1; x <= 1; x++)  
                               for(int y = -1;y <= 1;y++)  
                                    if(i+x >= 0 && i+x < L && j+y >= 0 && j+y < W)  
                                         sum += board[i+x][j+y]==9?1:0;  
                          board[i][j] = sum;  
                     }  
                }  
           }  
           return board;  
      }  
      public static void printArray(int[][] b){  
           if(b == null || b.length==0) return;  
           for(int i = 0;i < b.length;i++){  
                for(int j = 0;j < b[0].length;j++)  
                     System.out.print(b[i][j] + " ");  
                System.out.println();  
           }  
      }  
 }  

Shuffle to Wavy Array

Given an unordered array A[]={1,2,3,7,1,2,5}, shuffle the array matching the condition A[0]<=A[1]>=A[2]<=A[3]...A possible result would be A[]={1,7,3,5,2,2,1}

Naive Thinking:Sorting the array helps to know the put integers in order. And put the second half one by one in between of the first half. This would take O(nlogn) run time. And Sorting definitely has redundancy. It doesn't need to be all in order.

Then I came to greedy. As greedy should do it in O(n). I try to match the condition as far as I traversal. If condition fails, pick up another one afterwards. This approach is not guaranteed to be O(n) and may fail at certain point.

Then I came up with swapping, as I swapping at each position will only cost O(n) run time. I try to keep the condition as far as I traversal. If no satisfied, like A[i] < A[i+1], where the condition is A[i] >= A[i+1], swap A[i] with A[i+1]. This approach works on several examples I randomly pick up. Then I found this approach is theoretically correct.

Proof by induction:
(1) when there is only 1 number, it satisfies.
(2) when there are two numbers, at most one swap with fulfill.
(3) 1.suppose A[i-1] <= A[i],
      if A[i] >= A[i+1]
          satisfies
      else A[i] < A[i+1]
          since A[i-1] <= A[i], A[i] < A[i+1], A[i+1] is the peek of three
          swap A[i] and A[i+1]
      2. suppose A[i-1] >= A[i],
      if A[i] <= A[i+1]
          satisfies
      else A[i] > A[i+1]
          since A[i-1] >= A[i], A[i] > A[i+1], A[i+1] is the valley of three
          swap A[i] and A[i+1].
Proved.

 public class Solution{  
      public static void main(String args[]){  
           Solution s = new Solution();  
           int A[] = {1,2,2,7,3,1,5};  
           s.suffle(A);  
           for(int i = 0;i < A.length;i++)  
                System.out.println(A[i]);  
      }  
      public void suffle(int[] A){  
           for(int i = 0;i < A.length-1;i++){  
                if(i%2==0)  
                     if(A[i] > A[i+1]) swap(A, i, i+1);  
                else  
                     if(A[i] < A[i+1]) swap(A, i, i+1);  
           }  
           return;  
      }  
      private void swap(int A[], int a, int b){  
           int temp = A[a];  
           A[a] = A[b];  
           A[b] = temp;  
      }  
 }  

Common String in Lists

Given a List of List of String, find the common String in all Lists, output them in sorted order. (could contain duplicates)

Naive Way:Need to consider case [[a,a,a],[a,a],[a,a,b]] outputs [a,a]. Use a HashMap as pattern, go through the lists, for each list, match it with the pattern, update the pattern, what left in the pattern is common string.

 public List<String> commonString(List<List<String>> lists){  
           List<String> rslt = new ArrayList<String>();  
           // edge case  
           if(lists.size()==0) return rslt;  
           // initialize pattern   
           Map<String, Integer> pattern = new HashMap<String, Integer>();  
           List<String> temp = lists.get(0);  
           setMap(pattern, temp);  
           // match pattern with other lists  
           for(int i = 1;i < lists.size();i++){  
                Map<String, Integer> map = new HashMap<String, Integer>();  
                setMap(map, lists.get(i));  
                Iterator it = pattern.entrySet().iterator();  
                List<String> toBeRemove = new ArrayList<String>();  
                while(it.hasNext()){  
                     Map.Entry pair = (Map.Entry)it.next();  
                     if(map.containsKey(pair.getKey()))  
                          pattern.put((String)pair.getKey(), Math.min(map.get(pair.getKey()),(int)pair.getValue()));  
                     else  
                          toBeRemove.add((String)pair.getKey());  
                }  
                for(int j = 0;j < toBeRemove.size();j++)  
                     pattern.remove(toBeRemove.get(j));  
           }  
           // collect results  
           Iterator it = pattern.entrySet().iterator();  
           while(it.hasNext()){  
                Map.Entry pair = (Map.Entry)it.next();  
                for(int i = 0;i < (int)pair.getValue();i++)  
                     rslt.add((String)pair.getKey());  
           }  
           // sort the result  
           Collections.sort(rslt);  
           return rslt;  
      }  
      private void setMap(Map<String, Integer> map, List<String> list){  
           for(int i = 0;i < list.size();i++){  
                if(!map.containsKey(list.get(i)))  
                     map.put(list.get(i), 1);  
                else  
                     map.put(list.get(i), map.get(list.get(i))+1);  
           }  
      }  

Iterator over HashMap

How to use iterator to go through a HashMap?

 public static void printMap(Map mp) {  
   Iterator it = mp.entrySet().iterator();  
   while (it.hasNext()) {  
     Map.Entry pair = (Map.Entry)it.next();  
     System.out.println(pair.getKey() + " = " + pair.getValue());  
     it.remove(); // avoids a ConcurrentModificationException  
   }  
 }  

Find the row with Max 1s

From http://www.careercup.com/question?id=5700588635422720

 A 2-D array of 1's and 0's is given. Find the row with max 1's. The array is sorted row wise (all 0's in a row are followed by all 1's).





Naive Thinking: A first I just came up with all kinds of O(nm) solutions. For example scan column by column to find the first 1, or scan row by row and note down the earliest 1. Pretty bad, though, because O(n+m) solution did exists and there exists solution better than that.

An O(m+n) algorithm is kinda greedy. Keep two pointers, one for row(i), one for column(j). Start from the very end of first row, each time encounter a 1, step forward(j--), each time encounter a 0, it means current row will have no chance have more 1 than m-j, thus go to next row, starting from j. That saves us the time from repeatedly scanning rows that are denied.

 public class Solution{   
   public static void main(String args[]){   
    Solution s = new Solution();   
    int[][] matrix = {{0,0,0,1,1},   
        {0,0,1,1,1},   
        {0,0,0,0,1},   
        {0,0,0,1,1}};   
    System.out.println(s.findRowWithMaxOnes(matrix));   
   }   
   public int findRowWithMaxOnes(int[][] array){   
    int n = array.length;   
    int m = n==0?0:array[0].length;   
    int i = 0, j = m-1;   
    int row = 0;   
    while(i < n && j >= 0){   
     if(array[i][j]==1){   
      row = i;   
      j--;   
     }else{   
      i++;   
     }   
    }   
    return row;   
   }   
  }    

Improved Way: As you see, since the question gives the condition each row is sorted. That leads to binary search thinking. We can do a binary search to find the first 1 of current row instead of stepping forward once. That brings the run time to O(m+log n)

 public int findRowWithMaxOnes(int[][] array){  
           int n = array.length;  
           int m = n==0?0:array[0].length;  
           int i = 0, j = m-1;  
           int row = 0;  
           while(i < n && j >= 0){  
                j = binarySearch(array[i], 0, j);  
                row = i;  
                i++;  
                while(i < n && array[i][j]==0) i++;  
           }  
           return row;  
      }  
      private int binarySearch(int[] arr, int begin, int end){  
           while(begin < end){  
                int middle = (begin+end)/2;  
                if(arr[middle] == 0 && arr[middle+1] == 1) return middle+1;  
                if(arr[middle] == 0) begin = middle+1;  
                else end = middle;  
           }  
           return begin;  
      }  

Finding all palindromes in String

Finding all palindromes in String.

Naive Thinking: Use the method described in  longest-palindromic-substring . There are covered ranges for each character. That's the result we want.

Time complexity O(n^2) (because to generate output, Hoops, that seems not great benefit using longest-palindrome's algorithm) 
Space O(n^2) (Also because of the output).

 import java.util.List;  
 import java.util.ArrayList;  
 import java.util.Set;  
 import java.util.HashSet;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     List<String> list = s.findAllPalindrome("abbbbabaaabab");  
     System.out.println(list);  
   }  
   public List<String> findAllPalindrome(String s){  
     List<String> list = new ArrayList<String>();  
     Set<String> set = new HashSet<String>();  
     String str = preProcess(s);  
     int f[] = new int[str.length()]; // coverage  
     int p = 0; // pivot  
     for(int i = 1;i < str.length();i++){  
       // check if position i is in pivot's coverage  
       if(p + f[p] > i){  
         if(2*p-i - f[2*p-i] > p-f[p])  
           f[i] = f[2*p-i];  
         else  
           f[i] = f[p] - (i-p);  
       }else{  
         f[i] = 0;  
       }  
       // extend if necessary  
       int j = 1;  
       while(i-f[i]-j >= 0 && i+f[i]+j < str.length() && str.charAt(i+f[i]+j)==str.charAt(i-f[i]-j)) j++;  
       f[i] += j-1;  
       // check if need to replace pivot  
       if(i+f[i] > p+f[p]) p = i;  
     }  
     // generate result  
     for(int i = 0;i < f.length;i++)  
       for(int j = 2;j <= f[i];j++)  
         set.add(s.substring((i-j)/2,(i+j+1)/2));  
     list.addAll(set);  
     return list;  
   }  
   private String preProcess(String s){  
     StringBuilder str = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       str.append("#");  
       str.append(s.charAt(i));  
     }  
     str.append("#");  
     return str.toString();  
   }  
 }  

Arithmetic Slice

From http://codesays.com/2014/solution-to-count-arithmetic-sequence/
There is another question related to Arithmetic Sequence Longest Arithmetic Sequenece

Arithmetic Slice, is a slice of an array num[i..j] with at least size 3 and has num[i], num[i+1]...num[j-1],num[j] forming an arithmetic sequence.

For example:

Input:

[-1, 1, 3, 3, 3, 2, 1, 0]

Output:

5

Explanation:

There are five arithmetic sequences in the input:

[-1, 1, 3], [3, 3, 3], [3, 2, 1], [2, 1, 0], and [3, 2, 1, 0]

O(n) time complexity is required. Once the number of Arithmetic Slice is greater than 1000000000, return -1.

Naive Thinking:这道题一开始的例子给的好烦人，最好自己写一两个例子。
[1 2 3] has 1 arithmetic slice
[1 2 3 4] has 3 arithmetic slice since [1 2 3], [2 3 4] and [1 2 3 4].

 这样就很清楚了，如果再来个[1 2 3 4 5]， 那就有6个了，就是连续的差等数列会使得count 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。

 算法复杂度是O(n)， space O(1)。

 public static final int limit = 1000000000;  
   public int getLAS(int[] A){  
     int count = 0;  
     // edge case  
     if(A.length <= 2) return count;  
     // main process  
     int i = 1;  
     while(i+1 < A.length){  
       int k = i+1;  
       // if its neighbor and itself form an AS, count++  
       if(2*A[i] == A[i-1]+A[k]){  
         count++;  
         if(count > limit) return -1;  
         // if two neighbors match, go through all the way until not match  
         while(k+1 < A.length && 2*A[k] == A[k-1]+A[k+1]){  
           k++;  
           count += (k-i);  
           if(count > limit) return -1;  
         }  
       }  
       // increment  
       i = k;  
     }  
     return count;  
   }  

Amplitude of Tree

From http://codesays.com/2014/solution-to-tree-amplitude/

In a binary tree T, a path P is a non-empty sequence of nodes of tree such that, each consecutive node in the sequence is a subtree of its preceding node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two paths, while [12, 8, 2] is not. The amplitude of path P is the maximum difference among values of nodes on path P. The amplitude of tree T is the maximum amplitude of all paths in T. When the tree is empty, it contains no path, and its amplitude is treated as 0.
For exmaple.

Input:

         5

       /   \

    8        9

   /  \     /  \ 

12   2  8   4

          /    /

        2    5

Output:

7

Explanation:

The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.

Naive Thinking: 关键句是The amplitude of path P is the maximum difference among values of nodes on path P. 可以采用DFS，记录一条路径上的最大值和最小值，求差值，最后再总的求一个最大值。

算法复杂度是 O(n), space O(n)。 

也可以用一个全局变量去记录max, 那样就不需要最后再总的求一次最大值。 

 class TreeNode{  
   int val;  
   TreeNode left, right;  
   TreeNode(int x){  
     val = x;  
     left = null;  
     right = null;  
   }  
 }  
 public int amplitudeOfTree(TreeNode root){  
     if(root==null) return 0;  
     int max = 0;  
     List<Integer> maxs = new ArrayList<Integer>();  
     // use a List<Integer> to record min and max along a path  
     List<Integer> list = new ArrayList<Integer>();  
     list.add(root.val);  
     list.add(root.val);  
     dfs(root,list,maxs);  
     for(int i = 0;i < maxs.size();i++)  
       max = Math.max(maxs.get(i),max);  
     return max;  
   }  
   private void dfs(TreeNode root, List<Integer> cur, List<Integer> maxs){  
     if(root.left==null && root.right==null) maxs.add(cur.get(1)-cur.get(0));  
     if(root.left != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.left.val < list.get(0)) list.set(0,root.left.val);  
       if(root.left.val > list.get(1)) list.set(1,root.left.val);  
       dfs(root.left, list, maxs);  
     }  
     if(root.right != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.right.val < list.get(0)) list.set(0,root.right.val);  
       if(root.right.val > list.get(1)) list.set(1,root.right.val);  
       dfs(root.right, list, maxs);  
     }  
     return;  
   }   

Longest Arithmetic Sequenece

There is another question related to Arithmetic Sequence Arithmetic Slice

Given an array, return the number of longest possible arithmetic sequence
For example, [-1, 1, 3, 3, 3, 2, 1, 0}  return 5 because {-1, 0, 1, 2, 3} forms a arithmetic sequence. 

Naive Thinking: 先排序会给找等差序列带来极大的便利。还有就是重复的是差为0的等差数列。
假设从第一个数开始，之后每一个数都会与之形成一个差值，以该差值为步长，看之后的数是否出现在数组中，遍历过的数字对可以放入一个Set中防止重复遍历，并将时间复杂度降低至O(n^2)。

算法复杂度是O(n^2), space O(n^2)

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Map;  
 import java.util.HashMap;  
 import java.util.Set;  
 import java.util.HashSet;  
 import java.util.Arrays;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     int num[] = {1,1,1,3,4,5,6,7,9,11};  
     System.out.println(s.longestArithmeticSeq(num));  
   }  
   // O(n^2)  
   public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     Map<Integer,Integer> map = new HashMap<Integer, Integer>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     // sort the array  
     Arrays.sort(num);  
     // put num->freq into a map  
     for(int i = 0;i < num.length;i++){  
       if(!map.containsKey(num[i]))  
         map.put(num[i],1);  
       else  
         map.put(num[i],map.get(num[i])+1);  
       longest = Math.max(longest,map.get(num[i]));  
     }  
     // go through the array  
     for(int i = 0;i < num.length-longest+1;i++){  
       for(int j = i+1;j < num.length;j++){  
         int gap = num[j]-num[i];  
         if(gap==0) continue;  
         int cur = num[i];  
         while(map.containsKey(cur+gap)){  
           // use set to record the path  
           List<Integer> list = new ArrayList<Integer>();  
           list.add(cur);  
           cur += gap;  
           list.add(cur);  
           if(set.contains(list)) break;  
           set.add(list);  
         }  
         longest = Math.max(longest, (cur-num[i])/gap+1);  
       }  
       // early break  
       if(longest > num.length/2) break;  
     }  
     return longest;  
   }  
 }   

Improved Way: 上面的方法感觉是比较麻烦而且容易出错，答案是一个DP。想都没想过这道题用DP。
而且这个DP很非常规。在http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/有详细解释。基本逻辑为：
opt[i][j] //  the length of arithmetic sequence by setting num[i] and num[j] as first two elements
// base case
opt[i][j] = 2  for all i and j
// iteration
opt[i][j] = 
if(num[i] + num[k|k>j] = 2*num[j]) opt[j][k]+1

算法复杂度为O(n^2), space O(n^2), 因为定义的是以num[i] 和 num[j] 开头的数列，所以在找的时候要从后往前扫，后面的部分先更新，前面的部分才能囊括后面的信息。

 public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     int opt[][] = new int[num.length][num.length];  
     Arrays.sort(num);  
     // base case  
     for(int i = 0;i < num.length-1;i++)  
       for(int j = i;j < num.length;j++)  
          opt[i][j] = 2;  
     // iteration  
     for(int j = num.length;j >= 0;j--){  
       int i = j-1, k = j+1;  
       while(i >= 0 && k < num.length){  
         if(num[i] + num[k] < 2*num[j])  
           k++;  
         else if (num[i] + num[k] > 2*num[j])  
           i--;  
         else{  
           opt[i][j] = opt[j][k] + 1;  
           longest = Math.max(longest, opt[i][j]);  
           i--;  
           k++;  
         }  
       }  
     }    
     return longest;  
   }  

还有人在Discuss里提出一个以最大差距为一个参数的DP。基本逻辑为
opt[i][j] // 从num[0..i]的以 j 为步长的等差数列的长度。
// base case
opt[0][j] = 1
// iteration
opt[i][j] = if(num[i]-num[t] == j) opt[t][j] + 1

实际写得时候不用在Iteration部分遍历所有j，因为只需要求出num[i]-num[t]能产生的所有j就行了。

算法复杂度是 O(max(n^2, num[max]-num[min])), space 是 O(n * num[max]-num[min]))。
由于整数最大差值达到2^32，有可能空间不足以创建这个二维数组。所以这个算法有很大的漏洞。但是这个想法是对的。如果空间不足创建二维数组，可以将步长用map来记录，只记录num中可以产生的步长，将步长map到一个list上，list里存所有以该步长为间隔的两个数的集合。这样还是可以使算法复杂度达到O(n^2)， space O(n^2)的。

 public int longestArithmeticSeq(int num[]){  
     if(num.length < 2) return num.length;  
     Arrays.sort(num);  
     int longest = 2;  
     int m = num[num.length-1] - num[0];  
     // opt is defined "the length of longest arithmetix seq in num[0..i] using j as step"  
     int opt[][] = new int[num.length][m+1];  
     // base case  
     for(int i = 0;i <= m;i++) opt[0][i] = 1;  
     // iteration  
     for(int i = 0;i < num.length-1;i++){  
       for(int j = i+1;j < num.length;j++){  
         opt[j][num[j]-num[i]] = opt[i][num[j]-num[i]]+1;  
         longest = Math.max(longest, opt[j][num[j]-num[i]]);  
       }  
     }  
     return longest;  
   }   

Sliding Window Sum

Given a list of integers and a window size, return a new list of integers where each integer is the sum of all integers in the kth window of the input list. The kth window of the input list is the integers from index k to index k + window size - 1(inclusive).

For example, [1, 2, 3, 4] and window size 3 should return [6,9].

Naive Thinking: 用一个var标记当前和，每次前进一步都减头部加尾部。

算法复杂度是O(n)。

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,2,4,6};
        int sums[] = s.slidingWindowSum(num,4);
        for(int i = 0;i < sums.length;i++)
            System.out.print(sums[i] + " ");
        System.out.println();
    }

    public int[] slidingWindowSum(int num[], int window_size){
        // initialize result
        int sums[] = new int[Math.max(num.length-window_size+1,1)];
        // check if window_size is greater than num[] size, return -1
        if(window_size > num.length) sums[0] = -1;
        // current sum, function as a window
        int cur_sum = 0;
        // go through num[]
        for(int i = 0, j = 0;i < num.length;i++){
            // each time a new number come, add to window
            cur_sum += num[i];
            if(i >= window_size-1){
                // if not the start window, delete the first one from window
                if(i-window_size >= 0) cur_sum -= num[i-window_size];
                // set window(cur_sum) to output
                sums[j++] = cur_sum;
            }
        }
        return sums;
    }
}

Four Integers

有4个正数，A,B,C,D。改变他们的位置使得他们两两之间的距离之和最大。

Naive Way ：先写一个例子，1 3 4 6。如果采用一种greedy 的方法，第一个固定，第二个挑距离最大的6，第三个挑4，最后是3。这样下来 5 + 3 + 1 = 8。很明显，3和4放在一起距离太小了，把他们分开放最好。于是有了3 1 6 4，这样还是不如 4 1 6 3大。因为最大的和最小的会创造最大距离，而且他们离中间的两个都可以再差一个数，这样将一头一尾放在中间，然后中间两个分立两边，可造成最大距离和。

 import java.util.Arrays;

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = s.solution(1,3,4,6);
        for(int i = 0;i < num.length;i++)
            System.out.println(num[i]);
    }

    public int[] solution(int A, int B, int C, int D){
        int num[] = {A,B,C,D};
        Arrays.sort(num);
        swap(num, 0, 2);
        swap(num, 1, 3);
        swap(num, 0, 3);
        return num;
    }

    private void swap(int[] num, int x, int y){
        int temp = num[x];
        num[x] = num[y];
        num[y] = temp;
    }
}

Find Loops In Linkedlist

Find loops in LinkedList

Naive Thinking:用一快一慢两个指针找出是否有loop。着相当于是找圈的起点的简化版。 加强版的见Intersection of Two Linked Lists


算法复杂度O(n)。

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}

public class Solution{

    public static void main(String args[]){
        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(2);
        l1.next = l2;
        l2.next = l3;
        l3.next = l2;
        Solution s = new Solution();
        System.out.println(s.hasLoop(l1));
    }

    public boolean hasLoop(ListNode head){
        ListNode slow = head, fast = slow;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null) break;
            fast = fast.next;
            if(slow==fast) return true;
        }
        return false;
    }
}
 

Check Rotation Using one isSubstring Call

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 suing only one call to isSubstring (e.g, "waterbottle" is a rotation of "erbottlewat"). All Strings are assumed lowercase.

Naive Thinking:限制条件是只能用一次 isSubstring()。假设没有这个条件，先考虑这道题怎么做。假设单词A 和单词B，单词A从某个字母开始将和单词B完全匹配，知道单词A结尾，剩下的部分正好可以用 isSubstring来判断是否 单词B的后面的部分，这里同时还引出了一个漏洞就是必须确保单词A和单词B具有同样的词频。

算法复杂度是O(n^2)

public boolean isRotation(String s1, String s2){
        // check same character set
        int freq[] = new int[26];
        for(int i = 0;i < s1.length();i++)
            freq[(int)(s1.charAt(i)-'a')]++;
        for(int i = 0;i < s2.length();i++)
            freq[(int)(s2.charAt(i)-'a')]--;
        for(int i = 0;i < freq.length;i++)
            if(freq[i]!=0) return false;
        // check rotation
        for(int i = 0;i < s1.length();i++)
            if(s1.charAt(i)==s2.charAt(0))
                if(isEnd(s1, i, s2)) return isSubstring(s1.substring(0,i),s2);
        return false;
    }

    private boolean isEnd(String s1, int index, String s2){
        for(int i = index,j = 0;i < s1.length();i++,j++)
            if(s1.charAt(i)!=s2.charAt(j)) return false;
        return true;
    }

    public boolean isSubstring(String s1, String s2){
        return s2.indexOf(s1) >= 0;
    }

Improved Way: 这道题是Cracking the Coding Interview 里String/Array那一章的最后一道题。它的做法我想都没想过，特别巧妙。

这里直接照搬它的解释：
s1 = waterbottle; Let x = wat, y = erbottle
s1 = xy;
s2 = erbottlewat;
s2 = yx;

s1s1 = xyxy;
s2 = yx;
s2 will always be a substring of s1s1.

算法复杂度是O(n)。

public boolean isRotation(String s1, String s2){
        if(s1.length() == s2.length() && s1.length() > 0){
            String s1s1 = s1 + s1;
            return isSubstring(s2, s1s1);
        }
        return false;
    }

Find First Non Repeating Character in String

From http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/
Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’ and if input string is “GeeksQuiz”, then output should be ‘G’.

Naive Thinking: 用一个map去映射字母和出现次数？最后再遍历一遍，第一个出现次数为1的就是输出。可不可以一次遍历？好像可以，用一个指针指向目前最前出现的次数为1的位置。

public char firstNonRepeatingChar(String s){
        int index = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0;i < s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), 1);
            }else{
                map.put(s.charAt(i), map.get(s.charAt(i))+1);
                while(index < s.length() && map.containsKey(s.charAt(index)) && map.get(s.charAt(index)) > 1) index++;
            }
        }
        return index<s.length()?s.charAt(index):'0';
    }

Lowest Common Ancestor in a Binary Search Tree

From  http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
Given values of two nodes in a Binary Search Tree,  find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree.

The function prototype should be as follows:

 struct node *lca(node* root, int n1, int n2)
 n1 and n2 are two given values in the tree with given root.

For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.


Naive Thinking: Binary Search Tree 的题目一定要用上 左 < 中 < 右 这个性质。可以发现如果当前点是同时大于n1, n2 的，他们的LCA一定在当前节点的左子树，反之则在右子树。如果当前点在二者之间呢，说明这就是他们的LCA！



这是recursive的做法。

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        return traversal(root, n1, n2);
    }

    private TreeNode traversal(TreeNode root, int n1, int n2){
        if(root==null) return root;
        if(root.val >= n1 && root.val <= n2) return root;
        if(root.val > n1 && root.val > n2) return traversal(root.left,n1,n2);
        else return traversal(root.right,n1,n2);
    }


这是iterative的做法，用queue也可以，应该直接使用root作指针。这里好傻。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root==null) return root;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.val >= n1 && node.val <= n2) return node;
            if(node.val > n1 && node.val > n2 && node.left!=null) stack.push(node.left);
            else if(node.right!=null) stack.push(node.right);
        }
        return null;
    }

这是正确的做法。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        if(root==null) return root;
        while(root!=null){
            if(root.val >= n1 && root.val <= n2) return root;
            if(root.val > n1 && root.val > n2) root = root.left;
            else root = root.right;
        }
        return null;
    }


Improved Way: 如果这两个值有可能不在BST里呢？应当在找到LCA的时候继续遍历下去找到两个值。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        if(root==null) return root;
        while(root!=null){
            if(root.val >= n1 && root.val <= n2 && findNode(root,n1) && findNode(root, n2)) return root;
            if(root.val > n1 && root.val > n2) root = root.left;
            else root = root.right;
        }
        return root;
    }

    // improved version: make sure existence of n1 and n2
    private boolean findNode(TreeNode root, int n){
        while(root!=null){
            if(root.val == n) return true;
            if(root.val > n) root = root.left;
            else root = root.right;
        }
        return false;
    }

Remove Duplicates from an Unsorted Array

remove duplicates from an unsorted array, return its new length. It doesn't matter what's left beyond the length.

Naive Thinking: 因为是unsorted， 重复的数可能是分开的，不能用两个指针一快一慢进行了。需要用一个set去存已遍历过的。这样是O(n) run time, O(n) space。

 import java.util.Set;
import java.util.HashSet;

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3};
        for(int i = 0;i < s.removeDuplicates(num);i++)
            System.out.print(num[i] + " ");
        System.out.println();
    }

    public int removeDuplicates(int num[]){
        Set<Integer> set = new HashSet<Integer>();
        int j = 0;
        for(int i = 0;i < num.length;i++)
            if(!set.contains(num[i])){
                set.add(num[i]);
                num[j++] = num[i];
            }
        return j;
    }
}

Swap Two Numbers Without Temp

How to swap two numbers without a third variable?

I just collected two ways:

1. use bit operation:

a = a ^ b;
b = a ^ b;
a = a ^ b;

to illustrate:
b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
a = a ^ b ^ (a ^ b ^ b) = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b;

2. use -/+

a = a + b;
b = a - b;
a = a - b;

To illustrate:
b = a+b-b = a;
a = a+b-(a+b-b)=b;

Job Schedule

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum

Naive Thinking:  怎么看怎么像DP，还是经典的那种。
基本逻辑为：
opt[i] // maximum within time [0,i] without overlapping jobs
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[t] + cost of job[k] | where 0<=t<i , job[k]has start time >t, end time<=i)

但是实际做才发现，每次更新opt[i]都要遍历一遍所有job，这很不好，因为即使将job排序也不能有效减少算法复杂度O(n^3)，所以想到了这题跟 maximum non-overlapping intervals 很像。可能可以用Greedy。用Greedy先写一个例子

[  1  ]  [   3     ]
    [    5    ]

如果greedy是优先选start time 小的，这个例子就会通不过。

如果是优先选cost高的，以下这个例子又会不通过。

[  3  ]  [   3     ]
    [    5    ]


那么看来greedy是不可行的，还是老老实写DP。但还是有必要重新讨论一下如何减少一个Loop的。

可不可以先把用什么方法把任意[i,j]时间段对应的job先求出来，如果能在O(n^2)时间内求出来就算是成功的。可以，先将job按start time->end time排序，然后用一个二维数组或者map存每一个时间段对应的job编号，需要用O(n^2)的space。


import java.util.Arrays;
import java.util.Comparator;

class Job{
        int start,end,cost;
        Job(int s, int e, int c){
            start = s;
            end = e;
            cost = c;
        }
    }
public class Solution{

    public static void main(String args[]){
        int n = 1;
        Job[] jobs = new Job[n];
        jobs[0] = new Job(0,3,1);
        jobs[1] = new Job(3,6,3);
        jobs[2] = new Job(1,5,5);
        jobs[3] = new Job(6,7,1);
        jobs[4] = new Job(7,10,4);
        jobs[5] = new Job(6,8,2);
        jobs[6] = new Job(8,10,2);
        jobs[7] = new Job(1,4,6);
        jobs[8] = new Job(3,7,6);
        jobs[9] = new Job(3,8,8);
        Solution s = new Solution();
        System.out.println(s.maxCostOfJobs(jobs));
    }

    public int maxCostOfJobs(Job[] jobs){
        // edge case
        if(jobs.length==0){return 0;}

        // sort the jobs by start time ->end time
        Comparator<Job> comparator = new Comparator<Job>(){
            @Override
            public int compare(Job a, Job b){
                if(a.start > b.start)
                    return 1;
                else if(a.start < b.start)
                    return -1;
                else{
                    if(a.end > b.end)
                        return 1;
                    else if(a.end < b.end)
                        return -1;
                    else
                        return 0;
                }
            }
        };
        Arrays.sort(jobs,comparator);

        // match time interval to job cost
        int min = jobs[0].start, max = jobs[jobs.length-1].end;
        int[][] match = new int[max-min+1][max-min+1];
        Job pre = jobs[0];
        for(int i = 0;i < jobs.length;i++){
            if(jobs[i].start==pre.start && pre.cost > jobs[i].cost){
                match[jobs[i].start-min][jobs[i].end-min] = pre.cost;
            }else{
                match[jobs[i].start-min][jobs[i].end-min] = jobs[i].cost;
                pre = jobs[i];
            }
        }

        // DP to get maximum cost
        int opt[] = new int[max-min+1];
        for(int i = 1;i < opt.length;i++){
            opt[i] = opt[i-1];
            for(int t = 0;t < i;t++)
                opt[i] = Math.max(opt[i], opt[t] + match[t][i]);
        }

        return opt[opt.length-1];

    }
}

Vertical Level Traversal of Tree

Print arbitrary binary tree by vertical levels / columns from left to right


example tree

      a
     / \
    b   c
   / \   \
  d   g   z.
   \     /
    e   i
       /
      q
     /
    x
   /
  x1
/
x2


sample output

x2
d x1
b e x.
a g q
c i




Naive Way: 第一想法是一个recursive的算法，给每个节点设置一个weight每次要遍历左节点weight-1，每次遍历右节点weight+1。后来发现recursive的无论是preorder traversal还是DFS都有一个致命问题就是顺序有可能打乱，比如左边的子节点的某一孙子是连续往右拐的，就会优先占据list的第一个。所以这里一定要BFS。不太能recursive。


import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 13;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
          List<List<Integer>> rlst = s.verticalLevelTraversalofTree(tree[0]);
          System.out.println(rlst.size());
          for(int i = 0;i < rlst.size();i++)
              System.out.println(rlst.get(i));
    }

    public List<List<Integer>> verticalLevelTraversalofTree(TreeNode root){
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        Queue<TreeNode> queue= new LinkedList<TreeNode>();
        Map<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        if(root==null){return rlst;}
        // initialize
        queue.add(root);
        weight.put(root,0);
        int min = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            int w = weight.get(node);
            // put into map
            if(!map.containsKey(w)){
                List<Integer> list = new ArrayList<Integer>();
                list.add(node.val);
                map.put(w,list);
            }else{
                List<Integer> list = map.get(w);
                list.add(node.val);
            }
            // enqueue
            if(node.left!=null){
                queue.add(node.left);
                weight.put(node.left,w-1);
            }
            if(node.right!=null){
                queue.add(node.right);
                weight.put(node.right,w+1);
            }
            // update min
            min = Math.min(min,w);
        }
        // generate result
        while(map.containsKey(min)){
            rlst.add(map.get(min++));
        }
        return rlst;
    }

}


Improved Way: 还有一道基于这道题目的问题是
Print the sum of all the numbers at every vertical level in a binary tree
解法一样，可以在得到list后还要求sum，也可以用一个map不断更新同一vertical level的sum。
而且这样一来顺序就不重要了，可以DFS或者preorder traversal什么的， 难度其实降低了。

Product of Array

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

Naive Thinking:这道题想了很久之后我居然想出来一个办法。
要用额外两个数组。
num[] =[  1     2    3   4   5 ]
arr1[]  =[  1     1    2   6  24]   从前往后，arr1[0] = 1, arr1[i] = arr1[i-1]*num[i-1];
arr2[]  =[120  60  20  5   1 ]   从后往前，arr2[n] = 1, arr2[i] = arr2[i+1]*num[i+1];
num[] =[120  60  40  30 24]  然后num[i] = arr1[i]*arr2[i]

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,2,3,4,5,6,7};
        s.productOfArray(num);
        for(int i = 0;i < num.length;i++)
            System.out.print(num[i] + " ");
    }

    public void productOfArray(int[] num){
        if(num.length < 2){return;}
        int arr1[] = new int[num.length];
        int arr2[] = new int[num.length];
        arr1[0] = 1;arr2[num.length-1] = 1;
        for(int i = 1;i < num.length;i++)
            arr1[i] = arr1[i-1]*num[i-1];
        for(int i = num.length-2;i >= 0;i--)
            arr2[i] = arr2[i+1]*num[i+1];
        for(int i = 0;i < num.length;i++)
            num[i] = arr1[i]*arr2[i];
        return;
    }
}

A Bird and Fruit Trees

There are n trees in a circle. Each tree has a fruit value associated with it. A bird can sit on a tree for 0.5 sec and then he has to move to a neighbouring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. We are given n number of seconds the bird has and, the fruit values val[m] of the trees. We have to maximise the total fruit value that the bird can gather. The bird can start from any tree.


Naive Thinking: 第一眼觉得是DP，但是写了写发现只要找到连续的相加之和最大的树群就行了，每棵树用的时间是固定的。

算法复杂度是O(n)。

 public class Solution{

    public static void main(String args[]){
        int val[] = {1,1,1,1,1,1,1,2,1,1,2,4};
        Solution s = new Solution();
        System.out.println(s.maxFruitValue(4,val));
    }

    public int maxFruitValue(int n, int val[]){
        int sum = 0;
        int max = 0;
        int begin = 0;
        int end = n;
        for(int i = 0;i < end && i < val.length;i++)
            sum += val[i];
        max = sum;
        if(n >= val.length){return max;}
        while(begin < val.length){
            sum -= val[begin++];
            sum += val[end];
            max = Math.max(max,sum);
            end = (end+1)%val.length;
        }
        return max;
    }
}

Path for Binary Tree

Print all the paths from root to every leaf in a binary tree


Naive Thinking: 可以用stack进行DFS，同时还要回溯，也可以用recursive的DFS，避免些回溯的麻烦。

算法复杂度是O(n), space是O(n)。

import java.util.List;
import java.util.ArrayList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 10;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
        List<List<Integer>> list = s.pathsForBinaryTree(tree[0]);
        for(int i = 0;i < list.size();i++)
            System.out.println(list.get(i));

    }

    public List<List<Integer>> pathsForBinaryTree(TreeNode root){
        // recursive DFS
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        if(root==null){return rlst;}
        search(new ArrayList<Integer>(), rlst, root);
        return rlst;
    }

    private void search(List<Integer> list, List<List<Integer>> rlst, TreeNode root){
        List<Integer> newList = new ArrayList<Integer>(list);
        newList.add(root.val);
        if(root.left==null && root.right==null)
            rlst.add(newList);
        else{
            if(root.left!=null)
                search(newList, rlst, root.left);
            if(root.right!=null)
                search(newList, rlst, root.right);
        }
    }

}

Maximum overlapping interval

Maximum overlapping interval

Given n intervals [si, fi], find the maximum number of overlapping intervals.

 Naive Thinking: 好像是讲greedy时候的题目。从对所有interval排序，如果si相同就按fi排序。然后用greedy的思想取第一个，接着取最接近却又不和第一个重合的，依次类推，直到不能取，这算是一层，然后同样的方法取第二层、第三层，直到所有的都被取了一遍，看有多少层。

如果用一个doubly linked list去存排好序的interval,就可以实现O(nlogn)的算法复杂度，否则，用数组遍历就是O(n^2)的算法复杂度。

import java.util.Set;
import java.util.HashSet;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Iterator;

class Interval{
        int b;
        int e;
        Interval(int begin, int end){
            b = begin;
            e = end;
        }
    }
public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        Interval[] intervals = new Interval[10];
        intervals[0] = new Interval(0, 3);
        intervals[1] = new Interval(2, 4);
        intervals[2] = new Interval(3, 6);
        intervals[3] = new Interval(4, 5);
        intervals[4] = new Interval(5, 9);
        intervals[5] = new Interval(7, 8);
        intervals[6] = new Interval(6, 7);
        intervals[7] = new Interval(9, 11);
        intervals[8] = new Interval(7, 13);
        intervals[9] = new Interval(3, 8);
        System.out.println(s.maxOverlapInterval(intervals));
    }

   

    public int maxOverlapInterval(Interval[] intervals){
        Set<Interval> set = new HashSet<Interval>();
        int layers = -1;
        int end = -1;
        Comparator<Interval> c = new Comparator<Interval>(){
            @Override
            public int compare(Interval x, Interval y){
                if(x.b < y.b){
                    return -1;
                }else if(x.b > y.b){
                    return 1;
                }else{
                    if(x.e < y.e){
                        return -1;
                    }else if(x.e > y.e){
                        return 1;
                    }
                }
                return 0;
            }
        };
        Arrays.sort(intervals, c);
        for(int i = 0;i < intervals.length;i++)
            set.add(intervals[i]);
        while(!set.isEmpty()){
            // Iterator<Interval> iter = set.iterator();
            // while(iter.hasNext()){
            //     Interval i = iter.next();
            //     if(i.b > end){
            //         set.remove(i);
            //         end = i.e;
            //     }
            // }
            for(int i = 0;i < intervals.length;i++){
                if(set.contains(intervals[i])){
                    if(intervals[i].b > end){
                        set.remove(intervals[i]);
                        end = intervals[i].e;
                    }
                }
            }
            end = -1;
            layers++;
        }
        return Math.max(layers,0);
    }
}