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

[LintCode] #99 Reorder List

/**
 * 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 head of linked list.
     * @return: void
     */
    public void reorderList(ListNode head) {  
        // write your code here
        if (head == null || head.next == null) {
            return;
        }
        ListNode mid = findMiddle(head);
        ListNode head2 = reverse(mid.next);
        mid.next = null;
        merge(head, head2);
    }
    
    private ListNode findMiddle(ListNode head) {
        if (head == null && head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    
    private static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    private void merge(ListNode head1, ListNode head2) {
        ListNode tmp = new ListNode(0);
        boolean switchToHead2 = false;
        while (head1 != null && head2 != null) {
            if (!switchToHead2) {
                ListNode p = head1.next;
                tmp.next = head1;
                head1 = p;
            } else {
                ListNode p = head2.next;
                tmp.next = head2;
                head2 = p;
            }
            tmp = tmp.next;
            switchToHead2 = !switchToHead2;
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
    }
}

Quick Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        int pivot = A[start + (end - start) / 2];
        int index = partition(A, pivot, start, end);
        if (start < index - 1) {
            quickSort(A, start, index - 1);
        }
        if (index < end) {
            quickSort(A, index, end);
        }
    }
    
    private int partition(int[] A, int pivot, int start, int end) {
        while (start <= end) {
            while (start <= end && A[start] < pivot) {
                start++;
            }
            while (start <= end && A[end] > pivot) {
                end--;
            }
            if (start <= end) {
                swap(A, start, end);
                start++;
                end--;
            }
        }
        return start;
    }
    
    private void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Merge Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        mergeSort(A, 0, A.length - 1);
    }
    
    private void mergeSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);
        merge(A, start, mid, end);
    }
    
    private void merge(int[] A, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (A[i] <= A[j]) {
                temp[k++] = A[i++];
            } else {
                temp[k++] = A[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = A[i++];
        }
        while (j <= end) {
            temp[k++] = A[j++];
        }
        k--;
        while (k >= 0) {
            A[end--] = temp[k--];
        }
    }
}

[LintCode] #102 LinkedList Cycle

/**
 * 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: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {  
        // write your code here
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast != null && slow == fast) {
                return true;
            }
        }
        return false;
    }
}

[LintCode] #96 Partition List

/**
 * 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.
     * @param x: an integer
     * @return: a ListNode 
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        ListNode leftDummy = new ListNode(-1);
        ListNode rightDummy = new ListNode(-1);
        ListNode leftHead = leftDummy;
        ListNode rightHead = rightDummy;
        while (head != null) {
            if (head.val < x) {
                leftHead.next = head;
                leftHead = leftHead.next;
            } else {
                rightHead.next = head;
                rightHead = rightHead.next;
            }
            head = head.next;
        }
        leftHead.next = rightDummy.next;
        rightHead.next = null; //Attn!!!!!
        return leftDummy.next;
    }
}

[LintCode] #113 Remove Duplicates from Sorted List II

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list
     * @return: ListNode head of the linked list
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int val = cur.val;
                while (cur != null && cur.val == val) {
                    pre.next = cur.next;
                    cur = cur.next;
                }
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

努橙的Javascript学习笔记

* Function declaration: A function declaration creates a function that you can call later in your code.
* Function expression: If you put a function where the interpreter would expected to see an expression, then it is treated as expression(aka function expression). In function expression, the name is usually omitted.

* What's the difference of usage between function declaration and function expression?
** The interpreter always looks for variables and function declarations before going through each section of a script, line-by-line. This means that a function created with a function declaration can be called before it has been declared. In function expression, the function is not processed until the interpreter gets to that statement. This means you cannot call this function before interpreter has discovered it.

* IFFE = immediately invoked function expressions

[LintCode] 11. Search Range in Binary Search Tree

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        helper(root, k1, k2, result);
        return result;
    }
    private void helper(TreeNode root, int min, int max, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (root.val > min && root.val < max) {
            helper(root.left, min, max, result);
            result.add(root.val);
            helper(root.right, min, max, result);
        } else if (root.val <= min) {
            if (root.val == min) {
                result.add(root.val);
            }
            helper(root.right, min, max, result);
        } else if (root.val >= max) {
            helper(root.left, min, max, result);
            if (root.val == max) {
                result.add(root.val);
            }
        }
    }
}

[LeetCode] 98. Validate Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean helper(TreeNode root, long min, long 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);
    }
}