[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);
        }
    }
}

[LeetCode] Sum Root to Leaf Numbers

Thought:
Cache stores the current value including the root. It is not a class variable because we want it not change after sum(root.left) and sum(root.right).

Code:
public class Solution {
    public static int result = 0;
    public int sumNumbers(TreeNode root) {
        result = 0;
        int cache = 0;
        sum(root, cache);
        return result;
    }
    public void sum(TreeNode root, int cache) {
        if (root == null) return;
        cache = cache * 10 + root.val;
        if (root.left == null && root.right == null) result = result + cache;
        sum(root.left, cache);
        sum(root.right, cache);
    }
}

Thought: 
Or we could use normal BFS, keeping the add and remove matched.

Code:
public class Solution {
    public static int result = 0;
    public static int cache = 0;
    public int sumNumbers(TreeNode root) {
        result = 0;
        cache = 0;
        sum(root);
        return result;
    }
    public void sum(TreeNode root) {
        if (root == null) return;
        cache = cache * 10 + root.val;
        if (root.left == null && root.right == null) {
            result = result + cache;
        }
        sum(root.left);
        sum(root.right);
        cache = (cache - root.val) / 10;
    }
}

[LeetCode] Search Insert Position

Thought:
It is actually finding how many numbers are smaller than target.

Code:
public class Solution {
    public int searchInsert(int[] A, int target) {
        return helper(A, target, 0, A.length - 1);
    }
    public int helper(int[] A, int target, int start, int end) {   
        if (start >= end) return A[start] >= target ? 0 : 1;
        int mid = (start + end) / 2;
        if (A[mid] == target) return mid - start;
        if (A[mid] > target) return helper(A, target, start, mid - 1);
        return mid - start + 1 + helper(A, target, mid + 1, end);
    }
}

[Cracking the Code Interview 4th Edition] 4.5

Write an algorithm to find the 'next' node (in-order successor) of a given node in a binary search tree where each node has a link to its parent.

Thought:
If it is root, find the leftmost right child.
If it has right child, find the leftmost right child.
If it has no right child and has parent, go up until this node is left child of its parent. Find that parent.

[Cracking the Code Interview 4th edition] 4.2

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Thought: BFS.

Initialize all the points' state as unvisited.
Start.state = visiting
q.in(start)
while(q is not empty) {
       tmp = q.out(start) ;
       for ( v adjacent to tmp) {
             if (v.state is unvisited) {
                   if (v = end) { return true; }
                   else {
                         v.state = visiting;
                         q.in(v);
                   }
             }
       }
       tmp.state = visited;
}
return false;

[Algorithms] Stable marriage problem

This is a matching algorithm.

The link to wikipedia: Stable_marriage_problem

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}

[Algorithms] Brent's algorithm

This is also a cycle detection method.

Its key point is to move into the cycle as fast as possible.

Example: 0 1 2 3 4 5 6 7 3 4 5 6 7 3.....

P = 2^0 = 1, T = 0, H = 0, no match with x[T] within x[T + P]
P = 2^1 = 2, T = 1, H = 1, no match with x[T] within x[T + P]
P = 2^2 = 4, T = 3, H = 3, no match with x[T] within x[T + P]P = 2^3 = 8, T = 7, H = 5, no match with x[T] within x[T + P] -> v = 5;

Let T = 0, H = 5. -> u = 3 because x[3] = x[8].(x[0 + u] = x[v + u])

[Algorithms] Tortoise and hare

This is a cycle detection algorithm. Two pointers are used in this algorithm.
It is also called Floyd's cycle-finding algorithm, this is the link to wikipedia:
Tortoise and the Hare.

If there exists a cycle in X[0..n] from X[u] to X[u+v]. We have X[u] = X[u + kv]

In the first phase, we initialize two pointers, a tortoise with speed 1 and a hare with speed 2. They will meet at some point in the cycle. X[i] = X[2i].

In the second phase, we set the tortoise to X[0], and set the hare speed to 1.They will meet at X[u] = X[2i + u] (because 2i - i must be kv so that they could meet the first time).

Then we could easily find v.

[Cracking the Code Interview 4th Edition] 3.6

Write a program to sort a stack in ascending order.

Thought:
Use another stack r & the original stack is s.

while(s is not empty) {
      val = pop from s
      while (val is smaller than peeking r) {
            push to s(pop from r)
      } 
      push val to r
}

[Cracking the Code Interview 4th Edition] 3.5

Implement a MyQueue class which implements a queue suing two stacks.

Thought:
Queue is a FIFO structure.
Stack is a LIFO structure.

When pushing, we push Node in S1.
When popping or peeking, we check S2, if S2 is not empty, pop from s2.
If S2 is empty, pop s1 and push it into S2 until s1 is empty, and then pop from s2.

[Cracking the Code Interview 4th Edition] 3.2

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? 
Push, pop and min should all operate in O(1) time.

Thought:

1. We could modify the Node class in this stack. We add a local min variable in every Node which stores the local min of all the nodes under & including this one in the stack. 
Thus when pushing, we update the stack, and the top node's min.
When pop, just pop. Min is just peeking the min variable of the top Node.

2. We could change our mind to using another stack who stores the local min.
When pushing, we push the new local min value if and only if the pushed Node's value is smaller or equal to the current local min. That is, if our local min is 3 and we want to push a Node with value 4, the local min stack will not be updated.
When popping, if the popped value is equal to the local min, then pop them respectively.

The first method use extra space within every Node.
The second method use extra space of a stack.

[LeetCode] Same Tree

Thought:
Basic Recursion.

Code:
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[LeetCode] Path Sum II

Thought:
Traditional BFS.
Note that in BFS algorithms, we should always keep the cache.add and the cache.remove in pairs.

Code:
public class Solution {
    public static ArrayList<Integer> cache;
    public static ArrayList<ArrayList<Integer>> result;
   
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        cache = new ArrayList<Integer>();
        result = new ArrayList<ArrayList<Integer>>();
        helper(root, sum);
        return result;       
    }
    public void helper(TreeNode root, int sum) {
        if (root == null) return;
        cache.add(root.val);
        sum = sum - root.val;
        if (root.left == null && root.right == null && sum == 0) result.add(new ArrayList<Integer>(cache));
        if (root.left != null) helper(root.left, sum);
        if (root.right != null) helper(root.right, sum); 
        cache.remove(cache.size() - 1);
    }
}

Code: 2013/8/15
public class Solution {
    public static ArrayList<ArrayList<Integer>> result;
    public static ArrayList<Integer> cache;
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        result = new ArrayList<ArrayList<Integer>>();
        cache = new ArrayList<Integer>();
        dfs(root, sum, 0);
        return result;
    }
    public void dfs(TreeNode root, int target, int sum) {
        if (root == null) return;
        sum += root.val;
        cache.add(root.val);
        if (target == sum && root.left == null && root.right == null) {
            result.add(new ArrayList<Integer>(cache));
        }
        dfs(root.left, target, sum);
        dfs(root.right, target, sum);
        sum -= root.val;
        cache.remove(cache.size() - 1);
    }
    

}