[LeetCode] Search for a Range

Thought:
Find the largest index whose value is not more than target.

Code:
public class Solution {
    public int[] searchRange(int[] A, int target) {
       
        int[] ret = new int[2];
        ret[0] = helper(A, target - 1);
        ret[1] = helper(A, target);
        if (ret[1] != -1 && A[ret[1]] == target) ret[0]++;
        if (ret[0] != -1 && A[ret[1]] != target) ret[0] = ret[1] = -1;

        return ret;
    }   
    public int helper (int[] a, int x) {
        int start = 0;
        int end = a.length - 1;
        int mid = (start + end)/2;
        int result = -1;

        while (start <= end) {
            if (a[mid] > x) {
                end = mid - 1;
                mid = (start + end)/2;
            }else {
                start = mid + 1;
                result = mid;
                mid = (start + end)/2;
            }
        }
        return result;
    }
}

[LeetCode] Sqrt(x)

Thought:
It is a Binary Search.

Code:
public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;       
        int result = 2;
        int tmp = 1;
       
        while ( !(result <= x/result && result + 1 > x/(result + 1)) ) {
            if (result < x/result) {
                tmp = result;
                result = result * result;
            }else {
                result = (result + tmp) / 2;
            }
        }
        return result;
    }
}

[LeetCode] Valid Number

Thought: 
There is a very clear solution using state machines.

Code:
public class Solution {
    public boolean isNumber(String s) {
        char[] tmp = s.toCharArray();
        int[][] trans = {
            { 0 ,0 ,0 ,0 ,0 ,0 },// false
            { 0 ,2 ,3 ,0 ,1 ,4 },// 1
            { 0 ,2 ,5 ,6 ,9 ,0 },// 2
            { 0 ,5 ,0 ,0 ,0 ,0 },// 3
            { 0 ,2 ,3 ,0 ,0 ,0 },// 4
            { 0 ,5 ,0 ,6 ,9 ,0 },// 5
            { 0 ,7 ,0 ,0 ,0 ,8 },// 6
            { 0 ,7 ,0 ,0 ,9 ,0 },// 7
            { 0 ,7 ,0 ,0 ,0 ,0 },// 8
            { 0 ,0 ,0 ,0 ,9 ,0 } // 9
        };
        int i = 0;
        int stat = 1;
        while (i < tmp.length) {
            int type = 0;
            if (tmp[i] >= '0' && tmp[i] <= '9') type = 1;
            else if (tmp[i] == '.') type = 2;
            else if (tmp[i] == 'e') type = 3;
            else if (tmp[i] == ' ') type = 4;
            else if (tmp[i] == '+' || tmp[i] == '-') type = 5;
            stat = trans[stat][type];
            i++;
        }
        return stat == 2 || stat == 5 || stat == 7 || stat == 9;
    }
}

Note:

	type	0	1	2	3	4	5
stat		others	digits	point	e	space	sign
0	FALSE
1	only space
2	digits
3	only point
4	sign
5	digits.
6	e
7	e digits
8	e sign
9	valid space

[CTCI 4th Edition] 19.3

Description: Write an algorithm which computes the number of trailing zeros in n factorial.

Thought: 0 comes from 5 and 2, because in n factorial there will be always enough 2....so every 5 will result in a zero.(25 is 5*5 so result in 2 zeros)

Code:
public static int numZeros(int num) {
    int count = 0;
    for (int i = 5; num / i > 0; i = i * 5) {
        count = count + num / i;
    }
    return count;
}

Explanation:
The first loop we count the first column of 5s in the right side, the second loop count the second column of 5s....

5                  5
10                5
15                5
20                5
25                55
30                5
35                5
40                5
45                5
50                55
55                5
..                  ...
75                55

[CTCI 4th Edition] 19.2

Description: Design an algorithm to check if some one has won a tic-tac-toe game.

Thought: I think the solution CTCI gives is not clear and understandable. Try the following one.

Code: 

public class TripleT {
    enum State{Blank, X, O};
    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;

    void Move(int x, int y, State s){ // someone puts in (x, y)
     if(board[x][y] == State.Blank) board[x][y] = s;
     moveCount++;

     for(int i = 0; i < n; i++){ // check row
      if(board[x][i] != s) break;
      if(i == n-1)  //report win for s
     }

     for(int i = 0; i < n; i++){ // check col
      if(board[i][y] != s) break;
      if(i == n-1)  //report win for s
     }

     if(x == y){  //check diag
      for(int i = 0; i < n; i++){
       if(board[i][i] != s) break;
       if(i == n-1)  //report win for s
      }
     }

        if(x + y == n - 1){  //check anti diag
             for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s) break;
              if(i == n-1)  //report win for s
      }
     }

 
     //check draw
     if(moveCount == (n^2 - 1)) //report draw

    }
}

Thought: There should also be a O(1) solution for every new move. 

public class TripleT {
    enum State{Blank, X, O};
    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;
    int[] result = new int[2 * n + 2];

    void Move(int x, int y, State s){ // someone puts in (x, y)
    
     moveCount++;
        if (s == State.X) {
            result[x]++;
            if (result[x] == n) //report win for X
            result[n + y]++;
            if (result[n + y] == n) //report win for X
            if (x == y) result[2 * n]++;
            if (result[2 * n] == n) //report win for X
            if (x == n - 1 - y) result[2 * n + 1]++;
            if (result[2 * n + 1] == n) //report win for X
        }
        
        if (s == State.O) {
            result[x]--;
            if (result[x] == -n) //report win for O
            result[n + y]--;
            if (result[n + y] == -n) //report win for O
            if (x == y) result[2 * n]--;
            if (result[2 * n] == -n) //report win for O
            if (x == n - 1 - y) result[2 * n + 1]--;
            if (result[2 * n + 1] == -n) //report win for O
        }
 
     //check draw
     if(moveCount == (n^2 - 1)) //report draw

    }
}

[LeetCode] Set Matrix Zeros

Thought:
Constant space means we use the matrix itself to store the setting zero flag.

Code:
public class Solution {
    public void setZeroes(int[][] matrix) {
        
        int row = -1, col = -1, m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row = i;
                    col = j;
                    i = m;
                    j = n;
                }
            }
        }

        if (row == -1 && col == -1) return;
       
        for (int i = row; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][col] = 0;
                    matrix[row][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((matrix[row][j] == 0 && j != col) || (matrix[i][col] == 0 && i != row)) matrix[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i++) matrix[i][col] = 0;
        for (int j = 0; j < n; j++) matrix[row][j] = 0;

    }
}

[LeetCode] Merge Intervals

Thought:
First sort by the start time, then merge.

Code:
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if (intervals.size() == 0) return intervals;
        Collections.sort(intervals, BYSTART);
        ArrayList<Interval> ret = new ArrayList<Interval>();

        int s = intervals.get(0).start;
        int e = intervals.get(0).end;
        for ( Interval itv : intervals) {
            if (e >= itv.start) e = Math.max(e, itv.end);
            else {
                ret.add(new Interval(s, e));
                s = itv.start;
                e = itv.end;
            }
        }
        ret.add(new Interval(s, e));

        return ret;
    }

    private static final Comparator<Interval> BYSTART = new Comparator<Interval>(){
        public int compare (Interval i, Interval j) {
            return new Integer(i.start).compareTo(new Integer(j.start));
        }
    };
}

[LeetCode] Subsets

Thought:
We use a number to represent a subset, every bit in this number is 1 or 0. It means for every elements in the set, it should be either in the subset or not.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int max = 1 << S.length;
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> cache = new ArrayList<Integer>();
            int tmp = i;
            int index = 0;
            while (tmp > 0) {
                if ((tmp & 1) > 0) cache.add(S[index]);
                tmp = tmp >> 1;
                index++;
            }
            result.add(cache);
        }
        return result;
    }
}

[LeetCode] Remove Duplicates from Sorted List II

Thought:
Basically the same with previous problem.

Code: 
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
       
        ListNode flag = new ListNode(0);
        flag.next = head;
       
        ListNode current = head;
        ListNode index = flag;
       
        while (current != null) {
            boolean delete = false;
            while (current.next != null && current.val == current.next.val) {
                current = current.next;
                delete = true;
            }
            if(delete) {               
                index.next = current.next;           
            }else {
                index = index.next;
            }
            current = current.next;
        }
       
        return flag.next;
    }
}

[LeetCode] Remove Duplicates from Sorted List

Thought:
Basically the same with from sorted array.

Code:
 public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode current = head.next;
        ListNode index = head;
        while (current != null) {
            if (current.val == index.val) {
                index.next = current.next;
            }else {
                index = index.next;
            }
            current = current.next;
        }
        return head;
    }
}

[LeetCode] Remove Duplicates from Sorted Array II

Thought:
Use count to trace how many times A[index] has occured.

Code:
public class Solution {
    public int removeDuplicates(int[] A) {
        int index = 0;
        int len = A.length;
        int count = 1;
      
        if(A.length <= 1) return len;
      
        for(int i = 1; i < A.length; i++){
            if(A[i] == A[index]){
                if(count == 2) {
                    len--;
                }else {
                    count++;
                    A[++index] = A[i];
                }               
            }else{
                A[++index] = A[i];
                count = 1;
            }
        }
        return len;
    }
}

[LeetCode] Plus One

Thought:
It is an easy array problem.


Code:
public class Solution {
    public int[] plusOne(int[] digits) {
       
        if(digits.length == 0) return digits;

        int n = digits.length, carry = 1;
        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }

        if (carry == 0) return digits;
        else {
            int[] ret = new int[n + 1];
            ret[0] = 1;
            for (int i = 1; i < n + 1; i++) {
                ret[i] = digits[i - 1];
            }
            return ret;
        }        
    }
}

[LeetCode] Jump Game II

Thought:
start: the starting index, inclusive.
end: the ending index, exclusive.
max: the max index that could be reached.
steps: the steps used.
We start from [start, end) to reach out, update the [start, end) to [end, max + 1)
if end = A.length(Or max >= A.length - 1), return the result.

Code:
public class Solution {
    public int jump(int[] A) {
        int start = 0, end = 1, max = 0, steps = 0;
        while (end < A.length) {
            steps++;
            for (int i = start; i < end; i++) {
                if (A[i] + i >= A.length - 1) return steps;
                max = Math.max(A[i] + i, max);
            }
            start = end;
            end = max + 1;
        }
        return steps;
    }
}

[LeetCode] Jump Game

Thought:
Use an array to store how far you can go from index i. If it is less than zero, it means we could not reach index i.
To go to index i + 1, we could reach i first, or directly leave from some point before i.

Code:
public class Solution {
    public boolean canJump(int[] A) {
        int len = A.length;
        int[] step = new int[len];
        step[0] = 0;
        for (int i = 1; i < len; i++) {
            step[i] = Math.max(step[i - 1], A[i - 1]) - 1;
            if(step[i] < 0) return false;
        }
        return step[len - 1] >= 0;
    }
}

[LeetCode] Insert Interval

Thought:
Scan the ArrayList-> find the start and end-> deal with the case that newinterval is before the start or after the end-> remove s to e-> insert at s-> get the result

Code:
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int s = -1, e = -1;
        for (int i = 0; i < intervals.size(); i++) {
            if (s == -1 && intervals.get(i).end >= newInterval.start) {
                s = i;
            }
            if (intervals.get(i).start <= newInterval.end) {
                e = i;
            }
        }
        if (s == -1) {
            intervals.add(newInterval);
            return intervals;
        }else if (e == -1) {
            intervals.add(0, newInterval);
            return intervals;
        }      
        int start = Math.min(intervals.get(s).start, newInterval.start);
        int end = Math.max(intervals.get(e).end, newInterval.end);
        intervals.subList(s, e+1).clear();
        if (s < intervals.size()) {
            intervals.add(s, new Interval(start, end));
        }else {
            intervals.add(new Interval(start, end));
        }
        return intervals;
    }
}

[LeetCode] First Missing Positive

Thought:
Scan the array, if some element is smaller than the target element(the element that should be at this position), we move this element to the right position.

Code:
public class Solution {
    public int firstMissingPositive(int[] A) {
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] < i + 1 && A[i] != A[A[i] - 1]) {
                int tmp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = tmp;
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
               return i + 1; 
            }
        }
        return A.length + 1;
    }
}

[LeetCode] Edit Distance

Thought:
 http://en.wikipedia.org/wiki/Levenshtein_distance

Code:
public class Solution {
    public int minDistance(String word1, String word2) {
       
        int l1 = word1.length(), l2 = word2.length();        
        int[][] d = new int[l1 + 1][l2 + 1];
        
        for (int i = 0; i < l2 + 1; i++) {
            d[0][i] = i;
        }
        for (int i = 0; i < l1 + 1; i++) {
            d[i][0] = i;
        }
        for (int i = 1; i < l1 + 1; i++) {
            for (int j = 1; j < l2 + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    d[i][j] = d[i - 1][j - 1];
                }else {
                    d[i][j] = Math.min(1 + d[i][j - 1], Math.min(1 + d[i - 1][j], 1 + d[i - 1][j - 1]));
                }
            }
        }
        return d[l1][l2];
    }
}

[LeetCode] Divide Two Integers

Thought:
Bit manipulation. Take care of the Integer.MAX_VALUE and Integer.MIN_VALUE

Code:
public class Solution {
    public int divide(int dividend, int divisor) {
        int a = Math.abs(dividend);
        int b = Math.abs(divisor);
        boolean neg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);  
        if (divisor == 0) return Integer.MAX_VALUE;
        if (divisor == Integer.MIN_VALUE) {
            return dividend == divisor? 1: 0;
        }
        if (dividend == Integer.MIN_VALUE) {
            return neg? divide(dividend + b, b) - 1: 1 - divide(dividend + b, b);
        }        
        int product = b, result = 0;
        while (a >= b) {
            int q = 1;
            while (a - product >= product) {
                q = q << 1;
                product = product << 1;
            }
            a -= product;
            product = b;
            result += q;
        }
        return neg? -result: result;
    }
}

[LeetCode] Climbing Stairs

Thought:
   Nothing easier than this....

Code:
public class Solution {
    public int climbStairs(int n) {
        int[] result = new int[n + 2];
        result[1] = 1;
        for(int i = 2; i < n + 2; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n + 1];
    }
}

[LeetCode] Best Time to Buy and Sell Stock III

Thought: 
Divide the array into two parts, find two profits, and add them together.

Code:
public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 0; i < prices.length ; i++){
            if( forwardProfit(prices,i) + backwardProfit(prices,i) > profit ){
                profit = forwardProfit(prices,i) + backwardProfit(prices,i);
            }
        }
        return profit;     
    }
    public int forwardProfit(int[] prices, int n){
        if(prices.length==0) return 0;
        int min = prices[0] ;
        int profit = 0;
       
        for(int i = 0; i < n; i++){
            if( prices[i] < min ){
                min = prices[i];
            }else if( prices[i] - min > profit ){
                profit = prices[i] - min;
            }
        }
        return profit; 
    }
    public int backwardProfit(int[] prices, int n){
        if(prices.length==0) return 0;
        int max = prices[prices.length-1] ;
        int profit = 0;
       
        for(int i = prices.length - 1; i > n - 1; i--){
            if( prices[i] > max ){
                max = prices[i];
            }else if( max - prices[i] > profit ){
                profit = max - prices[i];
            }
        }
        return profit;
    }
}