Jump Game

This is a typically DP problem, but using DP method to solve it is not the best way. Firstly, I will post my code for this question. Here, I think if I start from 1st index, and jump the maximum length to next, and recursively, then if end is met, return true, but not, get back to last jump, then jump the (maximum - 1) length again and try. But for this method, it is possible for each element in the range of 1st index, and it might take up to O(n^2) time. Thus it get TLE.

Solution by me:

 public class Solution {  
   public boolean canJump(int[] A) {  
     if(A.length == 0) return false;  
     int[] B = new int[A.length];  
     Arrays.fill(B,-1);  
     return canJump(A,0,B);  
   }  
   public boolean canJump(int[] A, int crntIdx, int[] B){  
     if(crntIdx >= A.length - 1){   
       B[A.length - 1] = 1;   
       return true;  
     }  
     if(B[crntIdx] != -1){   
       return (B[crntIdx] == 0 ? false:true);  
     }  
     if(A[crntIdx] == 0) {  
       B[crntIdx] = 0;  
       return false;  
     }  
     int i = A[crntIdx];  
     while(i > 0 && !canJump(A,crntIdx+i,B)){  
       i--;  
     }  
     if((crntIdx+i) < (A.length - 1)) B[crntIdx+i] = (i == 0 ? 0: 1);  
     // else B[A.length - 1] = (i == 0 ? false: true);  
     else return true;  
     return (B[crntIdx+i] == 0 ? false:true);  
   }   
 }  

Solution by Code Ganker .In his post, he considers the "local maximum and global maximum reach" the elements in array A could get to, and if the global reach is larger than last index, then it must be TRUE.
Thanks to Code Ganker for his brilliant idea.

 public boolean canJump(int[] A) {  
   if(A==null || A.length==0)  
     return false;  
   int reach = 0;  
   for(int i=0;i<=reach&&i<A.length;i++)  
   {  
     reach = Math.max(A[i]+i,reach);  
   }  
   if(reach<A.length-1)  
     return false;  
   return true;  
 }  

Climb Stairs

Simple question, that's why its AC rate is very high.It is almost same as the 1st question in DP chapter of CC 150. Actually, I solved it once. But, as a practice on DP, I still worked on it. Code is shown as below:

 public class Solution {  
   public int climbStairs(int n) {  
     int[] arr = new int[n+1];  
     Arrays.fill(arr,-1);  
     return climbStairs(n, arr);  
   }  
   public int climbStairs(int n, int[] arr) {  
     if(n < 0){  
       return 0;  
     }  
     if(n == 0){  
       return 1;  
     }  
     if(arr[n] != -1) return arr[n];  
     arr[n] = climbStairs(n-1,arr) + climbStairs(n-2,arr);  
     return arr[n];  
   }  
 }  

Combinations

Another DP problem again, but this one is not that hard. Just recursively add elements starting from 1 to n, once tmpList is size of k, then pop out latest added number, and add next one, until number "n" is met. For example, n is 5, k is 3. Firstly, 1,2,3 are added, then tmpList contains 3 elements, now 3 is removed, 4 added, again, 4 removed, 5 added. Once we meet the end, it's time to get back, and 2 is removed, 3 is added, go on over and over again. It could also be implemented by using stack. A little bit tricky part is to find out the upper limit for ith number in tmpList. Lets go back to the example n = 5, k = 3 again. For 1st element in tmpList, its range is from 1 to 3, for 2nd  one, from 2 to 4, 3rd one, from 3 to 5. The formula for upper limit is " n - (k - tmpList.size() )+ 1 ". (k - tmpList.size()) is the number of elements needed.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     if(n < k || n <= 0 || k <= 0) return null;  
     ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();  
     ArrayList<Integer> tmpList = new ArrayList<Integer>();  
     if(n == k){  
       for(int i = 1; i <=n ; i++){  
         tmpList.add(i);  
       }  
       res.add(tmpList);  
     }  
     else {  
       // tmp.add(1);  
       buildComb(n,k,res,tmpList,1);  
     }  
     return res;  
   }  
   public void buildComb(int n, int k, ArrayList<List<Integer>> res, ArrayList<Integer> tmpList, int newElem){  
     if(tmpList.size() == k){  
       ArrayList<Integer> tmpRes = new ArrayList<Integer>();  
       tmpRes.addAll(tmpList);  
       res.add(tmpRes);  
       return;  
     }  
     for(int i = newElem; i<= ( n - (k - tmpList.size() )+ 1 ) ;i++){  
       tmpList.add(i);  
       buildComb(n,k,res,tmpList,i+1);  
       tmpList.remove(tmpList.size()-1);    
     }  
   }  
 }  

Distinct Subsequences

Well, this question is a typically DP one. At first sight, it reminds me of the "longest common subsequence " problem, where a matrix is applied, and one axis is String S, the other is String T. However, I didn't realize that similar method should also be used here. And as a result, one NOT good solution is come up, just like finding all possible ways to get distinct subsequences, while this is not necessary for this question. After checking out code ganker's code and explanation, I am so disappointed at myself. I really need to study DP again.
Anyway, thanks to him for his good post: http://blog.csdn.net/linhuanmars/article/details/23589057

Solution by code ganker:

 public int numDistinct(String S, String T) {  
   if(T.length()==0)  
   {  
     return 1;  
   }  
   if(S.length()==0)  
     return 0;  
   int[] res = new int[T.length()+1];  
   res[0] = 1;  
   for(int i=0;i<S.length();i++)  
   {  
     for(int j=T.length()-1;j>=0;j--)  
     {  
       res[j+1] = (S.charAt(i)==T.charAt(j)?res[j]:0)+res[j+1];  
     }  
   }  
   return res[T.length()];  
 }  

Solution: my version(result is correct, but time complexity is more than O(m*n)), which gets TLE. Just for memory:

 public class Solution {  
   public int numDistinct(String S, String T) {  
     if(S == null || T== null || S.length()<T.length()) return 0;  
     if(S.length() == T.length()){  
       if(S.equals(T)) return 1;  
       else return 0;  
     }    
     int res = 0;  
     ArrayList<ArrayList<Integer>> dict = new ArrayList<ArrayList<Integer>>();  
     buildDict(S,T,dict);  
     int[] endIdx = new int[T.length()];  
     for(int i = 0; i < T.length(); i++){  
       ArrayList<Integer> tmpList = dict.get(i);  
       if(tmpList.isEmpty()) return 0;  
       endIdx[i] = tmpList.size()-1;  
     }  
     res = countNumDistinctSubseq(endIdx,dict,T.length() - 1,S.length());  
     // Use stack, DP  
     // boolean [][] dict = new boolean[T.length()][S.length()];  
     // buildDict(S,T,dict);  
     // int i = T.length() - 1, j = S.length() - 1;  
 //    while(j>=0){  
 //      if(dict[i][j]){  
         // res += countNumSubseq(i,j,dict);  
 //      }  
 //      j--;  
 //    }  
 //      
     return res;  
   }  
   public int countNumDistinctSubseq(String S, int[] endIdx, ArrayList<ArrayList<Integer>> dict, int level){  
     int res = 0;  
     ArrayList<Integer> crntLevel = dict.get(level);  
     // for(Integer crntIdx:crntLevel){  
       res += countNumDistinctSubseq(endIdx,dict,level - 1,S.length());  
     // }  
     return res;  
   }  
   public int countNumDistinctSubseq(int[] endIdx, ArrayList<ArrayList<Integer>> dict, int level, int idxFromPreLevel){  
     int numCrntLevel = 0;  
     // if(level < 0) level=0;  
     int endIdxLevel = endIdx[level];  
     ArrayList<Integer> crntLevel = dict.get(level);       
     if(level == 0){  
       for(int i = endIdxLevel; i >= 0; i--){  
         if(crntLevel.get(i) < idxFromPreLevel){  
           //endIdx[level] = i;  
           numCrntLevel = ++i; break;  
         }  
       }      
       return numCrntLevel;  
     }  
     int res = 0;  
     for(int i = endIdxLevel; i >= 0; i--){  
       if(crntLevel.get(i) < idxFromPreLevel){  
         //endIdx[level] = i;//idxFromPreLevel = crntLevel.get(i);numCrntLevel = ++i; break;  
         res += countNumDistinctSubseq(endIdx,dict,level - 1,crntLevel.get(i));  
       }  
     }  
     // res *= numCrntLevel * countNumDistinctSubseq(endIdx,dict,level - 1,idxFromPreLevel);  
     return res;  
   }  
   public void buildDict(String S, String T, ArrayList<ArrayList<Integer>> dict){  
     for(int i = 0 ; i < T.length() ; i++){  
       ArrayList<Integer> list = new ArrayList<Integer>();  
       for(int j = i; j < S.length();j++){  
         if(T.charAt(i) == S.charAt(j)){  
           list.add(j);  
         }  
       }  
       dict.add(list);  
     }  
   }    
   public void buildDict(String S, String T, boolean[][] dict){  
     for(int i = 0 ; i < T.length() ; i++){  
       for(int j = i; j < S.length();j++){  
         if(T.charAt(i) == S.charAt(j)){  
           dict[i][j] = true;  
         }  
       }  
     }  
   }   
   public int countNumSubseq(int level, int endIdx, boolean[][] dict){  
     int res = 0;  
     if(level==0 ){  
       for(int i = endIdx;i>=0; i--){  
         if(dict[level][i]) res++;  
       }  
     }  
     else{  
       for(int i = endIdx;i>=level;i--){  
         if(dict[level][i]){  
           res += countNumSubseq(level-1,i-1,dict);  
         }  
       }  
     }  
     return res;  
   }  
 }  

Remove Element

Quite easy one. The tricky part may be how to remove element instances so that the whole algorithm takes O(n) time, while in-place. One hint given to us is very helpful: "The order of elements can be changed". So I think that just replace the element we need to remove with a different one, which can be found from end of array. And algorithm stops until start index, or can be also called insert index, meets end index. All elements are traversed just once, so time should be O(n)

 public class Solution {  
   public int removeElement(int[] A, int elem) {  
     if(A.length == 0) return A.length;  
     int startIdx = 0, endIdx = A.length - 1, newLen = A.length;  
     while(startIdx <= endIdx){  
       while(endIdx >= 0 && endIdx!= startIdx && A[endIdx]==elem) {  
         endIdx --;  
         newLen --;  
       }  
       if(endIdx < 0){  
         return newLen;  
       }  
       if(A[startIdx] == elem){  
         A[startIdx] = A[endIdx];  
         endIdx --;  
         newLen --;  
       }  
       startIdx ++;  
     }  
     return newLen;  
   }  
 }  

Partition List

Not difficult one. One thing to be noticed is to keep track of the last smaller node, after which new node with smaller should be inserted. Then each time if a smaller node is found, insert it after the last smaller one, and last smaller is now pointed to its next node.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     if(head == null || head.next == null) return head;  
     ListNode lastSmaller = new ListNode(Integer.MIN_VALUE);  
     ListNode fakeHead = lastSmaller;  
     lastSmaller.next = head;  
     ListNode preNode = lastSmaller;  
     ListNode crntNode = lastSmaller.next;  
     boolean largeFound = false;  
     while(crntNode != null){  
       if(crntNode.val >= x){  
         if(!largeFound) largeFound = true;  
         preNode = preNode.next;  
         crntNode = preNode.next;  
       }  
       else{  
         if(largeFound){  
           preNode.next = crntNode.next;  
           crntNode.next = lastSmaller.next;  
           lastSmaller.next = crntNode;  
           lastSmaller = lastSmaller.next;  
           crntNode = preNode.next;  
         }  
         else{  
           lastSmaller = lastSmaller.next;  
           preNode = preNode.next;  
           crntNode = preNode.next;  
         }  
       }  
     }  
     return fakeHead.next;  
   }  
 }  

Sqrt(x)

Honestly speaking, I am not very familiar with  "numeric calculation" kind question, since I met that sort of problems not often. Last one I worked on is pow(x,n), which I did not find out a valid solution. Thanks to code_ganker for his code and explanation. After reading his post about pow(x,n), I learned that "divide by 2" and "bit manipulation based on 2" are 2 basic useful methods. This time, "divide by 2" is applied to sqrt(x). Actually, my method is like binary search, and the target for search is to find out value res, whose square is smaller than or equal to x, and  (res + 1)^2 is larger than x. However, I did not consider the case where square of res might overflow, thus my submission can not get accepted, until I checked out what code_ganker said. Thanks to him again. Below is his post:

http://blog.csdn.net/linhuanmars/article/details/20089131

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

Sum Root to Leaf Numbers

This question is not difficult. Based on DFS, value of each node is stored and summed up until leaf node is met. Once hit the leaf node, add value of this node, then add this result to resList. As soon as the whole tree is traversed, sum up all the elements in resList. Then we get what we want.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public int sumNumbers(TreeNode root) {  
     if(root == null) return 0;  
     LinkedList<Integer> resList = new LinkedList<Integer>();  
     sumRoot2Leaf(root,0,resList);  
     int res = 0;  
     for(Integer i:resList){  
       res+=i;  
     }  
     return res;  
   }  
   public void sumRoot2Leaf(TreeNode root, int res, LinkedList<Integer> resList){  
     if(root == null) return;  
     if(root.left == null && root.right == null){  
       res = res * 10 + root.val;  
       resList.add(res);  
       return;  
     }  
     sumRoot2Leaf(root.left,res*10 + root.val,resList);  
     sumRoot2Leaf(root.right,res*10 + root.val,resList);  
   }  
 }  

Construct Binary Tree from Inorder and Postorder Traversal

Since I have played with the problem "Construct Binary Tree from Inorder and Preorder Traversal ", it is not a stranger to me. This time, I spent much less effort for it. Now, let me introduce my idea here.

As postorder traversal meet left and right children before root, we may know that the last element in postorder array must be the root. Based on this pattern, I can see that for subtree of root, whatever left one or right one, it must follow this pattern too. And we also know that in inorder array, elements before one particular element are on the left side of it, those after it on the right side, in the tree structure. So we continue this pattern on root's left subtree, and right subtree recursively, if exist.

One thing to notice is that the variable "del". This is the value we need to move leftwards when we are playing with right subtree. Each time we deal with right subtree, indexes of right subtree in inorder array should be minus by one, since root element must be left of right subtree in inorder array, and we use relative index of root to determine which part is left subtree, which is right. This variable "del" might can be used to perform so-called "calibration"

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public TreeNode buildTree(int[] inorder, int[] postorder) {  
     if(inorder.length != postorder.length || inorder.length < 1){  
       return null;  
     }  
     if(inorder.length == 1){  
       return new TreeNode(inorder[0]);  
     }  
     TreeNode root = constructTree(inorder,postorder,0,inorder.length - 1,0);  
     return root;     
   }  
   private TreeNode constructTree(int[] inorder, int[]postorder,int low,int up, int del){  
     if(low<=up){  
       TreeNode root = new TreeNode(postorder[up]);  
        int inIdx = Math.min(up, findInIdx(inorder,postorder[up]) - del);  
       TreeNode left = constructTree(inorder, postorder,low,inIdx - 1,del);  
       TreeNode right = constructTree(inorder, postorder,inIdx,up - 1,del + 1);  
       root.left = left;  
       root.right = right;  
       return root;  
     }  
     else return null;  
   }  
   private int findInIdx(int[] arr, int val){  
     for(int i=0;i < arr.length; i ++){  
       if(arr[i] == val) return i;  
     }  
     return -1;  
   }  
 }  

Populating Next Right Pointers in Each Node

The code below is very straightforward. Just take a look at it, then you can get what I mean.


/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null|| root.left == null) return;
        root.next = null;
        TreeLinkNode head =  root;

        while(head.left != null){
            TreeLinkNode pre = head;
            TreeLinkNode pos = head.next;          
            while(pos != null){
                pre.left.next = pre.right;
                pre.right.next = pos.left;
                pre = pos;
                pos = pos.next;
            }
            pre.left.next = pre.right;
            pre.right.next = null;
            head = head.left;
        }
    }
}

Median of Two Sorted Arrays

This problem seems very simple, or straightforward at first glance. But the time complexity requirement is a little bit tough. Obviously, this should be related to binary search. Follow this route, I began to think how to apply this kind of "Divide and Conquer" method to it. I tried to solve it by looking at each mid element for each array, compare them, and then find out the "range" where median of the whole merged array can be found. For example, if A[AMid] < B[BMid], it means that elements before AMid in array cannot be median, and elements after BMid in array B cannot be median neither. Thus the value of median must be between A[AMid] and B[BMid]. However, this method is not  O(log(m + n)). Actually, I also tried other other methods like combining 2 arrays together, and tried to find median in the array of size ( m+n), but binary search cannot be applied.

Luckily, code_ganker got good solutions. I might came up with similar idea, but I just missed it. Hope that I can learn more from him, and solve similar questions by myself.

Thanks a lot to code_ganker for his explanation. Details about his post is here:
http://codeganker.blogspot.com/2014/02/median-of-two-sorted-arrays-leetcode.html

public double findMedianSortedArrays(int A[], int B[]) {
    if((A.length+B.length)%2==1)
        return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1);
    else
        return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2)  
               +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0;
}
private int helper(int A[], int B[], int i, int i2, int j, int j2, int k)
{
    int m = i2-i+1;
    int n = j2-j+1;
    if(m>n)
        return helper(B,A,j,j2,i,i2,k);
    if(m==0)
        return B[j+k-1];
    if(k==1)
        return Math.min(A[i],B[j]);
    int posA = Math.min(k/2,m);
    int posB = k-posA;
    if(A[i+posA-1]==B[j+posB-1])
        return A[i+posA-1];
    else if(A[i+posA-1]<B[j+posB-1])
        return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);
    else
        return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);
}

Palindrome Partition II

This question is similar to the "palindrome partition I", but easier than that one, since we only need to care about minCut, rather than these possible ways to cut, which takes more spaces.  Dictionary is also necessary. Explanation can be found in the for loop.

BTW, the commented code in minCut(String s) is my previous version. This version can get same result, but it takes more time, which should be O(n^3), thus I get TLE.

Anyway, thanks to code_ganker's good post about "palindrome partition I".

public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() <= 1) return 0;
        
        boolean[][] dict = buildDict(s);
        // int minNum = Integer.MAX_VALUE;
        // for(int i = 0; i < s.length(); i++){ 
        //     if(minNum == 0) return 0;
        //     minNum = Math.min(minNum,i + minCut(s,dict,i));
            
        // }
        // return minNum;
        int[] res = new int[s.length() + 1];
        res[0] = 0;
        for(int i = 0; i < s.length(); i++){
            res[i+1] = i+1;
            for(int j = 0; j <= i; j++){
                if(dict[j][i]) res[i+1] = Math.min(res[i+1],res[j]+1);// be careful, it's dict[j][i],
                // if dict[j][i] true, add one to res[j], i.e. add a new cut based on previous result
            }
        }
        return res[s.length()] - 1;
    }
    
    public boolean[][] buildDict(String s){
        boolean[][] dict = new boolean[s.length()][s.length()];
        
        for(int i = s.length() - 1; i >= 0 ; i --){
            for(int j = i; j < s.length(); j ++){
                if(s.charAt(i)==s.charAt(j) && ((j-i<2)||dict[i+1][j-1])){// briliant method by code ganker
                    dict[i][j] = true;
                }
            }
        }
        return dict;
    }
    public int minCut(String s, boolean[][] dict, int startIdx){

        int tmpCut = Integer.MAX_VALUE;
        
        for(int i = s.length() - 1; i >= startIdx; i --){
            
            if(dict[startIdx][i]){
                if(i == s.length() - 1) return 0;
                tmpCut = Math.min(tmpCut, minCut(s,dict,i+1) + 1);
            }
        }
        return tmpCut;
    }
}

LRU Cache

This question is not difficult once you know what is LRU cache . Check out the link if you don't know. A hashmap is used to record the key and value, and linkedlist can be used as a queue, the least recently used element is always the head one of this queue.

ublic class LRUCache {
   
    private HashMap<Integer,Integer> cacheMap = null;
    private LinkedList<Integer> cacheList = null;
    private int cpct;
   
    public LRUCache(int capacity) {
        cpct = capacity;
        cacheMap = new HashMap<Integer,Integer>();
        cacheList = new LinkedList<Integer>();
    }
   
    public int get(int key) {
       
        if(cacheMap.containsKey(key)) {
            Integer val = cacheMap.get(key);
            cacheList.remove(new Integer(key));
            cacheList.add(key);
            return (int)val;
        }
       return -1;
    }
   
    public void set(int key, int value) {
       
        if(cacheList.size()<cpct){
           
            if(cacheMap.containsKey(key)){
                Integer val = cacheMap.get(key);
               
                cacheList.remove(new Integer(key));
               
                cacheList.add(key);
           
                cacheMap.put(key,value);
            }
            else{
                cacheMap.put(key,value);
                cacheList.add(key);
            }
        }
        else{// cache is full
            if(cacheMap.containsKey(key)){
                Integer val = cacheMap.get(key);
               
                cacheList.remove(new Integer(key));
                cacheList.add(key);
                cacheMap.put(key,value);
            }
            else{
                Integer keyOb = cacheList.poll();
                cacheMap.remove(keyOb);
                cacheMap.put(key,value);
                cacheList.add(key);
            }
        }
           
    }
}