Combination Sum

This question is typically a DP one. It might be the simplest one among those DP questions I have solved.

Basic idea is to start from the largest element in candidates array, then try to use this one as many times  as possible to let remainNum get 0. If remainNum gets 0, then remove latest added one, and lets try next number in array, until all numbers are traversed; otherwise, add new number into combination,

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
   
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        if((target <= 0) || (candidates.length == 0) || (target < candidates[0])) return res;
        ArrayList<Integer> comb = new ArrayList<Integer>();
        findCombOfSums(res,comb,candidates, candidates.length - 1, target);
        return res;
    }
   
    public void findCombOfSums(ArrayList<List<Integer>> res, ArrayList<Integer> comb,int[] candidates, int index, int remainNum){
        if(index >= 0 && remainNum >= 0){
            if(remainNum == 0){
               
                ArrayList<Integer> oneRes = new ArrayList<Integer>();
                for(int i = comb.size()-1; i >= 0;i--){// reverse the order
                    oneRes.add(comb.get(i));
                }
                if(!res.contains(oneRes)) res.add(oneRes);

            }
            else{
                    comb.add(candidates[index]);
                    findCombOfSums(res,comb,candidates, index, remainNum - candidates[index]);
                    comb.remove(comb.size()-1);
                    findCombOfSums(res,comb,candidates, index - 1, remainNum);
            }
        }
    }
}

Recover Binary Search Tree

Not a difficult question. The basic idea is to use a queue as a cache to store 2 successive nodes to find the pair where the first one is larger than second one in preorder traversal of this tree. Find 2 pairs like that, or only 1 pair might be found, then swap the values of appropriate nodes. Since res1, res2, and queue are all of size 3, I believe it should meet the constant space requirement.  


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) return;
       
        ArrayList<TreeNode> res1 = new ArrayList<TreeNode>();
        ArrayList<TreeNode> res2 = new ArrayList<TreeNode>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        findOneLargerThanNext(root,queue,null,res1);
        queue.clear();
        findOneLargerThanNext(root,queue,res1,res2);
       
        if(!res1.isEmpty() && !res2.isEmpty()){
            int tmp = res1.get(0).val;
            res1.get(0).val = res2.get(1).val;
            res2.get(1).val = tmp;
        }
        else{
            if(res2.isEmpty()){//swap result in res1
                int tmp = res1.get(0).val;
                res1.get(0).val = res1.get(1).val;
                res1.get(1).val = tmp;               
            }
        }
    }
   
    public void findOneLargerThanNext(TreeNode root,LinkedList<TreeNode> queue,ArrayList<TreeNode> res1,ArrayList<TreeNode> res2){
        if(root == null || res2.size() == 2){
            return;
        }
        findOneLargerThanNext(root.left,queue,res1,res2);
        if(queue.size() == 2){
            queue.remove(0);
        }
        queue.add(root);
        if(queue.size() == 2){
            if( (res1 == null || !res1.containsAll(queue))// res1 is NOT as same as res2
                    && res2.isEmpty() && queue.get(0).val > queue.get(1).val){
                res2.addAll(queue);
                return;
            }
        }
        findOneLargerThanNext(root.right,queue,res1,res2);       
    }
}

Palindrome Partitioning

This question is quite difficult to me, since I seldom deal with too many string problems before. Hope more questions related with this one can help me get better at strings in the future.

Anyway, thanks to code_ganker for his good explanation and his code:
http://blog.csdn.net/linhuanmars/article/details/22777711


Actually, my proposed algorithm is very similar to his. But it took me too much time to think of this idea, I believe things will get better for sure if I played with these "dictionary" kind of things more often. My code will be updated later.

Compared with code_ganker's code, mine looks more complicated, less readable. Hope I can improve this in following days.  

UPDATE: use a stack instead of recursion. But this method took me too much time to deal with the while loop. At first, I thought this should be similar to DFS case. But one thing I need to be aware of is that "visited" should be restored when elements are popped out, since they will be reused in next loop.

public class Solution {
    public List<List<String>> partition(String s) {
        int len = s.length();
        if(s == null) return null;
        LinkedList<List<String>> res = new LinkedList<List<String>>();
        LinkedList<String> sub = new LinkedList<String>();
        for(int i = 0 ; i<len; i++){
            sub.add(String.valueOf(s.charAt(i)));
        }
        res.add(sub);      
        if(len <= 1){

            return res;
        }
       
        ArrayList<ArrayList<Interval>> intervals = new ArrayList<ArrayList<Interval>>();
       
        for(int i = 0;i < len; i ++){
            ArrayList<Interval> tmpInterval = new ArrayList<Interval>();
            intervals.add(tmpInterval);
            int mv = i + 1;
            tmpInterval.add(new Interval(i,i));
            while(mv < len){
                if(isPld(s,i,mv)){
                    tmpInterval.add(new Interval(i,mv));
                }
                mv++;
            }
        }
        addPartitions(res,s,intervals);
        return res;
    }
   
    public boolean isPld(String s, int start, int end){
       
        while(end >= start){
            if(s.charAt(end) == s.charAt(start)){
                start ++;
                end --;
            }else return false;
        }
        return true;
    }
   
   public void addPartitions(List<List<String>> res, String s, ArrayList<ArrayList<Interval>> intervals){
     
     
      int i = 0;
           LinkedList<String> tmpPre = new LinkedList<String>();
           ArrayList<Interval> tmpIntervals = intervals.get(i);
           if(!tmpIntervals.isEmpty()){
               for(int j = 0 ; j < i;j++){
                   tmpPre.add(String.valueOf(s.charAt(j)));
               }
               // similar to DFS
               for(int j = 0; j < tmpIntervals.size();j++){
                   LinkedList<Interval> stack = new LinkedList<Interval>();

                   stack.push(tmpIntervals.get(j));
                   LinkedList<String> tmpRes = new LinkedList<String>();
                 
                   tmpRes.addAll(tmpPre);  
                   while(!stack.isEmpty()){
                            boolean allVisited = true;
                       Interval crntInterval = stack.peek();
                       if(!crntInterval.visited){
                       crntInterval.visited = true;
                       tmpRes.add(s.substring(crntInterval.start, crntInterval.end+1));
                       // crntInterval.visited = true;
                       if(crntInterval.end == s.length() - 1){
                           LinkedList<String> oneRes = new LinkedList<String>();
                           oneRes.addAll(tmpRes);

                           if(!res.contains(tmpRes)){

                               res.add(oneRes);
                           }
                           stack.pop().visited = false;
                           tmpRes.removeLast();
                         
                       }
                       else{
                             
                               for(int n = 0; n < intervals.get(crntInterval.end+1).size(); n++){
                                   if(!intervals.get(crntInterval.end+1).get(n).visited){
                                       stack.push(intervals.get(crntInterval.end+1).get(n));
                                       allVisited = false;
                                   }
                               }
                               if(allVisited){
                                stack.pop().visited = false;
                                tmpRes.removeLast();
                               }
                       }
                       }
                       else{
                            stack.pop().visited = false;
                            tmpRes.removeLast();                        
                       }
                   }
                   setToFalse(intervals);
               }
           }
   }
   
   
    public void setToFalse(ArrayList<ArrayList<Interval>> intervals){
        for(int i = 0; i < intervals.size();i++){
            ArrayList<Interval> tmp = intervals.get(i);
            for(int j = 0; j < tmp.size(); j ++){
                tmp.get(j).visited = false;
            }
        }
    }
}


class Interval {
    public int start;
    public int end;
    public boolean visited = false;
    Interval(int i, int j){start = i; end = j;}
   
}

ZigZag Conversion

Not very difficult. It is a typical "pattern" style question. Once some test cases are verified, you can see that the number of chars in diagonal should be nRows - 2, so every (nRows + nRows - 2) chars should be one pattern. (nRows is number of chars in vertical direction).

public class Solution {
    public String convert(String s, int nRows) {
        if(s == null || s.equals("") || nRows <= 1) return s;
     
        StringBuffer [] rows = new StringBuffer[nRows];
     
        for(int i = 0;i < nRows; i++){
            rows[i] = new StringBuffer();
        }
     
        int rowIdx = 0;
     
        for(int i = 0; i < s.length(); i ++){
         
            int tmp = i%(nRows + nRows - 2);
            if(tmp < nRows){// simple cases, should in the vertical column
                rows[tmp].append(s.charAt(i));
            }
            else{// a little complicated, in the diagonal
                rows[(nRows - 1) - (tmp - (nRows - 1))].append(s.charAt(i));
            }
         
        }
        StringBuffer res = new StringBuffer();
        for(int i = 0 ; i < nRows; i++)res.append(rows[i]);
     
        return res.toString();
    }
}

String to Integer (atoi)

This question is not very difficult. People may get frustrated by the low AC rate of it. But actually, the tricky part is just to take care of some special cases.

Firstly, check out the aoti page in cplusplus.com, which tells me if "bad" cases were met, return 0; secondly, be careful of cases like "-2147483647" ,"-2147483648", "2147483648", whose absolute value is larger than or equal to Integer.MAX_VALUE, or Integer.MIN_VALUE.

To determine whether result might be larger than or equal to Integer.MAX_VALUE in the loop, I use a long integer to store the temp result, so that it will not get overflowed when 2147483648 is the case.


public class Solution {
    public int atoi(String str) {
        if(str == null || str.equals(""))return 0;
        long tmpRes = 0;
        int res = 0;
        int numValChar = 0;
        boolean isNeg = false;
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == ' ' && numValChar == 0){
                continue;
            }
            else{
                if(str.charAt(i) == '-' && numValChar == 0){
                    isNeg = true;
                    numValChar++;
                }
                else{
                    if(str.charAt(i) == '+' && numValChar == 0){
                        numValChar++;continue;
                    }
                    if(str.charAt(i) < '0' || str.charAt(i) > '9'){//invalid characters exist
                        res = (int)tmpRes;
                        return (isNeg? -1*res: res);
                    }
                    else{
                        tmpRes=tmpRes*10+(str.charAt(i) - '0');
                       
                        if(tmpRes > Integer.MAX_VALUE){
                            return (isNeg? Integer.MIN_VALUE : Integer.MAX_VALUE);
                        }
                       
                        numValChar ++;
                    }
                }
            }
        }
        res = (int) tmpRes;
        return (isNeg? -1*res: res);
    }
}

Spiral Matrix II

Simple question. Be careful of the traversal direction, and length change after array is traversed horizontally.

 public class Solution {  
   public int[][] generateMatrix(int n) {  
     int[][] res = new int[n][n];  
     if(n<1) return res;      
     int dir = 0;// 0 means direction is from left to right, 1 means from up to down, 2 right to up,  
             // 3 down to up  
     int length = n;  
     int val = 1, i = 0, j = 0;  
     while(val <= Math.pow(n,2)){  
       int steps = 0;  
       if(dir == 0){// i is fixed, j should increase  
         for(;steps < length && val <= Math.pow(n,2);steps++){ res[i][j+steps] = val; val++;}  
         dir = (++dir)%4;  
         length --;  
         i++;  
         j = j + steps - 1;  
       }else{  
         if(dir == 1){// j is fixed, i should increase  
           for(;steps < length && val <= Math.pow(n,2);steps++){ res[i+steps][j] = val; val++;}  
           dir = (++dir)%4;  
           j--;  
           i = i + steps - 1;  
         }  
         else{  
           if(dir == 2){// i is fixed, j should decrease  
             for(;steps < length && val <= Math.pow(n,2);steps ++){ res[i][j-steps] = val; val++;}  
             dir = (++dir)%4;  
             length --;  
             i --;  
             j = j - (steps - 1);  
           }  
           else{  
              if(dir == 3){// j is fixed, i should decrease  
               for(;steps < length && val <= Math.pow(n,2);steps ++){ res[i - steps][j] = val; val++;}  
               dir = (++dir)%4;  
               j ++;  
               i = i - (steps - 1);  
              }             
           }  
         }  
       }  
     }  
     return res;  
   }  
 }  

UPDATE:

Recently I was preparing for one interview, and happened to work on this question again. Below is another implementation of my algorithm, which is much cleaner:

 public class Solution {  
   public int[][] generateMatrix(int n) {  
     //if(n <= 0) return null;  
     int[][] res = new int[n][n];  
     int m = 1, i = 0, j = 0;  
     int end = n*n;//Math.pow(n,2);  
     while(m <= end){  
       for(j = i; (j <= n - 1 - i) && ( m <= end) ; j++){ res[i][j] = m ; m ++;} j--;  
       for(i++; i <= j && m <= end; i++){ res[i][j] = m ; m ++;} i--;  
       for(j--; (j >= n-1-i) && (m <= end); j--){ res[i][j] = m ; m ++;} j++;  
       for(i--; i >= j+1 && m <= end; i--){ res[i][j] = m ; m ++;} i++;  
     }  
     return res;  
   }  
 }  

Search in Rotated Sorted Array

This question is similar to one in Chapter Sorting, CtCi.  Since I did it before, my code is based on that one. This question is a simpler one than that in CtCi. We are told array is rotated only one time. We need to care only 2 cases: one is that the length of rotated larger part is larger than smaller part, another is that "larger" length is smaller. I suggest you check out answer in CtCi, that one would be better. I will update this post latter.

public class Solution {
    public int search(int[] A, int target) {
        if(A.length == 0) return -1;
        return search(A,target,0,A.length - 1);
    }
   
    public int search(int[] A, int target, int low, int up){
        if(A[low] == target) return low;
        if(A[up] == target) return up;
        if(low<=up){
            int mid = (low + up)/2;
            if(A[mid] == target){
                return mid;
            }else{               
                if(A[mid] < target){
                    if(A[up] > target){
                        return search(A,target,mid + 1, up - 1);
                    }
                    if(A[up] < target && A[mid] > A[low]){
                        int i = mid;
                        while(i < up && A[i] < A[i+1]) i ++;
                        if(i == up) return -1;
                        else return search(A,target, mid+1,i);
                    }
                   
                    if(A[low] < target && A[mid] < A[low]){
                        int i = mid;
                        for (; i >=1; i --){
                            if(A[i - 1] > A[i]) break;
                        }
                        if(i==0) return -1;
                        else return search(A,target,low + 1,i - 1);                  
                    }
                }
               
                else{//A[mid] > target
                    if(A[low] < target){
                        return search(A,target,low + 1, mid - 1);
                    }
                   
                    if(A[up] > target && A[mid] > A[up]){
                        int i = mid;
                        while(i < up && A[i] < A[i+1]) i ++;
                        if(i == up) return -1;
                        else return search(A,target, i+1,up-1);                   
                    }
                   
                    if(A[low] > target && A[mid] < A[up]){
                        int i = mid;
                        while(i > 0 && A[i-1] < A[i]) i--;
                        if(i == 0) return -1;
                        else return search(A,target, i,mid - 1);
                    }
                }
            }
        }
        else{
            return -1;
        }
        return -1;
    }
}

Subsets II

The tricky part of this question is the duplicate numbers in array.

Algorithm for it should be very simple: start from empty subset, set previous result contains this empty subset, add each element in array to every single element in previous result, check whether the newly produced element has been contained, if not, add it to current result. One thing we need to be aware is that the previous result I mention here is result from last loop. And similarly, current result is just result we get in current loop.

Repeat above process until we add a result whose size is equal to length of array. This result should contain all the elements in array, which means no more elements can be added. Thus it is the last subset.

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        if(num.length == 0) return null;
       
        Arrays.sort(num);
        // Note: List<> can not be "new", i.e. it can not be instantiated
        LinkedList<List<Integer>> res= new LinkedList<List<Integer>>();
        LinkedList<List<Integer>> preRes= new LinkedList<List<Integer>>();
        LinkedList<List<Integer>> crntRes= new LinkedList<List<Integer>>();
       
        HashMap<Integer,Integer> numMap = new HashMap<Integer,Integer>();
        initMap(numMap,num);
        LinkedList<Integer> subset = new LinkedList<Integer>();
        res.add(subset);
        preRes.add(subset);
        while(!preRes.isEmpty()){
        for(int t = 0; t < preRes.size(); t++){
          
            for(int i = 0; i < num.length; i++){
                List<Integer> tmpSubset = copy(preRes.get(t));
                int aprTimes = findTimes(tmpSubset,num[i]);
                if(aprTimes < numMap.get(num[i])){
                    tmpSubset.add(num[i]);
                    Collections.sort(tmpSubset,new IntCompare());
                    if(!crntRes.contains(tmpSubset)){
                        crntRes.add(tmpSubset);
                        if(tmpSubset.size() == num.length){
                            res.addAll(crntRes);
                            return res;
                        }
                    }
                }
            }
           
        }
        res.addAll(crntRes);
        preRes = crntRes;
        crntRes = new LinkedList<List<Integer>>();
        }
        return res;
    }
    public int findTimes(List<Integer> subset, int num){
        if(subset.isEmpty()) return 0;
        int times = 0;
        for(int i = 0; i < subset.size();i++){
            if(subset.get(i) == num) times ++;
        }
        return times;
    }
    public void initMap(HashMap<Integer,Integer> numMap,int[] num){
        for(int i = 0; i < num.length; i++){
            if (numMap.containsKey(num[i])){
                int times = numMap.get(num[i]);
                times++;
                numMap.put(num[i], times);
            }
            else numMap.put(num[i], 1);
        }
    }
   
    class IntCompare implements Comparator<Integer>{
        public int compare(Integer i1, Integer i2){
            return i1.compareTo(i2);
        }
    }
   
    public List<Integer> copy( List<Integer> l1){
        LinkedList<Integer> l2 = new LinkedList<Integer>();
        for(int i = 0; i < l1.size();i++) l2.add(l1.get(i));
        return l2;
    }
}

Submission Details

Honestly, this problem might be the easiest one I have solved. Check out the code below, if you get any question, please let me know.

public class Solution {
    public int searchInsert(int[] A, int target) {
        if(A.length == 0) return 0;
       
        for(int i = 0; i < A.length; i++){
            if(A[i] == target) return i;
            else{
                if(A[i] > target){
                    return i;
                }
            }
        }
        return A.length ;
    }
}

Next Permutation

 This question is not hard. Firstly, we look for the first number larger(num[breakIdx]) than its previous one, starting from end of array. Once this number is found, what we need to do is to swap it with next greater number, e.g. num[swapIdx], of num[breakIdx] among numbers we have visited. After this operation, reverse the order of numbers between num[breakIdx] and end of array.

First 2 steps above make sure that result number is larger than before. And since the numbers we have visited are in the decreasing order, thus they form the largest possible number. Thus reverse the order, we can get a increasing order number, which should be the smallest  possible number.


public class Solution {
    public void nextPermutation(int[] num) {
        if(num.length <= 1) return;
        int breakIdx = -1, swapIdx = -1;
        for(int i = num.length - 1; i >= 1 ; i --){
            if(num[i] > num[i-1]){
                breakIdx = i - 1;
                break;
            }
        }
        if(breakIdx != -1){// find the next greater number of num[breakIdx], then swap with num[breakIdx]
            for(int i = breakIdx+1; i <= num.length - 1; i ++){
                if(num[i] <= num[breakIdx]){
                    swapIdx = i - 1;break;
                }
            }
            if(swapIdx == -1){// i in above loop hits the end of num,
                              // i.e. num[breakIdx] is smaller than anyone of rest elements
               
                int tmp = num[breakIdx];
               
                num[breakIdx] = num[num.length - 1];
                num[num.length - 1] = tmp;
               
            }
            else{// swap this number with num[breakIdx]
                int tmp = num[breakIdx];
               
                num[breakIdx] = num[swapIdx];
                num[swapIdx] = tmp;
            }
            breakIdx = breakIdx + 1;
            reverse(num,breakIdx, num.length - 1);
           
        }
        else{
            //reverse the order of the whole num array
            reverse(num,0, num.length - 1);
           
        }
    }
   
   
    public void reverse(int[] num, int left, int right){
        if(left == right) return;
       
        int mid = (left + right)/2;
        int i = left;
        int j = right;
        for(; i <= mid && i < j; ){
            int tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
            i++;
            j--;
        }
    }
}

Merge Intervals

It is quite similar to the question "Insert Interval". What we care is to merge intervals to get minimum number of intervals. For this question, we sort all the intervals first, by the value of start attribute. Then merge each interval with its neighborhood.

Code_Ganker's algorithm is almost the same:

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

He applies Comparator to take use of Collections.sort(), which is a built-in implementation of Quick Sort. But to me, to refresh Quick Sort, I implement it by myself. 

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null) return null;
        if(intervals.size() <= 1) return intervals;
   
        sortByStart(intervals,0,intervals.size() - 1);// sort by the start value of each interval using quick
                                                                            //sort
        int i = 0;
       
        while(i < intervals.size() - 1){// merge each interval with its neighborhood
            if(intervals.get(i).end < intervals.get(i+1).start){
                i++;
            }
            else{
                if(intervals.get(i).end < intervals.get(i+1).end){
                    Interval tmp = new Interval(intervals.get(i).start, intervals.get(i+1).end);
                    intervals.set(i+1,tmp);
                    intervals.remove(i);
                }
                else{
                    intervals.remove(i+1);                   
                }
            }
        }
       
       
        return intervals;
    }
   
    public void sortByStart(List<Interval> intervals, int low, int up){
        int index = partition(intervals, low, up);
       
        if(index - 1 > low ){
            sortByStart(intervals,low,index - 1);
        }
        if(index < up){
            sortByStart(intervals,index,up);
        }
    }
   
    public int partition(List<Interval> intervals, int low, int up){
        int mid = (low + up)/ 2;
        int midVal = intervals.get(mid).start;
        while(low <= up){
            while(intervals.get(low).start < midVal ){
                low++;
            }
           
            while(intervals.get(up).start > midVal){
                up--;  
            }
            if(low <= up){// swap
                Interval tmpInterval = intervals.get(low);
                // int tmpEnd = inervals.get(low).end;
                intervals.set(low,intervals.get(up));
                intervals.set(up,tmpInterval);
                low++;
                up--;
            }
        }
        return low;
    }
}

Remove Duplicates from Sorted Array

Basic idea of my code: variable len is used as a index representing where to put an unique element; once an unique, or differernt element is found, set A[len] to be this value. Since it is a sorted array, we can solve this problem in this way. Totally, time complexity should be O(n).

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null) return 0;
        if (A.length <= 1) return A.length ;
        int crntPre = A[0];
        int len = 1;
        for(int i = 1; i < A.length; i ++){
            if(crntPre != A[i]){
                // set element at swapTo to be A[i]
                A[len] = A[i];
                len ++;
                crntPre = A[i];
            }
        }
        return len;
    }
}

Jump Game II

For this quesiton, Greedy should be an efficient method. However, I took DP at first, which got TLE, even though I tried some improvements. I believe my code can get correct result, but time limit is always exceeded. Since I had some things to deal with, to save time, I checked out solution posted by Code_Ganker, where I got his greedy idea. Excellent! Hope next time I can work this question out by myself.

// My code, get TLE

public class Solution {
    public int jump(int[] A) {
        int minStep = 0;
        int []B = new int[A.length];
        Arrays.fill(B,-1);
        // recursively
        minStep = minJump(A,0,B); //start from 0 ,then recursion.
        return minStep;
    }
   
    public int minJump(int[] A, int idx, int[] B ){
        if(idx >= A.length - 1) {
            return 0;
        }
        if(B[idx] != -1) return B[idx];

        int step = A[idx];
        int minJumpNum = Integer.MAX_VALUE;
        for(int i = step; i >= 1; i --){
            // if(idx + i < A.length)  
            minJumpNum = Math.min(minJumpNum, 1 + minJump(A, idx + i, B));
        }
       
        B[idx] = minJumpNum;
        return minJumpNum;
    }
   
}

// Code_Ganker's code
public class Solution {
public int jump(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int lastReach = 0;
    int reach = 0;
    int step = 0;
    for(int i=0;i<=reach&&i<A.length;i++)
    {
        if(i>lastReach)
        {
            step++;
            lastReach = reach;
        }
        reach = Math.max(reach,A[i]+i);
    }
    if(reach<A.length-1)
        return 0;
    return step;
}
}

For explanation, please check this url out:

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

Implement strStr()

To get accepted is not difficult, it might be due to the time limit is not strict, i.e. O(n * m) can be tolerated in OJ. Since I misunderstood this question, and always failed in one test case, I googled this question, and found very good solution, which takes O(n), called as rolling hash. Basic idea of this algorithm is to hash each segment of haystack, the length is same as needle, and then compare the code with that of needle. The tricky part might be how to implement hash function. BTW, KMP algorithm is reviewed when dealing with this question, good thing.

It is good to find other's blog, by Code_Ganker , where solutions to 151 questions in LeetCode are posted. This is really helpful. Thanks Code_Ganker for his or her post.

//Solution 1 is my code, O(n * m), brute force, lol
public class Solution {
    public String strStr(String haystack, String needle) {
       
        if(haystack == null || needle == null || haystack.length() < needle.length()){
            return null;
        }
        int nLen = needle.length();
        if (nLen == 0) return haystack;
        for(int i = 0; i <= haystack.length() - nLen; i ++){
            if(haystack.substring(i,nLen+i).equals(needle)) return haystack.substring(i);
        }
        return null;
    }
}

Solution 2, contributed by Code_Ganker, O(n): please check this url out :
http://blog.csdn.net/linhuanmars/article/details/20276833

Multiply Strings

This question should be quite easy. Just divide numbers multiplication into 2 steps: 1) multiplication of one digit and one number, 2) sum up results from step 1.

Time complexity should be O(n^2). I am not sure whether there exits better algorithm. If you know one, please let me know. Thanks.

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        StringBuffer res = new StringBuffer();
       
        String prePrdct = null;
       
        String crntPrdct = null;

        for(int i = num1.length() - 1; i >= 0; i--){
           
            crntPrdct = multiply(num2, num1.charAt(i),num1.length() - 1 - i);
            prePrdct = add(crntPrdct,prePrdct);
        }
       
        return prePrdct;
    }
   
    public String multiply(String num1, char num2,int numZeros){
        StringBuffer res = new StringBuffer();
       
        int get = 0;
       
        for(int i = num1.length() - 1; i >= 0 ; i--){
            int prdct = (num1.charAt(i) - '0') * (num2 - '0') + get;
            get = prdct/10;
            res.append(prdct%10);
        }
       
        if(get != 0) res.append(get);
        res = res.reverse();
        for(int i = 0; i < numZeros;i++){
            res.append(0);
        }
        return res.toString();
    }
   
    public String add(String num1, String num2){
        if(num2 == null) return num1;
        StringBuffer res = new StringBuffer();
       
        if(num1.length() > num2.length()){
            int i = num1.length() - 1;
            int j = num2.length() - 1;
            int get = 0;
            for(; j >= 0; ){
                int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
                get = sum / 10;
                res.insert(0,sum%10);
                i --;
                j --;
            }
           
            for(;i>=0;i--){
                int sum = (num1.charAt(i) - '0') + get;
                get = sum/10;
                res.insert(0,sum%10);
            }
            if(get!=0) res.insert(0,get);
        }
        else{
            int i = num1.length() - 1;
            int j = num2.length() - 1;
            int get = 0;
            for(; i >= 0; ){
                int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
                get = sum / 10;
                res.insert(0,sum%10);
                i --;
                j --;
            }
           
            for(;j>=0;j--){
                int sum = (num2.charAt(j) - '0') + get;
                get = sum/10;
                res.insert(0,sum%10);
            }
            if(get!=0) res.insert(0,get);
        }
       
        return res.toString();
    }
}

Sort Colors

Based on the "follow up", this solution is the so-called "one pass with constant space" algorithm.

last0Idx, last1Idx, last2Idx are used to store the index of last 0, 1, and 2, so that when one color is met during traversal, this element can be inserted after one of these indexes. That's why above 3 indexes starts from -1.

After taking a look at "Discuss" community, I find one answer by xianlei, whose idea is similar to mine, but better.
// My solution
public class Solution {
    public void sortColors(int[] A) {
        int last0Idx = -1;
        int last1Idx = -1;
        int last2Idx = -1;
        int i = 0;
        for(;i < A.length; i ++){
            if(A[i] == 0){
                insert(A,last0Idx,i);
                last0Idx++;
                last1Idx++;
                last2Idx++;
            }
            else{
                if(A[i] == 1){
                    insert(A,last1Idx,i);
               
                    last1Idx++;
                    last2Idx++;                  
                }
                else{
                    insert(A,last2Idx,i);

                    last2Idx++;                  
                }
            }

        }
    }
   
    public void insert(int[] A, int insertIdx, int crntIdx){
                int tmp = A[crntIdx];
                for(int i = crntIdx-1;i>=insertIdx+1;i-- ) A[i+1] = A[i];
                A[insertIdx+1] = tmp;
    }
   
}


// By xianlei

public void sortColors(int[] A) { int i=-1, j=-1, k=-1; for(int p = 0; p < A.length; p++) { if(A[p] == 0) { A[++k]=2; A[++j]=1; A[++i]=0; } else if (A[p] == 1) { A[++k]=2; A[++j]=1; } else if (A[p] == 2) { A[++k]=2; } } }

Largest Rectangular Area in a Histogram

Good question. It is easy to get one "common" idea about it, but this kind of solution usually is not a good one. O(n^2) solution is easy to implement, but time complexity is definitely not satisfying.

I am not sure how much last trip could affect me. But this time I failed to come with a good idea to get accepted again. Is it possible to get "stupid" after 2 weeks' relaxing? I don't know. Hopefully, I can do better with following questions.

Alright, come back to this problem. Based on my understanding, the key point is to find out valid left and right bounds for each bar in histogram.

Thanks a lot to geeksforgeeks.org . There are 2 solutions posted in this website. One takes O(nlogn), the other O(n). It is also good to know a new data structure called "Segment Tree". Further details are posted below:

O(nlogn) solution: http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/ 

O(n) solution: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Segment Tree: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

I copied the O(n) solution into OJ, shown as following:

public class Solution {
    public int largestRectangleArea(int[] height) {
        int maxArea = 0;
        int crntArea = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int i = 0;
        for(; i < height.length;){
           
            if(stack.isEmpty() || height[stack.peek()] <= height[i]){
                stack.push(i++);
            }
            else{
                int topIdx = stack.pop();
               
                crntArea = height[topIdx] * (stack.isEmpty() ? i : i - stack.peek() - 1);
               
                if(crntArea > maxArea) maxArea = crntArea;
            }
            // maxArea = Math.max(maxArea,getArea(height,i));
        }
       
        while(!stack.isEmpty()){
                int topIdx = stack.pop();
               
                crntArea = height[topIdx] * (stack.isEmpty() ? i : i - stack.peek() - 1);
               
                if(crntArea > maxArea) maxArea = crntArea;           
        }
        return maxArea;
    }
   
    // public int getArea(int[] height, int idx){
    //     int area = 0,low = idx - 1, up = idx + 1;
    //     while(low >= 0 && height[low]>=height[idx]){
    //         low --;
    //     }
    //     while(up <= height.length - 1 && height[up]>=height[idx]){
    //         up++;
    //     }
    //     area = (up - low - 1) * height[idx];
    //     return area;
    // }
}

Single Number II

This problem is very tricky, especially when you need to solve it without extra spaces. I didn't think of any good idea, what a shame. I even didn't consider bits manipulation as a trial. Anyway, thanks to 1337c0d3r for his or her good explanation, this is really awesome.

public class Solution {
    public int singleNumber(int[] A) {
        // For this question, one point is very important:
        //If you sum the ith bit of all numbers and mod 3,
        //it must be either 0 or 1 due to the constraint of this problem
        //where each number must appear either three times or once.
        //This will be the ith bit of that "single number".
       
        int ones = 0, twos = 0, threes = 0;
        // ones as a bitmask to represent the ith bit had appeared once.
        // twos as a bitmask to represent the ith bit had appeared twice.
        // threes as a bitmask to represent the ith bit had appeared three times.
        for(int i = 0; i < A.length; i ++){
            twos |= ones & A[i];// if the ith bit of ones and A[i] are both 1, it means this bit can appear twice
            ones ^= A[i];// XOR with A[i], clear the bits with same value as A[i], only keep bits with different                                     //values,
                        // since if one bit appear once, and current element does not contain this bit,
                        // then this bit still appear once, similar to other cases
            threes = ones & twos;// only if one bit appears once and twice, then this bit can appear 3rd times
            ones &= ~threes;//clear the ith bit of both ones and twos to 0
            twos &= ~threes;
        }
        return ones;
    }
   
}

Construct Binary Tree from Preorder and Inorder Traversal

This question takes me too much time. Actually, it is not very difficult, but I am not very familiar with preorder and inorder traversal of binary tree, since I learned these things long long ago. Anyway, this is a good time for refreshing tree traversal. Before my trip to L.A., the code was almost done, but got TLE. Yesterday, I started working on it again, and then find out one mistake I made before.  

Now, time for explanation. Firstly, what we should do is to find out left child and right child for each node. We can build the tree if we knew the left and right child of each node, can't we? Since preorder traversal is mid-left-right, if we find one node in preorder array has left child, then its next node in preorder array should be its left child. So the key for left child is to determine whether it has left child. Previously, I wrote a method to do this thing. This method check inorder array from index 0, until current node is met, to find whether there exists unvisited node before current node in inorder array. Because inorder array traverse tree in left-mid-right order, nodes before current node must stand in the left-hand side of current node. If found, next value in preorder is current's left child, if not, just need  to find right child. One key point we should keep in mind is that the nodes before current node in inorder array stand in the left side, but these nodes might be "higher" or "lower" than current node, "higher" ones are "parent" nodes, which have been visited. Only lower ones, those unvisited, can be left child of current node. That is why a hashmap is applied in my code. Luckily, values in arrays are unique. This should be designed for this problem.

For right child, we can add number of nodes in left subtree to current index in preorder array, then we should know where right child locates. Because in preorder array, we visited left subtree first, then visit right child. If sum is larger than length of array, or node in such index has been visited, it means current node has no right child.
  
/**
 * 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[] preorder, int[] inorder) {
        // preorder is used to finally determine which is left or right child, inorder is helper
        if(preorder.length == 0 || inorder.length == 0 || preorder.length != inorder.length) return null;
       
        HashMap<Integer,TreeNode> visitedNode = new HashMap<Integer,TreeNode>();
        TreeNode root = new TreeNode(preorder[0]);
        visitedNode.put(root.val,root);
       for(int i = 0; i < preorder.length-1 && visitedNode.size()!= preorder.length; i ++){
           int crntVal = preorder[i];
           TreeNode newNode;
           if(!visitedNode.containsKey(crntVal)){
                newNode = new TreeNode(crntVal);
                visitedNode.put(crntVal,newNode);
           }
           else{
               newNode = visitedNode.get(crntVal);
           }
           int numIn = findNumLeft(inorder,crntVal,visitedNode);// findNumLeft find out how many left
           //children nodes this node has,
           // i.e. how many nodes contained in the left subtree of current node
           if(numIn > 0){
               TreeNode leftChild = new TreeNode(preorder[i+1]);
               newNode.left = leftChild;
               visitedNode.put(leftChild.val,leftChild);
               int rightIdx = numIn + i+1;
              
               if(rightIdx >= preorder.length || visitedNode.containsKey(preorder[rightIdx])) newNode.right = null;
               else {
                       TreeNode rightChild = new TreeNode(preorder[rightIdx]);
                       newNode.right = rightChild;
                       visitedNode.put(rightChild.val,rightChild);
               }
           }
           else{// if no left child
               newNode.left = null;

               int rightIdx = numIn + i+1;
               if(rightIdx >= preorder.length || visitedNode.containsKey(preorder[rightIdx])) newNode.right = null;// in this case, no right child
               else{
                   TreeNode rightChild = new TreeNode(preorder[rightIdx]);
                   newNode.right = rightChild;
                   visitedNode.put(rightChild.val,rightChild);                  
               }
           }
       }
   
        return root;
    }
   
    public int findNumLeft(int[] arr, int val,HashMap<Integer,TreeNode> visitedNode){
        int count = 0;
        for(int i = 0; i < arr.length; i++){
            if(!visitedNode.containsKey(arr[i])) count ++;
            if(arr[i] == val) return count;
        }
        return count;
    }
   
    // public boolean hasLeft(int[] inorder, TreeNode node,HashMap<Integer,TreeNode> visitedNode){
       
    //     //int idx = find(inorder,node.val);
    //     for(int i = 0 ; inorder[i]!=node.val; i++){
    //         if(!visitedNode.containsKey(inorder[i])) return true;
    //     }
    //     return false;
    // }
}