[LeetCode] Subsets II

Thought: easy DFS.

Code:
public class Solution {
    public static ArrayList<ArrayList<Integer>> result;
    public ArrayList<Integer> cache;
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        result = new ArrayList<ArrayList<Integer>>();
        cache = new ArrayList<Integer>();
        dfs(num, 0, num.length);
        return new ArrayList<ArrayList<Integer>>(new HashSet<ArrayList<Integer>>(result));
    }
    public void dfs(int[] num, int current, int length) {
        if (current == length) {
            result.add(new ArrayList<Integer>(cache));
            return;
        }
        dfs(num, current + 1, length);
        cache.add(num[current]);
        dfs(num, current + 1, length);
        cache.remove(cache.size() - 1);
    }
}

[LeetCode] Restore IP Addresses

Thought: Easy to think of dfs. Then try to code it.

Code:
public class Solution {
    public static ArrayList<String> result;
    public static StringBuilder cache;
    public ArrayList<String> restoreIpAddresses(String s) {
        result = new ArrayList<String>();
        cache = new StringBuilder();
        if (s.length() <= 3) return result;
        dfs(s, 0, 4, 0);
        return result;
    }
    public boolean isValid(String s) {
        if (s.length() == 1) return true;
        else if (s.length() == 2) {
            return s.charAt(0) != '0';
        }else if (s.length() == 3) {
            if (s.charAt(0) == '0') return false;
            if (s.charAt(0) == '1') return true;
            if (s.charAt(0) >= '3') return false;
            else {
                if (s.charAt(1) <= '4') return true;
                if (s.charAt(1) >= '6') return false;
                else {
                    return s.charAt(2) <= '5';
                }
            }
        }else {
            return false;
        } 
    }
    public void dfs(String s, int segment, int target, int current) {
        if (segment == target) {
            if (current == s.length()) {
                cache.delete(cache.length() - 1, cache.length());
                result.add(cache.toString());
                cache.append('.');
                return;
            }else {
                return;
            }
        }
        if (current < s.length() && isValid(s.substring(current, current + 1))) {
            cache.append(s.substring(current, current + 1));
            cache.append('.');
            dfs(s, segment + 1, target, current + 1);
            cache.delete(cache.length() - 2, cache.length());
        }
        if ((current < s.length() - 1) && isValid(s.substring(current, current + 2)))  {
            cache.append(s.substring(current, current + 2));
            cache.append('.');
            dfs(s, segment + 1, target, current + 2);
            cache.delete(cache.length() - 3, cache.length());
        }
        if ((current < s.length() - 2) && isValid(s.substring(current, current + 3))){
            cache.append(s.substring(current, current + 3));
            cache.append('.');
            dfs(s, segment + 1, target, current + 3);
            cache.delete(cache.length() - 4, cache.length());
        }
    }
}

[LeetCode] Triangle

Thought: DP. Use the Array to ensure O(n) space.

Code:
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int[] result = new int[triangle.size()];
        for (int i = 0; i < triangle.size(); i++) {
            result[i] = triangle.get(triangle.size() - 1).get(i);
        }
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.size() - i; j++) {
                result[j] = Math.min(result[j], result[j + 1]) + triangle.get(triangle.size() - i - 1).get(j);
            }
        }
        return result[0];
    }
}

[LeetCode] Palindrome Partitioning II

Thought: DP. f(i) = 1 + min(f(j)) where palindrome(i, j) = true.

Code:
public class Solution {
    public int minCut(String s) {
        if (s.length() == 0) return 0;
        boolean[][] palindrome = new boolean[s.length()][s.length()];
        for (int j = s.length() - 1; j >= 0; j--) {
            for (int i =  0; i <= j; i++) {
                palindrome[j][i] = true;
            }
        }
        for (int j = s.length() - 2; j >= 0; j--) {
            for (int i = j + 1; i < s.length(); i++) {
                palindrome[j][i] = palindrome[j + 1][i - 1] && (s.charAt(j) == s.charAt(i));
            }
        }
        int[] result = new int[s.length() + 1];
        result[0] = -1;
        for (int i = 2; i <= s.length(); i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                if (palindrome[j - 1][i - 1]) {
                    min = Math.min(min, result[j - 1]);
                }
            }
            result[i] = 1 + min;
        }
        return result[s.length()];
    }
}

[LeetCode] Recover Binary Search Tree

Thought: Recursion way is trivial.

Code:

public class Solution {

    public static TreeNode previous, first, second;

    public void recoverTree(TreeNode root) {

        previous = null;

        first = null;

        second = null;

        inorder(root);   

        swap(first, second);

    }

    public void inorder(TreeNode root) {

        if (root == null) return;

        if (root.left != null) inorder(root.left);

        dosomething(root);

        if (root.right != null) inorder(root.right);

    }

    public void dosomething(TreeNode root) {

        if (previous != null && root.val < previous.val) {

            if (first == null) {

                first = previous;

                second = root;

            }else second = root;

        }

        previous = root;

    }

    public void swap(TreeNode first, TreeNode second) {

        int temp = first.val;

        first.val = second.val;

        second.val = temp;

    }

}

Note: There exists a smart traversal method -> Inorder Morris Traversal 
No Recursion, no stack!!!
   
 public void inorder(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        while (cur != null) { 
            if (cur.left == null) { // no left child -> visit and step right
                dosomething(cur);
                cur = cur.right;
            }else {
                TreeNode tmp = cur.left; 
                while (tmp.right != null && tmp.right != cur) { // let tmp step rightest
                    tmp = tmp.right;
                }
                if (tmp.right == null) { // tmp is leaf -> build circle and step left
                    tmp.right = cur;
                    cur = cur.left;
                }else {
                    tmp.right = null; // tmp is already in circle -> destroy circle, visit, and step right
                    dosomething(cur);
                    cur = cur.right;
                }
            }
        }

    }

[LeetCode] Surrounded Regions

Thought: Any point that could not be reached if we started from four edges should be painted as 'X'.

Code:
public class Solution {
    public void solve(char[][] board) {
        int rows = board.length;
        if (rows == 0) return;
        int cols = board[0].length;
        for (int j = 0; j < cols; j++) markFrom(board, 0, j);
        for (int i = 0; i < rows; i++) markFrom(board, i, 0);
        for (int j = 0; j < cols; j++) markFrom(board, rows - 1, j);
        for (int i = 0; i < rows; i++) markFrom(board, i, cols - 1);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'M') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }    
    }
    public void markFrom(char[][] board, int x, int y) {
        int rows = board.length;
        int cols = board[0].length;
        if (x < 0 || x >= rows) return;
        if (y < 0 || y >= cols) return;
        if (board[x][y] == 'X' || board[x][y] == 'M') return;
        board[x][y] = 'M';
        markFrom(board, x - 1, y);
        markFrom(board, x, y - 1);
        markFrom(board, x + 1, y );
        markFrom(board, x, y + 1);
    }
}

[LeetCode] Word Search

Thought:
It is a DFS problem.

Code:
public class Solution {
    public static boolean flag;
    public boolean exist(char[][] board, String word) {
        flag = false;
        int row = board.length;
        int column = board[0].length;
        boolean[][] visited = new boolean[row][column];
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                helper(board, i, j, word, visited);
            }
        }
        
        return flag;        
    }
    public void helper(char[][] board, int row, int column, String word, boolean[][] visited) {
        if (flag) return;
        if (word.length() == 0) {
            flag = true;
            return;        
        }
        if (row >= board.length || column >= board[0].length || row < 0 || column < 0) return;
        if (visited[row][column] || board[row][column] != word.charAt(0)) return;
        visited[row][column] = true;
        helper(board, row - 1, column, word.substring(1), visited);
        helper(board, row, column - 1, word.substring(1), visited);
        helper(board, row + 1, column, word.substring(1), visited);
        helper(board, row, column + 1, word.substring(1), visited); 
        visited[row][column] = false;
    }
}

[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] Search in Rotated Sorted Array

Thought:
Binary Search with different condition.

Code:
public class Solution {
    public int search(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) return mid;
            if (A[start] > A[mid]) {
                if (A[mid] <= target && target <= A[end]) start = mid + 1;
                else end = mid - 1;
            }else {
                if (A[start] <= target && target <= A[mid]) end = mid - 1;
                else start = mid + 1;
            }
        }
        return - 1;
    }
}

[LeetCode] Search in Rotated Sorted Array II

Thought:
Update the condition. This will change the Time to O(n).

Code:
public class Solution {
    public boolean search(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) return true;
            if (A[start] > A[mid]) {
                if (A[mid] <= target && target <= A[end]) start = mid + 1;
                else end = mid - 1;
            }else if (A[start] < A[mid]){
                if (A[start] <= target && target <= A[mid]) end = mid - 1;
                else start = mid + 1;
            }else {
                start++;
            }
        }
        return false;
    }
}

[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] Word Ladder

Thought:
It is a BFS problem.

Code:
import java.util.*;
public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        LinkedList<String> q1 = new LinkedList<String>(); // as a queue
        LinkedList<Integer> q2 = new LinkedList<Integer>(); // as a queue
        q1.offer(start);
        q2.offer(1);
        dict.remove(start);
        while (!q1.isEmpty()) {
            String current = q1.poll();
            int depth = q2.poll();
            if (current.equals(end)) return depth;
            Iterator<String> it = dict.iterator();
            while(it.hasNext()) {
                String tmp = it.next();
                if (adjacent(tmp, current)) {
                    q1.offer(tmp);
                    q2.offer(depth + 1);    
                    it.remove();
                }                
            }
        }
        return 0;
    }
    public boolean adjacent(String a, String b) {
        int result = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) result++;
        }
        return result == 1;
    }
}

[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

[LeetCode] Populating Next Right Pointers in Each Node

Thought:
Recursion.

Code:
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        if (root.left != null) root.left.next = root.right;
        if (root.right != null) root.right.next = root.next != null ? root.next.left : null;
        connect(root.left);
        connect(root.right);            
    }
}

Thought: using a Level Order Traversal will be more clear and common.

Code:
public void connect(TreeLinkNode root) {
        if (root == null) return;
        Queue<TreeLinkNode> q1 = new LinkedList<TreeLinkNode>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        q1.offer(root);
        q2.offer(1);
        while (!q1.isEmpty()) {
            TreeLinkNode current = q1.poll();
            int level = q2.poll();
            if (q2.peek() != null && q2.peek() == level) {
                current.next = q1.peek();
            }
            //do something with current
            if (current.left != null) {
                q1.offer(current.left);
                q2.offer(level + 1);
            }
            if (current.right != null) {
                q1.offer(current.right);
                q2.offer(level + 1);
            }
        }

    }

[LeetCode] Partition List

Thought:
Find the first value that is equal or larger than x. Then put every smaller one before it.

Code:
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
     
        ListNode small = sentinel;
        ListNode large = head;
     
        while (large != null) {
            if (large.val >= x) break;
            small = small.next;
            large = large.next;
        }
     
        if (large == null) return sentinel.next;
     
        while (large.next != null) {
            ListNode tmp = large.next;
            if (tmp.val < x) {
                large.next = tmp.next;
                tmp.next = small.next;
                small.next = tmp;
                small = small.next;
            }else {
                large = large.next;          
            }

        }
     
        return sentinel.next;
    }
}

[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

    }
}

[Algorithms] Dynamic Programming

Dynamic programming & Greedy Algorithm both have the optimal sub-structure.

Dynamic programming usually have several optimal sub-structure at a time and we should choose one or more from them to get the global optimal answer.
It means we should have the sub problem solution first, then choose.

Greedy Algorithm usually have one optimal sub-structure, and we directly choose it and then deal with a smaller problem. Because Greedy ensure us this sub-structure must be in the global optimal answer.


Top-down design method & Bottom-up design method.

Top-down means we have the whole problem, and divide it to several sub-problem, then solve them all.
Bottom-up means we build the global problem directly from small problem, we might do not have the whole picture at all.

Memoization is used for storing solved sub-problem in case they might be solved repeatedly.

DP usually uses Bottom-up method., with memoization.
Greedy usually uses Top-down method, with only one sub-problem.

[Algorithms] Radix Sort

Doing counting sort from the LSB to MSB.

[Algorithms] Counting Sort

All Comparison Sort should take at least O(nlgn) time.

Counting Sort skip the comparison and improve the sorting time to O(n).
There will be extra space O(k) where k is the range of the array to be sorted.

import java.util.Arrays;
 
public static void countingSort(int[] a, int low, int high)
{
    int[] counts = new int[high - low + 1];  

    // this will hold all possible values, from low to high
    for (int x : a)
        counts[x - low]++;  

        // x is some value in array, counts[x - low] stores how many time x appears.
 
    int current = 0;
    for (int i = 0; i < counts.length; i++)
    {
        Arrays.fill(a, current, current + counts[i], i + low);  

        // counts[i] stores how many times i + low appears

        // we should fill counts[i] elements with this value: i + low
        current += counts[i];

        // leap forward by counts[i] steps
    }
}

[Algorithms] QuickSort

public class Quicksort  {
  private int[] numbers;
  private int number;

  public void sort(int[] values) {
    // Check for empty or null array
    if (values ==null || values.length==0){
      return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
  }

  private void quicksort(int low, int high) {
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    int pivot = numbers[low + (high-low)/2];

    // Divide into two lists
    while (i <= j) {
      // If the current value from the left list is smaller then the pivot
      // element then get the next element from the left list
      while (numbers[i] < pivot) {
        i++;
      }
      // If the current value from the right list is larger then the pivot
      // element then get the next element from the right list
      while (numbers[j] > pivot) {
        j--;
      }

      // If we have found a values in the left list which is larger then
      // the pivot element and if we have found a value in the right list
      // which is smaller then the pivot element then we exchange the
      // values.
      // As we are done we can increase i and j
      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }
    // Recursion
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
  }

  private void exchange(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
  }
} 

[Algorithms] Heapsort

Heapsort is a kind of in-place sorting algorithm like insertion sort.
Heapsort is also a O(nlgn) algorithm like merge sort.

7 main functions: first 3 used for sorting, last 4 for priority queue.
Note: in the code A[1..n] instead of A[0..n-1].

Max-Heapify:

• Condition: LEFT(i) & RIGHT(i) are both max-heap. A[i] might violates the rule.
• Code:                                                                                                            public void maxHeapify(int[] A, int i) {
      int left = left(i);
      int right = right(i);
      int largest = 0;
      if (l < heapSize && A[left] > A[i]) largest = left;
      else largest = i;
      if (r < heapSize && A[right] > A[largest]) largest = right;
      if (largest == i) {
          exchange A[i] & A[largest];
          maxHeapify(A, largest);
      }
  }
• Time: O(lgn)

Build-Max-Heap:

• Condition: We want to build a max-heap. The fact is A[n/2+1 to n] is all leaves.
• Code:                                                                                                          public void buildMaxHeap(int[] A) {
      heapSize = A.length;
      for (int i = A.length/2; i > 0; i--) maxHeapify(A, i);
  }
• Time: O(nlgn) BUT actually we will have a more tight Time bound O(n). It is because time cost by maxHeapify to different node is not the same. It is  proportional to O(h) where h is the node's height, and most nodes possess a small height.

Heap-Sort:

• Condition: We move the maximum of the heap to the end of the array. And Adjust the heap.
• Code:                                                                                                           public void heapSort(int[] A) {
      buildMaxHeap(A);
      for (int i = A.length; i > 1; i--) {
          exchange A[1] & A[i];
          heapSize--;
          maxHeapify(A, 1);
      }
  }
• Time: O(nlgn)

Max-Heap-Insert:

• Condition: Insert a key into this heap.
• Code:
  public void maxHeapInsert(A, key) {
      heapSize++;
      A[heapSize] = Integer.MIN_VALUE;
      heapIncreaseKey(A, heapSize, key);
  }
• Time: O(lgn)

Heap-Extract-Max:

• Condition: Remove the Maximum from the heap.
• Code:
  public int heapExtractMax(int[] A) {
      max = A[1];
      A[1] = A[heapSize];
      heapSize--;
      maxHeapify(A, 1);
      return max;   
  }
• Time: O(lgn)

Heap-Increase-Key:

• Condition: Increase some key in this heap.
• Code:
  public void heapIncreaseKey(int[] A, int i, int key) {
      A[i] = key;
      while (i > 1 & A[parent(i)] < A[i]) {
          exchange A[i] & A[parent(i)];
          i = parent(i);
      }
  }
• Time: O(lgn)

Heap-Maximum

• Condition: Return the maximum of the heap.
• Code:                                                                                                            public int heapMaximum(int[] A) {
      return A[1];
  }
• Time: O(1)

[Algorithms] Heap

Heap is Data Structure like a Binary Tree.
If it is stored in an array, then every node's parent, left child, right child could be calculated directly.

Parent(i): return i/2
Left(i): return 2*i
Right(i): return 2*i + 1

Max-Heap: A[parent(i)] >= A[i]                ->use for heap-sort
Min-Heap: A[parent(i)] <= A[i]                 ->use for priority queue

Height of a node: # of edge on the longest path to a leaf.
Height of a heap: height of root.               ->O(lgn)

[Algorithm] BFS

Classical BFS Code is like: 

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u ← G.adjacentVertex(t,e)
13             if u is not marked:
14                  mark u
15                  enqueue u onto Q
16     return none

[LeetCode] Palindrome Partitioning

Thought:
Classical BFS.
The format of BFS is just like this.
The end condition + the forward method.

Code:
public class Solution {
    private static ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    private static ArrayList<String> cache = new ArrayList<String>();
   
    private boolean isPalindrome(String s, int start, int end) {
        int i = start;
        int j = end;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
    public ArrayList<ArrayList<String>> partition(String s) {
        result.clear();
        cache.clear();
        dfs(s, 0);
        return result;
    }
    public void dfs(String s, int depth) {
        if (depth == s.length()) result.add(new ArrayList<String>(cache));
        for (int end = depth; end < s.length(); end++) {
            if (isPalindrome(s, depth, end)) {
                cache.add(s.substring(depth, end + 1));
                dfs(s, end + 1);
                cache.remove(cache.size() - 1);
            }
        }
    }   
}

[LeetCode] Validate Binary Serach Tree

Thought:
Check whether the root is in specific range.

Code:
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public boolean helper(TreeNode root, int min, int max) {
        if (root == null) return true;
        if (root.val >= max || root.val <= min) return false;
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

[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] Pow(x,n)

Thought:
Divide and Conquer.

Code:
public class Solution {
    public double pow(double x, int n) {
        boolean isNeg = false;
        if (n < 0) {
            n = - n;
            isNeg = true;
        }
        return isNeg ? 1 / helper(x, n): helper(x, n);       
    }
    public double helper(double x, int n) {      
       
        if (n == 0) return 1;       
        double result = pow(x, n / 2);
       
        if (n % 2 == 0) return result * result;
        return result * result * x;
    }
   
}

[LeetCode] Unique Binary Search Trees II

Thought:
Recursion.

Code:
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        return generateBST(1,n);
    }
    public ArrayList<TreeNode> generateBST(int start, int end){
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if(start>end){
            result.add(null);
        }else if(start==end){
            result.add(new TreeNode(start));
        }else{
            for(int i=start;i<=end;i++){                
                ArrayList<TreeNode> left = generateBST(start,i-1); 
                ArrayList<TreeNode> right = generateBST(i+1,end);
                for(int k = 0;k<left.size();k++){
                    for(int j = 0;j<right.size();j++){ 
                        TreeNode root = new TreeNode(i);
                        root.left = left.get(k);
                        root.right = right.get(j);
                        result.add(root);
                    }
                }
            }
        }        
        return result; 
    }
}

[LeetCode] Unique Binary Search Trees

Thought:
Recursion. We could also use DP to do faster.

Code:
public class Solution {
    public int numTrees(int n) {
        if (n < 2) return 1;
        if (n == 2) return 2;
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = result + numTrees(i) * numTrees(n - i - 1);
        }
        return result;      
    }
}

[LeetCode] Search a 2D Matrix

Thought:
First find the row and then find the column.

Code:
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
       
        int m = matrix.length, n = matrix[0].length;
       
        int[] a = new int[m];
        for (int i = 0; i < m; i++) a[i] = matrix[i][0];
       
        int row = helper(a, target);
        if (row == -1) return false;
        int col = helper(matrix[row], target);
        return matrix[row][col] == target;
    }
    public int helper (int[] a, int x) {
       
        int start = 0, end = a.length - 1, mid = (a.length - 1) / 2;
        int ret = -1;

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

        return ret;
    }
}

[LeetCode] Rotate Image

Thought:
Rotate from the outside to the inside.

Code:
public class Solution {
    public void rotate(int[][] matrix) {
        int layer = matrix.length;
        for (int i = 0; i < layer / 2; i ++) {
            for (int j = i; j < layer - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[layer - 1 - j][i];
                matrix[layer - 1 - j][i] = matrix[layer - 1 - i][layer - 1 - j];
                matrix[layer - 1 - i][layer - 1 - j] = matrix[j][layer - 1 - i];
                matrix[j][layer - 1 - i] = temp;
            }
        }
        return;
    }
}

[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] Permutations

Thought:
Recursion.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> cache = new ArrayList<Integer>();
        if (num.length == 1) {
            cache.add(num[0]);
            result.add(cache);
            return result;
        }       
        int first = num[0];
        int[] previous = Arrays.copyOfRange(num, 1, num.length);
        ArrayList<ArrayList<Integer>> temp = permute(previous);
        for (ArrayList<Integer> list : temp) {
            for (int i = 0; i <= list.size(); i++) {
                list.add(i, first);
                result.add(new ArrayList<Integer>(list));
                list.remove(i);
            }
        }
        return result;
    }
}

[CTCI 4th Edition] 8.7

Given an infinite number of quarters, dimes, nickels and pennies, write code to calculate the number of ways of representing n cents.

Thought:
f(n, number, base) : to represent n cents using number of base.
g(n) = f(n, 0, 25) + f(n, 1, 25) +....
       = f(n, 0, 10) + f(n, 1, 10) +... + f(n-25, 0, 10) + f(n-25, 1, 10)+...

[LeetCode] N Queen II

Thought:
It is much easier than the previous problem.

Code:
public class Solution {
    int[] cache;
    int result;
    public int totalNQueens(int n) {
        cache = new int[n];
        result = 0;
        placeQueen(0, n);
        return result;
    }
    public boolean check(int row) {
        for (int i = 0; i < row; i++) {
            int dif = Math.abs(cache[i] - cache[row]);
            if (dif == 0 || dif == row - i) return false;
        }
        return true;
    }
    public void placeQueen(int row, int max) {
        if (row == max) {           
            result++;
            return;
        }
        for (int i = 0; i < max; i++) {
            cache[row] = i;
            if (check(row)) placeQueen(row + 1, max);
        }
    }
}

[LeetCode] N Queen

Thought:
It is a classic backtracking problem.
Cache stores the column index of each queen in each row.
Check method check the rules of queens.
We first put the first queen in the first row, and if no rules violated, we put the next row, once we have put N queens, update the result.

Code:
public class Solution {
    int[] cache;
    ArrayList<String[]> result;
    public ArrayList<String[]> solveNQueens(int n) {
        cache = new int[n];
        result = new ArrayList<String[]>();
        placeQueen(0, n);
        return result;
    }
    public boolean check(int row) {
        for (int i = 0; i < row; i++) {
            int dif = Math.abs(cache[i] - cache[row]);
            if (dif == 0 || dif == row - i) return false;
        }
        return true;
    }
    public void placeQueen(int row, int max) {
        if (row == max) {           
            String[] buffer = new String[max];
            for (int i = 0; i < max; i++) {
                StringBuilder temp = new StringBuilder();
                for (int j = 0; j < max; j++) {
                    if (cache[i] == j) temp.append("Q");
                    else temp.append(".");
                }
                buffer[i] = temp.toString();
            }
            result.add(buffer);
            return;
        }
        for (int i = 0; i < max; i++) {
            cache[row] = i;
            if (check(row)) placeQueen(row + 1, max);
        }
    }
}

[LeetCode] Valid Palindrome

Thought:
Skip the special characters.

Code:
public class Solution {
    public boolean isPalindrome(String s) {
        char[] char_set = s.toCharArray();
        if (s.length() == 0) return true;
       
        int first = 0;
        int last = char_set.length - 1;
       
        while (first < last) {
            while ( !Character.isLetterOrDigit(char_set[first]) ) {
                first++;
                if (first == char_set.length - 1) return true;
            }   
            while ( !Character.isLetterOrDigit(char_set[last]) ) {
                last--;
            }
            char tmp1 = Character.toLowerCase(char_set[first]);
            char tmp2 = Character.toLowerCase(char_set[last]);
           
            if( ! (tmp1 == tmp2) ) return false;
            first++;
            last--;
        }
        return true;
    }
}

[LeetCode] Symmetric Tree

Thought:
Recursion.

Code:
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }else {
            return symmetric(root.left, root.right);
        }
    }
    public boolean symmetric(TreeNode n1, TreeNode n2){
        if (n1 == null && n2 == null) {
            return true;
        }else{
            return n1 != null && n2 != null && n1.val == n2.val && symmetric(n1.left,n2.right) && symmetric(n1.right,n2.left);
        }
    }
}