Trie Implementation

 public class Trie {  
      static final int ALPHABET_SIZE = 26;  
      static class TrieNode {  
           TrieNode[] children = new TrieNode[ALPHABET_SIZE];  
           boolean isEndOfWord;  
           TrieNode() {  
                isEndOfWord = false;  
                for (int i = 0; i < ALPHABET_SIZE; i++) {  
                     children[i] = null;  
                }  
           }  
      }  
      static TrieNode root;  
      // if not parent, inserts key into trie  
      // if the key is prefix of trie node, just mark leaf node  
      static void insert(String key) {  
           int level;  
           int length = key.length();  
           int index;  
           TrieNode pCrawl = root;  
           for (level = 0; level < length; level++) {  
                index = key.charAt(level) - 'a';  
                if (pCrawl.children[index] == null) {  
                     pCrawl.children[index] = new TrieNode();  
                }  
                pCrawl = pCrawl.children[index];  
           }  
           // mark the last node as leaf  
           pCrawl.isEndOfWord = true;  
      }  
      // Returns true if key presnts in trie, else false  
      static boolean search(String key) {  
           int level;  
           int length = key.length();  
           int index;  
           TrieNode pCrawl = root;  
           for (level = 0; level < length; level++) {  
                index = key.charAt(level) - 'a';  
                if (pCrawl.children[index] == null) {  
                     return false;  
                }  
                pCrawl = pCrawl.children[index];  
           }  
           return pCrawl != null && pCrawl.isEndOfWord;  
      }   
 }  

[LeetCode] #200 Number of Islands

public class Solution {
    public int numIslands(char[][] grid) {
        int result = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return result;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (grid[i][j] != '1') {
            return;
        }
        
        grid[i][j] = '2';
        if (i - 1 >= 0) {
            dfs(grid, i - 1, j);
        }
        if (j - 1 >= 0) {
            dfs(grid, i, j - 1);
        }
        if (i + 1 < grid.length) {
            dfs(grid, i + 1, j);
        }
        if (j + 1 < grid[0].length) {
            dfs(grid, i, j + 1);
        }
    }
}

[LeetCode] 287. Find the Duplicate Number

1. Imagine the array is a linked list. Take the value of each element as a pointer to next element. if there is a duplicate element, there must be a loop in the linked list. Use fast, slow pointer to find the loop. O(n)
2. BitMap - TODO

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

[LeetCode] 289. Game of Life

(1) Add a new 2D array to hold the new state - O(n ^ 2) space
(2) Bit operation - in place

public class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int[][] newState = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = isLive(i, j, board);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = board[i][j] >> 1;
            }
        }
    }
    
    private int isLive(int i, int j, int[][] board) {
        int liveNeighbor = 0;
        for (int m = i - 1; m < board.length && m <= i + 1; m++) {
            for (int n = j - 1; n < board[0].length && n <= j + 1; n++) {
                if (m < 0 || n < 0 || (m == i && n == j)) {
                    continue;
                }
                if ((board[m][n] & 0x0001) == 1) {
                    liveNeighbor++;
                }
            }
        }
        if (liveNeighbor <= 1 || liveNeighbor >= 4) {
            return board[i][j];
        } 
        if (liveNeighbor == 3) {
            return (board[i][j] | 2);
        }
        return (board[i][j] | (board[i][j] << 1));
    }
}

[LeetCode] #148 Sort List

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (head == null) {
        return head;
    }
    return mergeSort(head);
};

var mergeSort = function(head) {
    var pre_mid = findMiddle(head);
    var mid = pre_mid.next;
    
    if (mid != null && mid.next != null) {
        mid = mergeSort(mid);
    }
    pre_mid.next = null;
    if (pre_mid != head) {
        head = mergeSort(head);
    }
    return merge(head, mid);
};

var merge = function(head1, head2) {
    var dummy = new ListNode(-1);
    var cur = dummy;
    while (head1 != null && head2 != null) {
        if (head1.val <= head2.val) {
            cur.next = head1;
            head1 = head1.next;
        } else {
            cur.next = head2;
            head2 = head2.next;
        }
        cur = cur.next;
    }
    if (head1 != null) {
        cur.next = head1;
    }
    if (head2 != null) {
        cur.next = head2;
    }
    return dummy.next;
};

var findMiddle = function(head) {
    var fast = head.next;
    var slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};

[LeetCode] #19 Remove Nth Node From End of List

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    var dummy = new ListNode(-1);
    dummy.next = head;
    
    var fast = head;
    var slow = head;
    var pre = dummy;
    
    for (; n > 0; n--) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }
    pre.next = slow.next;
    
    return dummy.next;
    
};

[LintCode] #102 LinkedList Cycle II

N - distance from head to the node of cycle begins
M - the number of nodes in the cycle
K - the distance from node of cycle begins to the node fast and slow pointer meet

fast = N + xM + K
slow = N + yM + K
fast = 2 slow

=> N + K = (x - 2y) * M

We know when fast and slow meet, they are at Kth node in the cycle, it takes N steps to move from the Kth node in the cycle to the first node in the cycle. How to move this N steps? We know the distance from head to the node where cycle begins is also N. So, we just need to move fast or slow to head and keep step+1 until the two pointers meet.

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {  
        // write your code here
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}