需要记住的算法

理解也没啥用的，就背下来吧

Partition Array

public int partitionArray(int[] nums, int k) {
    if(nums == null || nums.length == 0){
        return 0;
    }

    int left = 0, right = nums.length - 1;
    while (left <= right) {

        while (left <= right && nums[left] < k) {
            left++;
        }

        while (left <= right && nums[right] >= k) {
            right--;
        }

        if (left <= right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            left++;
            right--;
        }
    }
    return left;
}

Merge Sorted Array

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int i = m-1, j = n-1, index = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (A[i] > B[j]) {
            A[index--] = A[i--];
        } else {
            A[index--] = B[j--];
        }
    }
    while (i >= 0) {
        A[index--] = A[i--];
    }
    while (j >= 0) {
        A[index--] = B[j--];
    }
}

Search in Rotated Sorted Array

public int search(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }

    int start = 0;
    int end = A.length - 1;
    int mid;

    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            return mid;
        }
        if (A[start] < A[mid]) {
            // situation 1, red line
            if (A[start] <= target && target <= A[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        } else {
            // situation 2, green line
            if (A[mid] <= target && target <= A[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
    } // while

    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }
    return -1;
}

Linked List Cycle

public Boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode fast, slow;
    fast = head.next;
    slow = head;
    while (fast != slow) {
        if(fast==null || fast.next==null)
            return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
}

Linked List Cycle II

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next==null) {
        return null;
    }

    ListNode fast, slow;
    fast = head.next;
    slow = head;
    while (fast != slow) {
        if(fast==null || fast.next==null)
            return null;
        fast = fast.next.next;
        slow = slow.next;
    }

    while (head != slow.next) {
        head = head.next;
        slow = slow.next;
    }
    return head;
}

Binary Tree Preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
	Stack<TreeNode> stack = new Stack<TreeNode>();
    List<Integer> preorder = new ArrayList<Integer>();

    if (root == null) {
        return preorder;
    }

    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        preorder.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }

    return preorder;
}

Binary Tree Inorder Traversal

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    ArrayList<Integer> result = new ArrayList<Integer>();
    TreeNode curt = root;
    while (curt != null || !stack.empty()) {
        while (curt != null) {
            stack.add(curt);
            curt = curt.left;
        }
        curt = stack.peek();
        stack.pop();
        result.add(curt.val);
        curt = curt.right;
    }
    return result;
}

Binary Tree Postorder Traversal

public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode prev = null; // previously traversed node
    TreeNode curr = root;

    if (root == null) {
        return result;
    }

    stack.push(root);
    while (!stack.empty()) {
        curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            }
        } else if (curr.left == prev) { // traverse up the tree from the left
            if (curr.right != null) {
                stack.push(curr.right);
            }
        } else { // traverse up the tree from the right
            result.add(curr.val);
            stack.pop();
        }
        prev = curr;
    }

    return result;
}

Median of Two Sorted Arrays

public double findMedianSortedArrays(int A[], int B[]) {
    int len = A.length + B.length;
    if (len % 2 == 1) {
        return findKth(A, 0, B, 0, len / 2 + 1);
    }
    return (
        findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)
    ) / 2.0;
}

// find kth number of two sorted array
public static int findKth(int[] A, int A_start,
                           int[] B, int B_start,
                           int k){		
	if (A_start >= A.length) {
		return B[B_start + k - 1];
	}
	if (B_start >= B.length) {
		return A[A_start + k - 1];
	}

	if (k == 1) {
		return Math.min(A[A_start], B[B_start]);
	}

	int A_key = A_start + k / 2 - 1 < A.length
	           ? A[A_start + k / 2 - 1]
	           : Integer.MAX_VALUE;
	int B_key = B_start + k / 2 - 1 < B.length
	           ? B[B_start + k / 2 - 1]
	           : Integer.MAX_VALUE;

	if (A_key < B_key) {
		return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
	} else {
		return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
	}
}

Largest Rectangle in Histogram

 public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }

    Stack<Integer> stack = new Stack<Integer>();
    int max = 0;
    for (int i = 0; i <= height.length; i++) {
        int curt = (i == height.length) ? -1 : height[i];
        while (!stack.isEmpty() && curt <= height[stack.peek()]) {
            int h = height[stack.pop()];
            int w = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max, h * w);
        }
        stack.push(i);
    }

    return max;
}

Topological Sorting

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
    HashMap<DirectedGraphNode, Integer> map = new HashMap();
    for (DirectedGraphNode node : graph) {
        for (DirectedGraphNode neighbor : node.neighbors) {
            if (map.containsKey(neighbor)) {
                map.put(neighbor, map.get(neighbor) + 1);
            } else {
                map.put(neighbor, 1);
            }
        }
    }
    Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>();
    for (DirectedGraphNode node : graph) {
        if (!map.containsKey(node)) {
            q.offer(node);
            result.add(node);
        }
    }
    while (!q.isEmpty()) {
        DirectedGraphNode node = q.poll();
        for (DirectedGraphNode n : node.neighbors) {
            map.put(n, map.get(n) - 1);
            if (map.get(n) == 0) {
                result.add(n);
                q.offer(n);
            }
        }
    }
    return result;
}