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