import java.util.HashSet;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        String[] strs = {"abc", "bd", "bd", "abc"};
        System.out.println(findFirstDuplicate(strs));
    }
    public static String findFirstDuplicate(String[] strs) {
        if (strs == null || strs.length == 0) {
            return null;
        }
        Set<String> set = new HashSet();
        for (int i = 0; i < strs.length; i++) {
            if (set.contains(strs[i])) {
                return strs[i];
            } else {
                set.add(strs[i]);
            }
        }
        return null;
    }
}

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[index--] = nums1[i--];
            } else {
                nums1[index--] = nums2[j--];
            }
        }
        while (i >= 0) {
            nums1[index--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] a = {1, 3, 7};
        int[] b = {2, 4, 5, 6};
        System.out.println(Arrays.toString(merge(a, 3, b, 4)));
    }
    public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int index = 0;
        int i = 0;
        int j = 0;
        int[] result = new int[m + n];
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                result[index++] = nums1[i++];
            } else {
                result[index++] = nums2[j++];
            }
        }
        while (i < m) {
            result[index++] = nums1[i++];
        }
        while (j < n) {
            result[index++] = nums2[j++];
        }
        return result;
    }
}

You are given a list of size , initialized with zeroes. You have to perform  operations on the list and output the maximum of final values of all the  elements in the list. For every operation, you are given three integers ,  and  and you have to add value  to all the elements ranging from index  to (both inclusive).

Input Format

First line will contain two integers  and  separated by a single space.
Next  lines will contain three integers ,  and  separated by a single space.
Numbers in list are numbered from  to .

Constraints

Output Format

A single line containing maximum value in the updated list.

Sample Input

5 3
1 2 100
2 5 100
3 4 100
Sample Output

200
Explanation

After first update list will be 100 100 0 0 0.
After second update list will be 100 200 100 100 100.
After third update list will be 100 200 200 200 100.
So the required answer will be 200.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] a = new int[m];
        for (int i = 0; i < n; i++) {
            int left = in.nextInt();
            int right = in.nextInt();
            int value = in.nextInt();
            for (int j = left - 1; j < right; j++) {
                a[j] += value;
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            max = Math.max(max, a[i]);
        }
        System.out.println(max);
    }
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] a = new int[m];
        for (int i = 0; i < n; i++) {
            int left = in.nextInt();
            int right = in.nextInt();
            int value = in.nextInt();
            a[left - 1] += value;
            if (right < m - 1) {
                a[right] -= value;
            }
        }
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += a[i];
            a[i] = sum;
            max = Math.max(a[i], max);
        }
        System.out.println(max);
    }
}

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Subscribe to see which companies asked this question

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(' || cur == '{' || cur == '[') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (cur == ')' && stack.pop() != '(') {
                    return false;
                } else if (cur == ']' && stack.pop() != '[') {
                    return false;
                } else if (cur == '}' && stack.pop() != '{') {
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

public static Character getFirstNotRepeatedChar(String input) {

    byte[] flags = new byte[256]; //all is initialized by 0 

    for (int i = 0; i < input.length(); i++) { // O(n)
        flags[(int)input.charAt(i)]++ ;
    }

    for (int i = 0; i < input.length(); i++) { // O(n)
        if(flags[(int)input.charAt(i)] == 1)
            return input.charAt(i);
    }

    return null;
}

import java.util.HashSet;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] words = str.split("\t|-|\\.|:");
//        String[] words = str.split("\\.");
        HashSet<String> set = new HashSet();
        for (int i = 0; i < words.length; i++) {
            if (set.contains(words[i])) {
                System.out.println(words[i]);
            } else {
                set.add(words[i]);
            }
        }
    }
}

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(' || cur == '{' || cur == '[') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (cur == ')' && stack.pop() != '(') {
                    return false;
                } else if (cur == ']' && stack.pop() != '[') {
                    return false;
                } else if (cur == '}' && stack.pop() != '{') {
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

/**
 * Definition of ParentTreeNode:
 *
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root: The root of the tree
     * @param A, B: Two node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here
        List<ParentTreeNode> pathA = getPathToRoot(A);
        List<ParentTreeNode> pathB = getPathToRoot(B);
        int indexA = pathA.size() - 1;
        int indexB = pathB.size() - 1;

        ParentTreeNode lowestAncestor = null;
        while (indexA >= 0 && indexB >= 0) {
            if (pathA.get(indexA) != pathB.get(indexB)) {
                break;
            }
            lowestAncestor = pathA.get(indexA);
            indexA--;
            indexB--;
        }
        return lowestAncestor;
    }
    private static List<ParentTreeNode> getPathToRoot(ParentTreeNode node) {
        List<ParentTreeNode> path = new ArrayList();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        return path;
    }
}

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    List<TreeNode> children = new ArrayList();
    public TreeNode(int v) {
        val = v;
    }
}
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.children.add(new TreeNode(2));
        root.children.add(new TreeNode(3));
        root.children.get(0).children.add(new TreeNode(4));
        System.out.println(getLowestCommonAncestor(root, root, root).val);
        System.out.println(getLowestCommonAncestor(root, root.children.get(0), root.children.get(0).children.get(0)).val);
    }
    public static TreeNode getLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        List<TreeNode> pPath = new ArrayList();
        List<TreeNode> qPath = new ArrayList();
        getPath(root, p, pPath);
        getPath(root, q, qPath);
        //
        if (pPath.isEmpty() && qPath.isEmpty()) {
            return null;
        }
        int index = 0;
        TreeNode result = null;
        while (index < pPath.size() && index < qPath.size()) {
            if (pPath.get(index) == qPath.get(index)) {
                result = pPath.get(index);
                index++;
            } else {
                break;
            }
        }
        return result;
    }
    public static boolean getPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        path.add(root);
        if (root == target) {
            return true;
        }
        boolean found = false;
        List<TreeNode> list = root.children;
        for (TreeNode n : list) {
            if (found) {
                break;
            }
            found = getPath(n, target, path);
        }
        if (!found) {
            path.remove(path.size() - 1);
        }
        return found;
    }
}

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    List<TreeNode> children = new ArrayList();
    public TreeNode(int v) {
        val = v;
    }
}
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.children.add(new TreeNode(2));
        root.children.add(new TreeNode(3));
        root.children.get(0).children.add(new TreeNode(4));
        System.out.println(getLowestCommonAncestor(root, root, root).val);
        System.out.println(getLowestCommonAncestor(root, root.children.get(0), root.children.get(0).children.get(0)).val);
    }
    public static TreeNode getLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        List<TreeNode> pPath = new ArrayList();
        List<TreeNode> qPath = new ArrayList();
        boolean pFlag = getPath(root, p, pPath);
        boolean qFlag = getPath(root, q, qPath);
        //
        if (pPath.isEmpty() && qPath.isEmpty()) {
            return null;
        }
        int index = 0;
        TreeNode result = null;
        while (index < pPath.size() && index < qPath.size()) {
            if (pPath.get(index) == qPath.get(index)) {
                result = pPath.get(index);
                index++;
            } else {
                break;
            }
        }
        return result;
    }
    public static boolean getPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        path.add(root);
        if (root == null) {
            return false;
        }
        if (root == target) {
            return true;
        }
        boolean found = false;
        List<TreeNode> list = root.children;
        for (TreeNode n : list) {
            if (found) {
                break;
            }
            found = getPath(n, target, path);
        }
        if (!found) {
            path.remove(path.size() - 1);
        }
        return found;
    }
}

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    List<TreeNode> children = new ArrayList();
    public TreeNode(int v) {
        val = v;
    }
}
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.children.add(new TreeNode(2));
        root.children.add(new TreeNode(3));
        root.children.get(0).children.add(new TreeNode(4));
        System.out.println(getLowestCommonAncestor(root, root, root));
        System.out.println(getLowestCommonAncestor(root, root.children.get(0), root.children.get(0).children.get(0)).val);
    }
    public static TreeNode getLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        List<TreeNode> pPath = new ArrayList();
        List<TreeNode> qPath = new ArrayList();
        boolean pFlag = getPath(root, p, pPath);
        boolean qFlag = getPath(root, q, qPath);
        //
        if (!pFlag || !qFlag) {
            return null;
        }
        if (pPath.isEmpty() && qPath.isEmpty() || pPath.size() == 1 || qPath.size() == 1) {
            return null;
        }
        int index = 0;
        TreeNode result = null;
        while (index < pPath.size() && index < qPath.size()) {
            if (pPath.get(index) == qPath.get(index)) {
                result = pPath.get(index);
                index++;
            } else {
                break;
            }
        }
        return result;
    }
    public static boolean getPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        path.add(root);
        if (root == null) {
            return false;
        }
        if (root == target) {
            return true;
        }
        boolean found = false;
        List<TreeNode> list = root.children;
        for (TreeNode n : list) {
            if (found) {
                break;
            }
            found = getPath(n, target, path);
        }
        if (!found) {
            path.remove(path.size() - 1);
        }
        return found;
    }
}

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        // dp[i][j] : 前i个物品是否能够组成j价值
        boolean[][] dp = new boolean[2][m + 1];
        dp[0][0] = true;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < m + 1; j++) {
                dp[(i + 1) % 2][j] = dp[i % 2][j];
                if (j >= A[i] && dp[i % 2][j - A[i]]) {
                    dp[(i + 1) % 2][j] = true;
                }
            }
        }
        for (int j = m; j >= 0; j--) {
            if (dp[(A.length) % 2][j]) {
                return j;
            }
        }
        return 0;
    }
}

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] max = new int[len];
        int[] min = new int[len];
        max[0] = min[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = Math.min(nums[i], Math.min(min[i - 1] * nums[i], max[i - 1] * nums[i]));
            max[i] = Math.max(nums[i], Math.max(min[i - 1] * nums[i], max[i - 1] * nums[i]));
            result = Math.max(result, max[i]);
        }
        return result;
    }
}

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        // write your code here
        if (null == matrix || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[2][n]; // dp[i][j]表示以i，j结尾能达到的最大的正方形的边长
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 1) {
                max = 1;
            }
            dp[i % 2][0] = matrix[i][0];
        }
        for (int j = 0; j < n; ++j) {
            if (dp[0][j] == 1) {
                max = 1;
            }
            dp[0][j] = matrix[0][j];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j - 1], Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1])) + 1;.
                } else {
                    dp[i % 2][j] = 0;
                }
                max = Math.max(max, dp[i % 2][j]);
            }
        }
        return max * max;
    }
}

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the poli

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(robber1(nums, 0, nums.length - 2), robber1(nums, 1, nums.length - 1));
    }
    public int robber1(int[] nums, int st, int ed) {
        int []res = new int[2];
        if(st == ed)
            return nums[ed];
        if(st+1 == ed)
            return Math.max(nums[st], nums[ed]);
        res[st%2] = nums[st];
        res[(st+1)%2] = Math.max(nums[st], nums[st+1]);

        for(int i = st+2; i <= ed; i++) {
            res[i%2] = Math.max(res[(i-1)%2], res[(i-2)%2] + nums[i]);

        }
        return res[ed%2];
    }
}

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length <= 2) {
            return Math.max(nums[0], nums[nums.length - 1]);
        }
        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i % 2] = Math.max(dp[(i - 1) % 2], nums[i] + dp[(i - 2) % 2]);
        }
        return dp[(nums.length - 1) % 2];
    }
}

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.

 Notice

You can assume that there is at least one topological order in the graph.

Have you met this question in a real interview? Yes
Clarification
Learn more about representation of graphs

Example
For graph as follow:

picture

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
     public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList();
        if (graph == null || graph.size() == 0) {
            return result;
        }
        HashMap<DirectedGraphNode, Integer> map = new HashMap();
        //map 用来记录那些成为了别人邻居的点作为多少个邻居，也就是他的入度是多少。
        for (DirectedGraphNode g : graph) {
            for (DirectedGraphNode n : g.neighbors) {
                if (map.containsKey(n)) {
                    map.put(n, map.get(n) + 1);
                } else {
                    map.put(n, 1);
                }
            }
        }
        Queue<DirectedGraphNode> queue = new LinkedList();
        for (DirectedGraphNode g : graph) {
            if (!map.containsKey(g)) {
                //不在map里面，说明他的度为0
                result.add(g);
                queue.add(g);
            }
        }
        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode n : node.neighbors) {
                map.put(n, map.get(n) - 1);
                if (map.get(n) == 0) {
                    result.add(n);
                    queue.add(n);
                }
            }
        }
        return result;
    }
}

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

public class Solution {
    /**
     * @param num an integer
     * @return true if num is an ugly number or false
     */
    public boolean isUgly(int num) {
        if (num <= 0) return false;
        if (num == 1) return true;  

        while (num >= 2 && num % 2 == 0) num /= 2;
        while (num >= 3 && num % 3 == 0) num /= 3;
        while (num >= 5 && num % 5 == 0) num /= 5;  

        return num == 1;
    }
}

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    /**
     * @author ChunyueLi--Big Data Scientist
     * @答案和思路：这道题也是希望利用二分思想来做，每一次找到排除掉的那一半。
     * @复杂度：log(len)
     */
    public static void main(String[] args) {
//        int[] nums1 = {1, 2, 3, 4, 4};
//        int[] nums2 = {0, 0, 4, 4, 4};
//        int[] nums3 = {0, 0, 4, 4, 4};
        int[] nums1 = {1, 12, 13};
        int[] nums2 = {6, 7};
        int[] nums3 = {0, 3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2, nums3));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2, int[] nums3) {
        if (nums1 == null || nums2 == null || nums3 == null) {
            return -1;
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len3 = nums3.length;
        int len = len1 + len2 + len3;
        if (len % 2 == 1) {
            return findKthFromThreeArray(nums1, 0, nums2, 0, nums3, 0, len / 2 + 1);
        } else {
            System.out.println("here");
            System.out.println(findKthFromThreeArray(nums1, 0, nums2, 0, nums3, 0, len / 2));
            System.out.println(findKthFromThreeArray(nums1, 0, nums2, 0, nums3, 0, len / 2 + 1));
            return (findKthFromThreeArray(nums1, 0, nums2, 0, nums3, 0, len / 2) + findKthFromThreeArray(nums1, 0, nums2, 0, nums3, 0, len / 2 + 1)) / 2.0;
        }
    }
    private static double findKthFromThreeArray(int[] a, int aIndex, int[] b, int bIndex, int[] c, int cIndex, int k) {
        //如果其中一个走完了就退化成两个数组找
        if (aIndex >= a.length) {
            return findKthFromTwoArray(b, bIndex, c, cIndex, k);
        }
        if (bIndex >= b.length) {
            return findKthFromTwoArray(a, aIndex, c, cIndex, k);
        }
        if (cIndex >= c.length) {
            return findKthFromTwoArray(a, aIndex, b, bIndex, k);
        }
        if (k == 1) {
            return Math.min(a[aIndex], Math.min(b[bIndex], c[cIndex]));
        }
        if (k == 2) { //这是最关键的地方，因为如果k == 2不进行判断，那么下一次移位就是0，会导致死循环，从而爆栈。
            ArrayList<Integer> temp = new ArrayList();
            for (int i = 0; i < 2; i++) {
                if (aIndex < a.length) {
                    temp.add(a[aIndex++]);
                }
                if (bIndex < b.length) {
                    temp.add(b[bIndex++]);
                }
                if (cIndex < c.length) {
                    temp.add(c[cIndex++]);
                }
            }
            Collections.sort(temp);
            return temp.get(1);
        }
        int aMid = aIndex + k / 3 - 1 < a.length ? a[aIndex + k / 3 - 1] : Integer.MAX_VALUE;
        int bMid = bIndex + k / 3 - 1 < b.length ? b[bIndex + k / 3 - 1] : Integer.MAX_VALUE;
        int cMid = cIndex + k / 3 - 1 < c.length ? c[cIndex + k / 3 - 1] : Integer.MAX_VALUE;
        if (aMid < bMid) {
            if (aMid < cMid) {
                return findKthFromThreeArray(a, aIndex + k / 3, b, bIndex, c, cIndex, k - k / 3);
            } else {
                return findKthFromThreeArray(a, aIndex, b, bIndex, c, cIndex + k / 3, k - k / 3);
            }
        } else {
            if (bMid < cMid) {
                return findKthFromThreeArray(a, aIndex, b, bIndex + k / 3, c, cIndex, k - k / 3);
            } else {
                return findKthFromThreeArray(a, aIndex, b, bIndex, c, cIndex + k / 3, k - k / 3);
            }
        }
    }
    private static double findKthFromTwoArray(int[] a, int aIndex, int[] b, int bIndex, int k) {
        if (aIndex >= a.length) {
            return b[bIndex + k - 1];
        }
        if (bIndex >= b.length) {
            return a[aIndex + k - 1];
        }
        if (k == 1) {
            return Math.min(a[aIndex], b[bIndex]);
        }
        int aMid = aIndex + k / 2 - 1 < a.length ? a[aIndex + k / 2 - 1] : Integer.MAX_VALUE;
        int bMid = bIndex + k / 2 - 1 < b.length ? b[bIndex + k / 2 - 1] : Integer.MAX_VALUE;
        if (aMid < bMid) {
            return findKthFromTwoArray(a, aIndex + k / 2, b, bIndex, k - k / 2);
        } else {
            return findKthFromTwoArray(a, aIndex, b, bIndex + k / 2, k - k / 2);
        }
    }
}

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> results = new ArrayList();
        if (s == null || s.length() == 0) {
            return results;
        }
        ArrayList cur = new ArrayList();
        partition(results, s, 0, cur);
        return results;
    }
    private static void partition(List<List<String>> results, String s, int start, List<String> path) {
        if (start == s.length()) {
            results.add(new ArrayList(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (isPalindrome(sub)) {
                path.add(sub);
                partition(results, s, i, path);
                path.remove(path.size() - 1);
            }
        }
    }
    private static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int left = nums[i] - 1;
            while (set.contains(left)) {
                set.remove(left);
                left--;
            }
            int right = nums[i] + 1;
            while (set.contains(right)) {
                set.remove(right);
                right++;
            }
            result = Math.max(result, right - left - 1);
        }
        return result;
    }
}

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Have you met this question in a real interview? Yes
Example
If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

    20
   /  \
  8   22
 / \
4   12

/**
 * 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();
        if (root == null) {
            return result;
        }
        searchRange(root, k1, k2, result);
        return result;
    }
    private static void searchRange(TreeNode root, int k1, int k2, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }
        if (root.val >= k1 && root.val <= k2) {
            searchRange(root.left, k1, k2, result);
            result.add(root.val);
            searchRange(root.right, k1, k2, result);
        } else if (root.val > k2) {
            searchRange(root.left, k1, k2, result);
        } else {
            searchRange(root.right, k1, k2, result);
        }
    }
}

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

public class Solution {
    public String reverseString(String s) {
        char[] c = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            char temp = c[left];
            c[left] = c[right];
            c[right] = temp;
            left++;
            right--;
        }
        return new String(c);
    }
}

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        int result = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[mid] <= nums[nums.length - 1]) {
                result = nums[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        int result = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[mid] <= nums[nums.length - 1]) {
                result = nums[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        int result = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[nums.length - 1]) {
                result = nums[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int x = matrix.length - 1;
        int y = 0;
        while (y < matrix[0].length && x >= 0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                x--;
            } else {
                y++;
            }
        }
        return false;
    }
}

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        // find row
        int row = 0;
        int low = 0;
        int high = matrix.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                row = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        // find target
        int left = 0;
        int right = matrix[0].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                left =  mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

// version 1: Merge Sort
public class Solution {
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }    

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if (head1 != null) {
            tail.next = head1;
        } else {
            tail.next = head2;
        }

        return dummy.next;
    }

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

        ListNode mid = findMiddle(head);

        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);

        return merge(left, right);
    }
}

// version 2: Quick Sort 1
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = findMedian(head); // O(n)

        ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
        ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
        ListNode middleDummy = new ListNode(0), middleTail = middleDummy;
        while (head != null) {
            if (head.val < mid.val) {
                leftTail.next = head;
                leftTail = head;
            } else if (head.val > mid.val) {
                rightTail.next = head;
                rightTail = head;
            } else {
                middleTail.next = head;
                middleTail = head;
            }
            head = head.next;
        }

        leftTail.next = null;
        middleTail.next = null;
        rightTail.next = null;

        ListNode left = sortList(leftDummy.next);
        ListNode right = sortList(rightDummy.next);

        return concat(left, middleDummy.next, right);
    }

    private ListNode findMedian(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode concat(ListNode left, ListNode middle, ListNode right) {
        ListNode dummy = new ListNode(0), tail = dummy;

        tail.next = left; tail = getTail(tail);
        tail.next = middle; tail = getTail(tail);
        tail.next = right; tail = getTail(tail);
        return dummy.next;
    }

    private ListNode getTail(ListNode head) {
        if (head == null) {
           return null;
        } 

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

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

public class Solution{
    //思路：
    //localProfit[i][j]：到了第i天，并且第i天进行了第j次交易的maxProfit
    //globalProfit[i][j]:到了第i天，进行了j次交易的maxProfit
    //note：为什么要分两个？答：首先一定要有的是globalProfit[i][j]。因为这个就是要求的答案
    //但是这个答案分为两种方案：1，是i天不做交易，那么他就==global[i-1][j];
    //一种是，i天做交易。那么就要用一个i天做交易得到的maxProfit。
    //然后最后max两种情况。
    //【错误】注意，n天最多交易n/2次，当k很大，大于n/2要单独判断（相当于第一题，随便几次都可以），并且不要忘记那时候就要return
    public int maxProfit(int k, int[] prices){

        int n = prices.length;
        if(k <= 0 || n == 0) return 0;
        if(k >= n / 2){
            int max = 0;
            for(int i = 1; i < n; i++){
                max += Math.max(0, prices[i] - prices[i - 1]);
            }
            return max;
        }
        int[][] localProfit = new int[n][k+1];
        int[][] globalProfit = new int[n][k + 1];
        //最重要的部分，从这里开始：
        for(int j = 1; j <= k; ++j){
            for(int i = 1; i < n; ++i){//天数是从0开始的。localProfit[0][0] = 0;
                localProfit[i][j] = Math.max(localProfit[i - 1][j] + prices[i] - prices[i - 1],globalProfit[i - 1][j - 1] +Math.max(0, prices[i] - prices[i - 1]));
                globalProfit[i][j] = Math.max(localProfit[i][j], globalProfit[i - 1][j]);
            }
        }
        return globalProfit[n - 1][k];

    }
}

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(left[i - 1], prices[i] - min);
        }
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            max = Math.max(prices[i], max);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            profit = Math.max(left[i] + right[i], profit);
        }
        return profit;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(0, prices[i] - prices[i - 1]);
        }
        return result;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int min = prices[0];
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            result = Math.max(result, prices[i] - min);
        }
        return result;
    }
}

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

public class Solution {
    private void copyNext(RandomListNode head) {
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random;
            newNode.next = head.next;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.next.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            head = head.next;
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
        }
        return newHead;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }
}

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for (int i = 1; i < len1 + 1; i++) {
            if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i < len2 + 1; i++) {
            if (s2.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
            }
        }
        return dp[len1][len2];
    }
}

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        int wordMaxLen = 0;
        for (String str : wordDict) {
            wordMaxLen = Math.max(wordMaxLen, str.length());
        }
        for (int i = 1; i < len + 1; i++) {
            for (int j = i - 1; j >= 0 && i - j <= wordMaxLen; j--) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int start = 0;
        int end = 0;
        int jumps = 0;
        while (end < nums.length - 1) {
            jumps++;
            int farthest = 0;
            for (int i = start; i <= end; i++) {
                farthest = Math.max(farthest, nums[i] + i);
            }
            start = end;
            end = farthest;
        }
        return jumps;
    }
}

   public int jump(int[] A) {
        // write your code here
        int[] dp = new int[A.length];
        dp[0] = 0;
        for (int i = 1; i < A.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (A[j] >= i - j) {
                    min = Math.min(min, dp[j]);
                }
            }
            dp[i] = min + 1;
        }
        return dp[A.length - 1];
    }

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int farthest = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i <= farthest && nums[i] + i >= farthest) {
                farthest = nums[i] + i;
                if (farthest >= nums.length - 1) {
                    return true;
                }
            }
        }
        return farthest >= nums.length - 1;
    }
}

public class Solution {
    public boolean canJump(int[] nums) {
        // if (nums == null || nums.length == 0) {
        //     return true;
        // }
        boolean[] canJump = new boolean[nums.length];
        canJump[0] = true;
        for (int i = 0; i < nums.length; i++) {
            if (!canJump[i]) {
                return false;
            }
            for (int j = nums[i]; j >= 1; j--) {
                if (i + j >= nums.length - 1) {
                    return true;
                }
                canJump[i + j] = true;
            }
        }
        return canJump[nums.length - 1];
    }
}

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int result = 0;
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

 public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int result = 0;
        Set<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            int left = nums[i] - 1;
            while (set.contains(left)) {
                set.remove(left);
                left--;
            }
            int right = nums[i] + 1;
            while (set.contains(right)) {
                set.remove(right);
                right++;
            }
            result = Math.max(result, right - left - 1);
        }
        return result;
    }
}

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (null == triangle || triangle.size() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int height = triangle.size();
        for (int i = height - 2; i >= 0; i--) {
            int size = triangle.get(i).size();
            for (int j = 0; j < size; j++) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (null == triangle || triangle.size() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int height = triangle.size();
        for (int i = height - 2; i >= 0; i--) {
            int size = triangle.get(i).size();
            for (int j = 0; j < size; j++) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    Stack<TreeNode> stack = new Stack();
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        TreeNode node = cur;
        cur = cur.right;
        return node.val;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.

If the given node has no in-order successor in the tree, return null.

 Notice

It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)

Have you met this question in a real interview? Yes
Example
Given tree = [2,1] and node = 1:

  2
 /
1
return node 2.

Given tree = [2,1,3] and node = 2:

  2
 / \
1   3
return node 3.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // write your code here
        if (root == null) {
            return null;
        }
        TreeNode successor = null;
        while (root != null) {
            if (root.val <= p.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }
        return successor;
    }
}

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the 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 int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] max = {Integer.MIN_VALUE};
        maxPathSum(root, max);
        return max[0];
    }
    // 注意这里的辅助函数意思一定是root往一边走的最大路径。
    private static int maxPathSum(TreeNode root, int[] max) {
        if (root == null) {
            return 0;
        }
        int leftSum = maxPathSum(root.left, max);
        int rightSum = maxPathSum(root.right, max);
        int curMax = root.val + Math.max(0, Math.max(leftSum, rightSum));
        max[0] = Math.max(max[0], Math.max(curMax, root.val + leftSum + rightSum));
        return curMax;
    }
}

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

/**
 * 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 binary tree.
     * @return an integer
     */
    public int maxPathSum2(TreeNode root) {
        // Write your code here
        if (root == null) {
            return 0;
        }
        return Math.max(root.val, root.val + Math.max(maxPathSum2(root.left), maxPathSum2(root.right)));
    }
}

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

Given a string and an offset, rotate string by offset. (rotate from left to right)

public class Solution {
    /**
     * @param str: an array of char
     * @param offset: an integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
       if (null == str || str.length == 0 || offset <= 0) {
           return;
       }
       offset = offset % str.length;
       reverseString(str, 0, str.length - 1 - offset);
       reverseString(str, str.length - offset, str.length - 1);
       reverseString(str, 0, str.length - 1);

    }
    public static void reverseString(char[] str, int start, int end) {
        if (null == str || str.length == 0) {
            return;
        }
        while (start < end) {
            str[start] = (char) (str[start] ^ str[end]);
            str[end] = (char) (str[start] ^ str[end]);
            str[start] = (char) (str[start] ^ str[end]);
            start++;
            end--;
        }
    }
}

Given a rotated sorted array, recover it to sorted array in-place.

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        if (null == nums || nums.size() == 0) {
            return;
        }
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) {
                reverseArrayList(nums, 0, i);
                reverseArrayList(nums, i + 1, nums.size() - 1);
                reverseArrayList(nums, 0, nums.size() - 1);
            }
        }

    }

    // reverse the ArrayList
    public static void reverseArrayList(ArrayList<Integer> a, int start, int end) {
        // swap the a.get(start) and the a.get(end)
        /** Error:
         *while (start < end) {
         *    a.get(start) = a.get(start) ^ a.get(end);
         *    a.get(end) = a.get(start) ^ a.get(end);
         *    a.get(start) = a.get(start) ^ a.get(end);
         *    start++;
         *    end--;
         * }
         */
         while (start < end) {
             a.set(start, a.get(start) ^ a.get(end));
             a.set(end, a.get(start) ^ a.get(end));
             a.set(start, a.get(start) ^ a.get(end));
             start++;
             end--;
         }
    }
}

给一个按照升序排序的正整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数。(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。

如果找不到target，返回-1。

/**
 * Definition of ArrayReader:
 *
 * class ArrayReader {
 *      // get the number at index, return -1 if not exists.
 *      public int get(int index);
 * }
 */
public class Solution {
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return : An integer which is the index of the target number
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        // write your code here
        if (reader == null) {
            return -1;
        }
        int start = 0;
        int end = Integer.MAX_VALUE;
        int res = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (reader.get(mid) == -1) {
                end = mid - 1;
                continue;
            }
            if (reader.get(mid) == target) {
                res = mid;
                end = mid - 1;
            } else if (reader.get(mid) < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return res;
    }
}

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

public class Solution {
    /**
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] a, int target) {
        // write your code here
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if (a == null || a.length == 0) {
            return res;
        }
        res[0] = findStartPosition(a, target);
        res[1] = findEndPosition(a, target);
        return res;
    }
    public static int findStartPosition(int[] a, int target) {
        if (a == null || a.length == 0) {
            return -1;
        }
        int start = 0;
        int end = a.length - 1;
        int res = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == target) {
                res = mid;
                end = mid - 1;
            } else if (a[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return res;
    }
    public static int findEndPosition(int[] a, int target) {
        if (a == null || a.length == 0) {
            return -1;
        }
        int start = 0;
        int end = a.length - 1;
        int res = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == target) {
                res = mid;
                start = mid + 1;
            } else if (a[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return res;
    }
}

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (left == right) {
                return left;
            }
            if (right - left == 1) {
                return nums[right] > nums[left] ? right : left;
            }
            int mid = left + (right - left) / 2;
            if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return -1;
        }
        int left = 1;
        int right = n;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int result = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                result = mid + 1;
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        return result;
    }
}

Find the last position of a target number in a sorted array. Return -1 if target does not exist.

public class Solution {
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return an integer
     */
    public int lastPosition(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Have you met this question in a real interview? Yes
Example
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int result = -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 6};
        System.out.println(binarySearch(nums, 2));
    }
    private static int binarySearch(int[] nums, int t) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == t) {
                return mid;
            } else if (nums[mid] > t) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by Nano on 2016/9/29.
 */
public class Solution {
    static String[] paginate(int num, String[] results) {
        int length = results.length;
        int count = length / num;
        String[] output = new String[count + length];
        boolean[] flag = new boolean[length];
        ;
        ; i <= count; i++) {
            Set<String> keep = new HashSet();
            ; k < length && keep.size() < num; k++) {
                int location = results[k].indexOf(",");
                String ID = results[k].substring(, location);
                if (!keep.contains(ID) && !flag[k]) {
                    keep.add(ID);
                    flag[k] = true;
                    output[start++] = results[k];
                }
            }
            if (i != count && keep.size() == num) {
                output[start++] = "";
            } else {
                int size = keep.size();
                ; size < num && k < length; k++) {
                    if (!flag[k]) {
                        flag[k] = true;
                        output[start++] = results[k];
                        size++;
                    }
                }
                    if (i != count) {
                        output[start++] = "";
                    }
                }
            }
            return output;
        }

    public static void main(String[] args) {
        String[] results = {
                "131,28,300.6,San Francisco",
                "4,5,209.1,San Francisco",
                "20,7,203.4,Oakland",
                "6,8,202.9,San Francisco",
                "6,10,199.8,San Francisco",
                "1,16,190.5,San Francisco",
                "6,29,185.3,San Francisco",
                "7,20,180.0,Oakland",
                "6,21,162.2,San Francisco",
                "2,18,161.7,San Jose",
                "2,30,149.8,San Jose",
                "3,76,146.7,San Francisco",
                "2,14,141.8,San Jose"
        };
        System., results)));
    }
}

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
          List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        Arrays.sort(nums);
        results.add(cur);
        if (nums == null) {
            return results;
        }
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = new ArrayList(results);
            for (List<Integer> list : results) {
                List<Integer> listTemp = new ArrayList(list);
                listTemp.add(nums[i]);
                if (!temp.contains(listTemp)) {
                    temp.add(listTemp);
                }

            }
            results = new ArrayList(temp);
        }
        return results;
    }
}

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        if (nums == null) {
            return results;
        }
        Arrays.sort(nums);
        List<Integer> cur = new ArrayList();
        subsets(nums, 0, results, cur);
        return results;
    }
    private static void subsets(int[] nums, int index, List<List<Integer>> results, List<Integer> cur) {
        results.add(new ArrayList(cur));
        for (int i = index; i < nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }
            cur.add(nums[i]);
            subsets(nums, i + 1, results, cur);
            cur.remove(cur.size() - 1);
        }
    }
}

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        results.add(cur);
        if (nums == null) {
            return results;
        }
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = new ArrayList(results);
            for (List<Integer> list : results) {
                List<Integer> listTemp = new ArrayList(list);
                listTemp.add(nums[i]);
                temp.add(listTemp);
            }
            results = new ArrayList(temp);
        }
        return results;
    }
}

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        if (nums == null) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        subsets(nums, 0, results, cur);
        return results;
    }
    private static void subsets(int[] nums, int index, List<List<Integer>> results, List<Integer> cur) {
        results.add(new ArrayList(cur));
        for (int i = index; i < nums.length; i++) {
            cur.add(nums[i]);
            subsets(nums, i + 1, results, cur);
            cur.remove(cur.size() - 1);
        }
    }
}

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

public class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            int j = 0;
            for (; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }

            }
            if (j == needle.length()) {
                return i;
            }
        }
        return -1;
    }
}

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null) {
            return true;
        } else if (s == null) {
            return false;
        } else if (t == null || s.length() != t.length()) {
            return false;
        }
        Map map1 = new HashMap();
        Map map2 = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            if (!Objects.equals(map1.put(s.charAt(i), i), map2.put(t.charAt(i), i))) {
                return false;
            }
        }
        return true;
    }
}

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        Queue<UndirectedGraphNode> queue = new LinkedList();
        queue.add(node);
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap();
        map.put(node, head);
        while (!queue.isEmpty()) {
            UndirectedGraphNode curNode = queue.poll();
            for (UndirectedGraphNode now : curNode.neighbors) {
                if (!map.containsKey(now)) {
                    map.put(now, new UndirectedGraphNode(now.label));
                    queue.add(now);
                }
                map.get(curNode).neighbors.add(map.get(now));
            }
        }
        return head;
    }
}

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

public class Solution {
public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList();
        if (strs == null || strs.length == 0) {
            return result;
        }
        Map<String, List<String>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            char[] now = strs[i].toCharArray();
            Arrays.sort(now);
            String str = new String(now);
            if (map.containsKey(str)) {
                List<String> cur = map.get(str);
                cur.add(strs[i]);
                map.put(str, cur);
            } else {
                List<String> cur = new ArrayList();
                cur.add(strs[i]);
                map.put(str, cur);
            }
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }
}

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        //注意，map.put（）返回的是他代替掉的值，如果还没有存入，那么就是null。所以他可以用来判断是否一致。
        if (pattern == null && str == null) {
            return true;
        } else if (pattern == null || str == null) {
            return false;
        }
        String[] words = str.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }
        Map map = new HashMap();
        for (int i = 0; i < pattern.length(); i++) {
            if (!Objects.equals(map.put(words[i], i), map.put(pattern.charAt(i), i))) {
                return false;
            }
        }
        return true;
    }
}

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] results = new int[2];
        if (nums == null || nums.length == 0) {
            return results;
        }
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                results[0] = map.get(nums[i]);
                results[1] = i;
                return results;
            } else {
                map.put(target - nums[i], i);
            }
        }
        return results;
    }
}

map:
      HashMap:无序;TreeMap:有序。LinkedHashMap:插入顺序。
set : ArrayList : 有重复的。 HashSet：无序。TreeSet：有序。LinkedHashSet：插入顺序。

add, remove, get, containsKey都是O（1）。containsValue是O（n）；

    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap();
        map.put(1, 2);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey());
        }
    }

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class Kolmostar {
    public static void main(String[] args) {
        int[] a = {1, 7, 16, 7, 9};
        quickSort(a, 0, 4);
        System.out.println(Arrays.toString(a));
    }
    private static void quickSort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int first = left;
        int last = right;
        int key = a[first];
        while (first < last) {
            while (first < last && a[last] >= key) {
                last--;
            }
            a[first] = a[last];
            while (first < last && a[first] <= key) {
                first++;
            }
            a[last] = a[first];
        }
        a[first] = key;
        quickSort(a, left, first - 1);
        quickSort(a, first + 1, right);
    }
}

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return 0;
        }
        return helper(nums, 0, nums.length - 1, nums.length - k + 1);
    }
    private static int helper(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int position = partition(nums, left, right);
        if (position + 1 == k) {
            return nums[position];
        } else if (position + 1 < k) {
            return helper(nums, position + 1, right, k);
        } else {
            return helper(nums, left, position - 1, k);
        }
    }
    private static int partition(int[] nums, int left, int right) {
        int first = left;
        int last = right;
        int key = nums[first];
        while (first < last) {
            while (first < last && nums[last] >= key) {
                last--;
            }
            nums[first] = nums[last];
            while (first < last && nums[first] <= key) {
                first++;
            }
            nums[last] = nums[first];
        }
        nums[first] = key;
        return first;
    }
}

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode newHead = new ListNode(-1);
        // PriorityQueue<Integer> minHeap = new PriorityQueue();
        PriorityQueue<ListNode> minHeap = new PriorityQueue(new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                minHeap.add(lists[i]);
            }
        }
        ListNode cur = newHead;
        while (!minHeap.isEmpty()) {
            cur.next = minHeap.poll();
            cur = cur.next;
            if (cur.next != null) {
                minHeap.add(cur.next);
            }
        }
        return newHead.next;
    }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode newHead = new ListNode(-1);
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            while (node != null) {
                minHeap.add(node.val);
                node = node.next;
            }
        }
        ListNode cur = newHead;
        while (!minHeap.isEmpty()) {
            cur.next = new ListNode(minHeap.poll());
            cur = cur.next;
        }
        return newHead.next;
    }
}

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode node1 = l1;
        ListNode node2 = l2;
        ListNode node = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                node.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                node.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            node = node.next;
        }
        while (l1 != null) {
            node.next = new ListNode(l1.val);
            l1 = l1.next;
            node = node.next;
        }
        while (l2 != null) {
            node.next = new ListNode(l2.val);
            l2 = l2.next;
            node = node.next;
        }

        return newHead.next;
    }
}

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        while (m > 0 && n > 0) {
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[index] = nums1[m - 1];
                m--;
            } else {
                nums1[index] = nums2[n - 1];
                n--;
            }
            index--;
        }
        while (m > 0) {
            nums1[index] = nums1[m - 1];
            index--;
            m--;
        }
        while (n > 0) {
            nums1[index] = nums2[n - 1];
            index--;
            n--;
        }
    }
}

add/insert:O(n)。把数字插入到最后一个位置，然后不断地往上走。
delete.删除。把最后一个和顶元素交换。然后把他不断地往下走。
建堆：1，如果是一个接一个的加入。复杂度是：nlogn.
2，但是通常的建堆是把堆建好。从倒数第二层开始一层一层的往下走。那么递推公式就是：
看似建堆(make_heap)的复杂度为O(nlogn)，实则为O(n)，reheapify_down不会touch到每个节点，所以不算简单的递归，只能算叠加。证明如下：

因为堆构建的是一颗平衡二叉树。于是有：
1. 一棵拥有n个节点的平衡二叉树，树高 h 约为 lg n 。
2. 树的第 i 层 最多有节点 2^i 个。注意，第 i 层的高度为 i + 1。如第0层的高度为1，拥有1个根节点。

那么做reheapify_down时，最底层(h-1)的节点不会动，倒数第二层（h-2）的节点最多往下移动一次，倒数第三层（h-3）的节点最多往下移动2次....第0层的节点往下最多移动（h-1）次。
所以，最坏情况下，每层所有节点都会往下移到最底层。
则，所有操作总和为     S = 2^(h-1)*0 + 2^(h-2)*1 + 2^(h-3) * 2 + ... + 2^1*(h-2) + 2^0*(h-1)        ----- （1）
把（1）式乘以2，再减去（1）式， 可得
S = 2^(h-1) + 2^(h-2) + ... + 2^1 - 2^0*(h-1)  = 2(1-2^(h-1))/(1-2) - (h-1) = 2^h - h- 1      ---- (2)
把h = lg n 代入 （2）式， 得 S = n - lgn - 1 <= n   (n >=1)

故而， 建堆复杂度为O(n) 。

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] status = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (status[i] == 0 && !isDAG(graph, i, status)) {

            1    return false;
            }
        }
        return true;
    }
    private static boolean isDAG(List<List<Integer>> graph, int root, int[] status) {
        if (status[root] == 1) {
            return false;
        }
        status[root] = 1;
        for (int i : graph.get(root)) {
            if (!isDAG(graph, i, status)) {
                return false;
            }
        }
        status[root] = 2;
        return true;
    }
}

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> cur = new ArrayList();
            for (int i = 0; i < size; i++) {
                TreeNode now = queue.poll();
                if (flag) {
                    cur.add(now.val);
                } else {
                    cur.add(0, now.val);
                }
                if (now.left != null) {
                    queue.add(now.left);
                }
                if (now.right != null) {
                    queue.add(now.right);
                }
            }
            result.add(new ArrayList(cur));
            flag = !flag;
        }
        return result;
    }
}

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> cur = new ArrayList();
            for (int i = 0; i < size; i++) {
                TreeNode now = queue.poll();
                cur.add(now.val);
                if (now.left != null) {
                    queue.offer(now.left);
                }
                if (now.right != null) {
                    queue.offer(now.right);
                }
            }
            result.add(new ArrayList(cur));
        }
        return result;
    }
}

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }
        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

/**
 * 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) {
        if (root == null) {
            return true;
        }
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private static boolean isValidBST(TreeNode root, long left, long right) {
        if (root == null) {
            return true;
        }
        if (root.val <= left || root.val >= right) {
            return false;
        } else {
            return isValidBST(root.left, left, root.val) && isValidBST(root.right, root.val, right);
        }

    }
}

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * 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 isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> results = new ArrayList();
        if (s == null || s.length() == 0) {
            return results;
        }
        ArrayList cur = new ArrayList();
        partition(results, s, 0, cur);
        return results;
    }
    private static void partition(List<List<String>> results, String s, int start, List<String> path) {
        if (start == s.length()) {
            results.add(new ArrayList(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (isPalindrome(sub)) {
                path.add(sub);
                partition(results, s, i, path);
                path.remove(path.size() - 1);
            }
        }
    }
    private static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] flag = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (exist(board, i, j, word, 0, flag)) {
                    return true;
                }
            }
        }
        return false;
    }
    private static boolean exist(char[][] board, int x, int y, String word, int index, boolean[][] flag) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || flag[x][y] || board[x][y] != word.charAt(index)) {
            return false;
        }
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            flag[x][y] = true;
            if (exist(board, x + dx[i], y + dy[i], word, index + 1, flag)) {
                return true;
            }
            flag[x][y] = false;
        }
        return false;
    }
}

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

public class MedianFinder {
    PriorityQueue<Integer> minHeap = new PriorityQueue();
    PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());
    // Adds a number into the data structure.
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return -1;
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        if (len % 2 == 1) {
            return findMedian(nums1, 0, nums2, 0, len / 2 + 1);
        } else {
            return (findMedian(nums1, 0, nums2, 0, len / 2) + findMedian(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        }
    }
    private static double findMedian(int[] a, int aIndex, int[] b, int bIndex, int k) {
        if (aIndex >= a.length) {
            return b[bIndex + k - 1];
        }
        if (bIndex >= b.length) {
            return a[aIndex + k - 1];
        }
        if (k == 1) {
            return Math.min(a[aIndex], b[bIndex]);
        }
        int aMid = aIndex + k / 2 - 1 < a.length ? a[aIndex + k / 2 - 1] : Integer.MAX_VALUE;
        int bMid = bIndex + k / 2 - 1 < b.length ? b[bIndex + k / 2 - 1] : Integer.MAX_VALUE;
        if (aMid < bMid) {
            return findMedian(a, aIndex + k / 2, b, bIndex, k - k / 2);
        } else {
            return findMedian(a, aIndex, b, bIndex + k / 2, k - k / 2);
        }
    }
}

因为给的条件都比较独特，为了弥补早上发挥的不足，所以，写了早上面试过程中讨论的三种情况的答案。

1，师兄给出的题目：给两个数组，都是长度为n。需要找的中位数是返回C(n)（C代表把两个数组合并在一起了）.所以，这里面说明了需要实际查找的是第N + 1位。

     根据这个背景下，给出代码如下：

public class Kolmostar {
    /**
     * @author 李春跃-北京邮电大学研究生
     * @email chunyuelibigdata@gmail.com
     * @思路 利用二分来做。其实早上说的时候基本上思路已经正确了，就是比较中间的值，然后往哪边走。
     * 当时的说法错误在于不应该两个都动，而是动其中较小的那个就行。排除掉那部分肯定不会含有值的地方。
     * @分析 时间复杂度O(log(n)).空间复杂度O(1)
     */
    public static void main(String[] args) {
        int[] A = {1, 6, 7, 9};
        int[] B = {0, 2, 4, 5};
        System.out.println(findMedian(A, B));
    }
    private static int findMedian(int A[], int B[]) {
        if (A == null || B == null) {
            return -1; // 判断是否有异常，返回-1.
        }
        int n = A.length; //早上题目描述是给两个都是长度为n的数组。返回的是C(n)。那么也就是找第n+1位.
//        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;
        return findKth(A, 0, B, 0, n + 1);
    }
    // find kth number of two sorted array
    private static int findKth(int[] A, int A_index, int[] B, int B_index, int k){
        if (A_index >= A.length) {
            return B[B_index + k - 1];
        }
        if (B_index >= B.length) {
            return A[A_index + k - 1];
        }
        if (k == 1) {
            return Math.min(A[A_index], B[B_index]);
        }
        int A_key = A_index + k / 2 - 1 < A.length ? A[A_index + k / 2 - 1] : Integer.MAX_VALUE;
        int B_key = B_index + k / 2 - 1 < B.length ? B[B_index + k / 2 - 1]: Integer.MAX_VALUE;
        if (A_key < B_key) {
            return findKth(A, A_index + k / 2, B, B_index, k - k / 2);
        } else {
            return findKth(A, A_index, B, B_index + k / 2, k - k / 2);
        }
    }
}

2，因为严格意义上这道题给出的两个数组不一定都是一样长为n，而且中位数的严格定义应该是总个数为奇数的时候是最中间那个，偶数个的时候是最中间的那两个的均值。所以，相对于上面的这里需要作出以下几个改变：

（1）返回值应该是double而不是整数。

（2）需要分情况讨论总个数是奇数还是偶数的时候。

 （3）时间复杂度变成了O(log(Math. min(A.length, B.length)))。

在这个背景下，给出代码：

public class Kolmostar {
    /**
     * @author 李春跃-北京邮电大学研究生
     * @email chunyuelibigdata@gmail.com
     * @思路 利用能够找到第k大的函数来分个数为奇数偶数情况的时候求出中位数
     * @时间复杂度O(log(Math. min(A.length, B.length)))
     * @空间复杂度O(1)
     */
    public static void main(String[] args) {
        int[] A = {1, 6, 7, 9};
        int[] B = {0, 2, 4, 5};
        System.out.println(findMedian(A, B));
    }
    private static double findMedian(int A[], int B[]) {
        if (A == null || B == null) {
            return -1; // 判断是否有异常，返回-1.
        }
        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
    private static int findKth(int[] A, int A_index, int[] B, int B_index, int k){
        if (A_index >= A.length) {
            return B[B_index + k - 1];
        }
        if (B_index >= B.length) {
            return A[A_index + k - 1];
        }
        if (k == 1) {
            return Math.min(A[A_index], B[B_index]);
        }
        int A_key = A_index + k / 2 - 1 < A.length ? A[A_index + k / 2 - 1] : Integer.MAX_VALUE;
        int B_key = B_index + k / 2 - 1 < B.length ? B[B_index + k / 2 - 1]: Integer.MAX_VALUE;
        if (A_key < B_key) {
            return findKth(A, A_index + k / 2, B, B_index, k - k / 2);
        } else {
            return findKth(A, A_index, B, B_index + k / 2, k - k / 2);
        }
    }
}

3，早上面试的时候，也讨论到了如果两个数组没有序的话该怎么做。回来学校也写了这种情况的代码。

import java.util.PriorityQueue;

public class Kolmostar {
    /**
     * @author 李春跃-北京邮电大学研究生
     * @email chunyuelibigdata@gmail.com
     * @思路 利用最大堆最小堆来辅助一起维持中位数的位置
     * @时间复杂度：O(A.length + B.length)
     * @空间复杂度：O(A.length + B.length)
     */
    public static void main(String[] args) {
        int[] A = {1, 6, 7, 9};
        int[] B = {0, 2, 4, 5};
        System.out.println(findMedian(A, B));
    }
    public static double findMedian(int[] A, int[] B) {
        if (A == null || B == null) {
            return -1;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        PriorityQueue<Integer> maxHeap = new PriorityQueue();
        for (int i = 0; i < A.length; i++) {
            minHeap.offer(A[i]);
            maxHeap.offer(-minHeap.poll());
            if (maxHeap.size() - minHeap.size() > 1) {
                minHeap.offer(-maxHeap.poll());
            }
        }
        for (int i = 0; i < B.length; i++) {
            minHeap.offer(B[i]);
            maxHeap.offer(-minHeap.poll());
            if (maxHeap.size() - minHeap.size() > 1) {
                minHeap.offer(-maxHeap.poll());
            }
        }
        //返回的时候，讨论总个数是偶数还是奇数
        if (minHeap.size() == maxHeap.size()) {
            return (double)(minHeap.peek() - maxHeap.peek()) / 2.0;
        }
        return -maxHeap.peek();
    }
}

                                      　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　----by 李春跃 

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        maxPathSum(root, max);
        return max[0];
    }
    private static int maxPathSum(TreeNode root, int[] max) {
        if (root == null) {
            return 0;
        }
        int leftSum = maxPathSum(root.left, max);
        int rightSum = maxPathSum(root.right, max);
        int curMax = root.val + Math.max(0, Math.max(leftSum, rightSum));
        max[0] = Math.max(max[0], Math.max(curMax, leftSum + root.val + rightSum));
        return curMax;
    }
}

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> results = new ArrayList();
        if (root == null) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        pathSum(root, sum, results, cur);
        return results;
    }
    private static void pathSum(TreeNode root, int sum, List<List<Integer>> results, List<Integer> cur) {
        if (root == null) {
            return;
        }
        sum = sum - root.val;
        if (root.left == null && root.right == null) {
            if (sum == 0) {
                cur.add(root.val);
                results.add(new ArrayList<Integer>(cur));
                cur.remove(cur.size() - 1);
            }
            return;
        }
        cur.add(root.val);
        pathSum(root.left, sum, results, cur);
        pathSum(root.right, sum, results, cur);
        cur.remove(cur.size() - 1);
    }
}

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * 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 hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                return true;
            }
            return false;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0) {
            return right +1;
        }
        if (right == 0) {
            return left +1;
        }
        return Math.min(left, right) + 1;
    }
}

101. Symmetric Tree  QuestionEditorial Solution  My Submissions
Total Accepted: 131244
Total Submissions: 366595
Difficulty: Easy
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

/**
 * 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 isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    private static boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            if (left.val != right.val) {
                return false;
            } else {
                return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
            }
        }
    }
}

/**
 * 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 isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return depth(root) != -1;
    }
    private static int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}

public int depth(TreeNode root) {
        if (root == null) {
            ;
        }
        ;
    }

import javax.xml.soap.Node;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class Main {

    public static boolean find(int value, TreeNode node) {
        while (node != null) {
            if (node.val == value) {
                return true;
            } else if (node.val > value) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return false;
    }
    public static boolean add(int value, TreeNode root) {
        if (root == null) {
            root = new TreeNode(value);
            return true;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.val > value) {
                if (node.left != null) {
                    node = node.left;
                } else {
                    node.left = new TreeNode(value);
                    return true;
                }
            } else if (node.val < value) {
                if (node.right != null) {
                    node = node.right;
                } else {
                    node.right = new TreeNode(value);
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean remove(int value, TreeNode root) { // find, then removeNode
        if (root == null) {
            return false;
        }
        if (root.val == value) {
            root = removeNode(root);
            return true;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.val > value) {
                if (node.left != null && node.left.val != value) {
                    node = node.left;
                } else if (node.left == null) {
                    return false;
                } else {
                    node.left = removeNode(node.left);
                    return true;
                }
            } else if (node.val < value) {
                if (node.right != null && node.right.val != value) {
                    node = node.right;
                } else if (node.right != null) {
                    return false;
                } else {
                    node.right = removeNode(node.right);
                    return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
    public static TreeNode removeNode(TreeNode node) {
        if (node.left == null && node.right == null) {
            return null;
        } else if (node.left == null) {
            return node.right;
        } else if (node.right == null) {
            return node.left;
        } else {
            node.val = findAndRemove(node);
            return node;
        }
    }
    public static int findAndRemove(TreeNode node) {
        int result;
        if (node.left.right == null) {
            result = node.left.val;
            node.left = node.left.left;
            return result;
        }
        node = node.left;
        while (node.right.right != null) {
            node = node.right;
        }
        result = node.right.val;
        node.right = node.right.left;
        return result;
    }
}

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        return buildTree(inorder, 0, len - 1, postorder, 0, len - 1);
    }
    private static TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        int val = postorder[postEnd];
        TreeNode root = new TreeNode(val);
        int k = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (val == inorder[i]) {
                k = i;
                break;
            }
        }
        root.left = buildTree(inorder, inStart, k - 1, postorder, postStart, postStart + k - inStart - 1);
        root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k - inStart, postEnd - 1);
        return root;
    }
}

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Subscribe to see which companies asked this question

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        return buildTree(preorder, 0, len - 1, inorder, 0, len - 1);
    }
    private static TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int val = preorder[preStart];
        TreeNode p = new TreeNode(val);
        int k = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (val == inorder[i]) {
                k = i;
                break;
            }
        }
        p.left = buildTree(preorder, preStart + 1, preStart + (k - inStart), inorder, inStart, k - 1);
        p.right = buildTree(preorder, preStart + (k - inStart) + 1, preEnd, inorder, k + 1, inEnd);
        return p;
    }
}

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class TreeNodeWithFlag {
     TreeNode node;
     boolean flag;
     public TreeNodeWithFlag(TreeNode n, boolean value) {
         node = n;
         flag = value;
     }
 }
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        Stack<TreeNodeWithFlag> stack = new Stack();
        TreeNode curNode = root;
        TreeNodeWithFlag newNode;
        while (!stack.isEmpty() || curNode != null) {
            while (curNode != null) {
                newNode = new TreeNodeWithFlag(curNode, false);
                stack.push(newNode);
                curNode = curNode.left;
            }
            newNode = stack.pop();
            curNode = newNode.node;
            if (!newNode.flag) {
                newNode.flag = true;
                stack.push(newNode);
                curNode = curNode.right;
            }else {
                result.add(curNode.val);
                curNode = null;
            }
        }
        return result;
    }
}

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],
   1
    \
     2
    /
   3
return [1,3,2].

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        if (root == null) {
            return result;
        }
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }
        return result;
    }
}

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            } if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        TreeNode node = root;
        while (!stack.isEmpty()) {
            result.add(node.val);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                node = node.left;
            } else {
                node = stack.pop();
            }
        }
        return result;
    }
}

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

public class Solution {
    public int numDistinct(String s, String t) {
        if (s == null) {
            return 0;
        }
        if (t == null) {
            return 1;
        }
        int lenS = s.length();
        int lenT = t.length();
        int[][] dp = new int[lenS + 1][lenT + 1];
        for (int i = 0; i <= lenS; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= lenS; i++) {
            for (int j = 1; j <= lenT; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[lenS][lenT];
    }
}

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (null == triangle || triangle.size() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int height = triangle.size();
        for (int i = height - 2; i >= 0; i--) {
            int size = triangle.get(i).size();
            for (int j = 0; j < size; j++) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

Give A0,A1,.....,An-1 n different matrixs
Find minimum of multiplication it needs to get the result
input: An array P with n+1 numbers
A0 = p0*p1, An-1 = Pn-1*Pn

public static int MatrixChain(int[] p)
{
int n = p.length;
n --;
int[][] m = new int[n][n];
for(int i = 0; i < n; i++)
m[i][i] = 0;
for(int r = 2; r <= n; r++)
{
for(int i = 0; i < n - r + 1; i ++)
{
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i] * p[i+1] * p[j + 1];
for(int k = i + 1; k < j; k++)
{
int t = m[i][k] + m[k + 1][j] + p[i] * p[k+1] * p[j+1];
if( t < m[i][j])
m[i][j] = t;
}
}
}
return m[0][n-1];
}

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) {
            return 0;
        } else if (word1 == null) {
            return word2.length();
        } else if (word2 == null) {
            return word1.length();
        }
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null) {
            return 0;
        }
        int lenA = A.length();
        int lenB = B.length();
        int[][] dp = new int[lenA + 1][lenB + 1];
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if(A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, Math.max(dp[i - 1][j], dp[i][j - 1]));
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[lenA][lenB];
    }
}

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

0-1 Knapsack
Given a knapsack which can hold s pounds of items, and a set
of items with weight w1, w2, ... wn. Each item has its value
s1,s2,...,sn. Try to select the items that could put in knapsack
and contains most value.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        int[] w = {1, 3, 4, 5};
        int[] v = {3, 8, 4, 7};
        System.out.println(knapsack(7, w, v));
    }
    public static int knapsack(int capacity, int[] weights, int[] values) {
        if (capacity <= 0 || weights == null || weights.length == 0 || values == null || values.length == 0) {
            return 0;
        }
        int[][] dp = new int[weights.length + 1][capacity + 1];
        for (int i = 1; i <= weights.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - weights[i - 1]] + values[i - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[weights.length][capacity];
    }
}

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (null == obstacleGrid || obstacleGrid.length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

Print Path of a Tree Given a Leave
Description:
Given a root of a known binary tree and a key, return the path from the root to this node. We can make sure that there are no duplicates in the tree for the key
Example Tree is like:
Examples:
Key = 30 return [14,9,0,17,30]
Key = 4 return [14,5,8,3,4]
Key = 22 return [14,9,19,22]
API
Java: public List<Integer> PrintPath(Node Root, int key)
C++: public int[] PrintPath(Node* Root, int key)
Java:
Node {
int val;
Node leftChild;
Node rightChild;
}
C++:
Node {
int val;
Node* leftChild;
Node* rightChild;
}
Print Characters from number
Description:
Given a number in string format, return how many character combinations there could be derived from the number. Number to character: 1-A, 2-B, 26-Z. We ensure the string is always valid (it will not contain other character than ‘0’ to ‘9’)
Examples:
Input: 1234
Output: 3,
(These three are the possible results:
<1,2,3,4 ABCD>, <12, 3, 4 LCD>, <1, 23, 4 AWD>
API:
Java: public static int stringCombinationNum(String number);
C++: public int stringCombinationNum(string number);
Division + Cycle
Description:
Given two numbers num1 and num2, return the string format of division result of num1/num2.
If num1 cannot be divided by num2, then put the cycle of the result into brackets.
Examples:
Input: 4, 5
Output: 0.8
Input: 4, 6
Output: 0.(6)
Input: 17, 66
Output: 0.2(57)
API:
Java: public static String divide(int num1, int num2);
C++: public static string divide(int num1, int num2);
Palindrome: Minimum Insertion
Description:
Given a String, return the minimum number of characters that it needs to be inserted to make it become a palindrome. We make sure we only have lowercase English characters (a to z)
Examples:
Input: abc, output: 2 (it can become cbabc or abcba, etc)
Input: ababa, output: 0
Input: abccbac, output: 1 (it will become cabccbac)
API:
Java: public int minimumPalidrome(String word)
C++: public int minimumPalidrome(string word)

import java.util.ArrayList;
import java.util.List;
class Node {
    int val;
    Node leftChild;
    Node rightChild;
    public Node(int x) {
        val = x;
    }
}
public class Solution {
    /**
     * 答案和思路：利用树的递归性质，往左往右找，用List存下来路径的每一个点，如果找到了就返回。值得注意的是每一个ArrayList必须新开，不然左右的值都会add到一起。
     * 时间复杂度分析：O(n)
     * @author ChunyueLi
     */
    public static void main(String[] args) {
        Node root = new Node(14);
        root.leftChild = new Node(5);
        root.rightChild = new Node(9);
        root.leftChild.leftChild = new Node(8);
        root.leftChild.rightChild = new Node(6);
        System.out.println(printPath(root, 6));
    }
    public static List<Integer> printPath(Node root, int key) {
        List<Integer> result = new ArrayList();
        if (root == null) {
            return result;
        }
        return findPath(root, key, result);
    }
    private static List<Integer> findPath(Node root, int key, List<Integer> result) {
        if (root != null) {
            result.add(root.val);
            if (root.val == key) {
                return new ArrayList(result);
            }
        } else {
            return null;
        }
        List<Integer> left = findPath(root.leftChild, key, new ArrayList(result));
        if (left != null) {
            return left;
        } else {
            return findPath(root.rightChild, key, new ArrayList(result));
        }

    }
}

public class Solution {
    public static void main(String[] args) {
        String number = "1234";
        System.out.println(stringCombinationNum(number));
    }
    public static int stringCombinationNum(String number) {
        /**
         * 答案和思路：这道题是一道dp题。解答并不难。dp[i]表示的是前i个字符能够表示多少种合法的字母。那么对于第i个位置，唯一能够影响他的也就是他的前一个和他是否又能够构成一个字母，如果能的话，他就有两种组成方式。
         * 一种组成方式是他自己和他的前面的i-1个组成，一种是他和i-1再和他前面的i-2个组成。
         * 时间复杂度分析：O（n)
         * 滚动指针优化动态规划：%3就可以。空间复杂度从O（n)优化到O（1）
         * @author ChunyueLi
         */
        int n = number.length();
        int[] dp = new int[n+1]; // A table to store results of subproblems
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (number.charAt(i - 1) > '0') {
                dp[i] = dp[i-1];
            }
            if (number.charAt(i - 2) < '2' || (number.charAt(i - 2) == '2' && number.charAt(i-1) < '7') ) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
}

import java.util.LinkedHashMap;

public class Solution {
    public static void main(String[] args) {
        System.out.println(divide2(17, 66));
    }
    /**
     * 这里用LinkedHashMap来看是否已经循环了.LinkedHashMap的好处就是他可以记住插入的顺序位置
     */
    public static String divide2(int num1, int num2) {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap();
        StringBuffer sb = new StringBuffer();
        while (num1 != 0) {
            if (map.containsKey(num1)) {
                sb = new StringBuffer();
                int i = 1;
                for (int n : map.keySet()) {
                    if (n < num2 && sb.length() == 0) {
                        sb.append("0.");
                    }
                    if (n == num1) {
                        sb.append('(');
                        sb.append(map.get(n));
                    } else {
                        sb.append(map.get(n));
                    }
                    i++;
                }
                sb.append(')');
                return sb.toString();
            }

            if (num1 < num2) {
                if (sb.length() == 0) {
                    sb.append("0.");
                } else {
                    sb.append('.');
                }
                sb.append(num1 * 10 / num2);
                map.put(num1, num1 * 10 / num2);
                num1 = num1 * 10 % num2;
            } else {
                sb.append(num1 / num2);
                map.put(num1, num1 / num2);
                num1 = num1 % num2;
            }
        }
        return sb.toString();
    }
}

public class YUEYE {
    public static void main(String[] args) {
        System.out.println(minimumPalidromw("abc"));
    }
    /**
     * 思路：找到最小的插入位置就核心。
     * @author ChunyueLi
     */
    public static int minimumPalidromw(String word) {
        return helper(word, 0, word.length() - 1);
    }
    public static int helper(String str, int l, int h)
    {
        if (l > h) {
            return Integer.MAX_VALUE;
        }
        if (l == h) {
            return 0;
        }
        if (l == h - 1) {
            return (str.charAt(l) == str.charAt(h))? 0 : 1;
        }
        if (str.charAt(l) == str.charAt(h)) {
            return helper(str, l + 1, h - 1);
        } else {
            return Math.min(helper(str, l, h - 1), helper(str, l + 1, h)) + 1;
        }

    }
}

用样本中有限的编号来估计总体数量，可以使用“一致最小变异不偏估计量’或‘无偏见最佳估计”理论进行估计假设坦克是按从1到N顺序生产的，通过最小方差无偏估计得出估算：m是（样本最大值）最大序列号，k是观测到的坦克数（样本大小）。一个序列号经过观测后将被排除样本池之外，不再进行观测。方差：但是这个估计是有误差的。真正的坦克总数应该是在估计值左右，所以我们就要用置信区间（ConfidenceInterval）的方式，把真实值左右的变化度体现出来。通过置信区间我们可以结论，有95%信心，真正的坦克数量是出现在这个区间之中[m,m/p^1/k]改估计的优点是用贝叶斯估计改进了传统的统计学理论，比传统估计更加准确，缺点是公式复杂。

import java.util.Arrays;
public class Solution {
    static int[] a = {7, 6, 5, 4, 3, 2, 1};

    public static void main(String[] args) {
        smallBigSort(a);                           //按照题目的要求进行排序
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ",");     //排序后打印出来
        }
    }
    public static void smallBigSort(int[] a) {
        boolean flag = false;
        for (int i = 0; i < a.length - 1; i++) {
            if (flag) {
                for (int j = a.length - 1; j > i; j--) {
                    if (a[j] > a[j - 1]) {
                        int team = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = team;
                    }
                }
            } else {
                for (int j = a.length - 1; j > i; j--) {
                    if (a[j] <= a[j - 1]) {
                        int team = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = team;
                    }
                }
            }
            flag = !flag;
        }
    }

}

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        // find the mid, the reverse.
        if (head == null || head.next == null) {
            return true;
        }
        // reverse from the mid
        ListNode middle = findMiddle(head);
        middle.next = reverse(middle.next);
        return isSame(head, middle.next);
    }
    private static ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    private static ListNode reverse(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
    private static boolean isSame(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null && head1.val == head2.val) {
            head1 = head1.next;
            head2 = head2.next;
        }
        return head2 == null ? true : false;
    }
}

Given a collection of numbers C and a number k, return
all the combinations of k numbers.
Note: There could be duplicates in C, but duplicates are
not allowed in the results.
Examples:
Input: [1, 1, 1], 2 -> Output: [[1, 1]]
Input: [2, 3, 4], 2 -> Output: [[2, 3], [2, 4], [3, 4]]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        int[] w = {1, 1, 1};
        System.out.println(combination(w, 2));
    }
    public static List<List<Integer>> combination(int[] nums, int k) {
        List<List<Integer>> results = new ArrayList();
        if (nums == null || nums.length == 0 || k < 0) {
            return results;
        }
        Arrays.sort(nums);
        List<Integer> cur = new ArrayList();
        combine(nums, k, results, cur, 0);
        return results;
    }
    private static void combine(int[] nums, int k, List<List<Integer>> results, List<Integer> cur, int index) {
        if (cur.size() == k) {
            results.add(new ArrayList(cur));
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }
            cur.add(nums[i]);
            combine(nums, k, results, cur, i + 1);
            cur.remove(cur.size() - 1);
        }
    }
}

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> results = new ArrayList();
        if (k <= 0 || n <= 0) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        combine(results, cur, n, k, 1);
        return results;
    }
    private static void combine(List<List<Integer>> results, List<Integer> cur, int n, int k, int start) {
        if (cur.size() == k) {
            results.add(new ArrayList(cur));
            return;
        }
        for (int i = start; i <= n; i++) {
            cur.add(i);
            combine(results, cur, n, k, i + 1);
            cur.remove(cur.size() - 1);
        }
    }

}

1.    Given 2 sorted array, find the kth smallest number.
Examples:
a.    Input: [1, 3, 5], [2, 4, 6], 5    ----->    Output: 5
b.    Input: [6, 9, 17], [2, 18, 30], 4    ----->    Output: 17
Interface:
Java: int kthSmall(int[] arr1, int[] arr2, int k);
C++: int kthSmall(vector<int>arr1, vector<int>arr2, int k);

思路：这里思路利用的是归并的merge部分的思想。
时间复杂度是：0(K).
代码如下：
public int kthSmall(int[] arr1, int[] arr2, int k) {
    if (arr1 == null || arr2 == null || arr1.length + arr2.length < k || k <= 0) {
        return -1;
    }
    int arr1Index = 0;
    int arr2Index = 0;
    int result = -1;
    while (arr1Index < arr1.length || arr2Index < arr2.length) {
        while (arr1Index < arr1.length &&(arr2Index >= arr2.length || arr1[arr1Index] < arr2[arr2Index])) {
            arr1Index++;
            // 这里虽然index都是下标，但是由于每一次判断的时候，index都是指向了下一个位置。所以不用再多加1.
            if (arr1Index + arr2Index == k) {
                return arr1[arr1Index - 1];
            }
        }

        while (arr2Index < arr2.length && (arr1Index >= arr1.length || arr2[arr2Index] < arr1[arr1Index])) {
            arr2Index++;
            if (arr1Index + arr2Index == k) {
                return arr2[arr2Index - 1];
            }
        }
    }
    return result;
}
进一步优化的想法：根据m，n，k的范围可以进一步优化，比如，m，n，k都非常大，k也远远大于m+n的一半，那么从后往前找能够优化。

int kthSmall(int[] arr1, int[] arr2, int k){
return findKthSmallest(arr1, arr2, 0, 0, arr1.length-1, arr2.length-1, k);
}
int findKthSmallest(int a[], int b[], int startA, int startB, int endA, int endB, int k){
if(endA-startA > endB - startB) {
return findKthSmallest(b,a,startB,startA,endB,endA,k);
}
if(endA<startA) return b[startB+k-1];
if(k == 1) return Math.min(a[startA], b[startB]);
int pA = Math.min(endA-startA + 1, k/2);
int pB = k - pA;
if(a[startA + pA - 1] < b[startB + pB - 1]) {
return findKthSmallest(a,b,startA + pA, startB, endA, startB + pB, k - pA);
}
else if(a[startA + pA - 1] > b[startB + pB - 1]) {
return findKthSmallest(a,b,startA, startB + pB, startA + pA, endB, k - pB);
}
else {
return a[startA + pA - 1];

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList();
        generateParenthesis(results, "", n, n);
        return results;
    }
    private static void generateParenthesis(List<String> results, String prefix, int left, int right) {
        if (left == 0 && right == 0) {
            results.add(prefix);
            return;
        }
        if (left > 0) {
            generateParenthesis(results, prefix + "(", left - 1, right);
        }
        if (right > 0 && left < right) {
            generateParenthesis(results, prefix + ")", left, right - 1);
        }
    }
}

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        Interval pre = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= pre.end) {
                pre.end = Math.max(intervals.get(i).end, pre.end);
            } else {
                result.add(new Interval(pre.start, pre.end));
                pre = intervals.get(i);
            }
        }
        result.add(pre);
        return result;
    }
}

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

Credits:

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (s == 0 || nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0;
        int end = 0;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            while (end < nums.length && sum < s) {
                sum += nums[end++];
            }
            if (sum >= s) {
                result = Math.min(result, end - i);
            }
            sum -= nums[i];
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

public class Solution {
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] count = new int[1];
        int[] board = new int[n];
        placeNQueens(count, board, 0);
        return count[0];
    }
    private static void placeNQueens(int[] count, int[] board, int row) {
        if (row == board.length) {
            count[0]++;
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isLegal(board, row, col)) {
                board[row] = col;
                placeNQueens(count, board, row + 1);
            }
        }
    }
    private static boolean isLegal(int[] board, int row, int col) {
        for (int i = row - 1; i >= 0; i--) {
            if (board[i] == col || Math.abs(col - board[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
}

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList();
        if (n <= 0) {
            return results;
        }
        int[] board = new int[n];
        placeNQueens(results, board, 0);
        return results;
    }
    private static void placeNQueens(List<List<String>> results, int[] board, int row) {
        if (row == board.length) {
            save(results, board);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isLegal(board, row, col)) {
                board[row] = col;
                placeNQueens(results, board, row + 1);
            }
        }
    }
    private static boolean isLegal(int[] board, int row, int col) {
        for (int i = row - 1; i >= 0; i--) {
            if (board[i] == col || Math.abs(col - board[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
    private static void save(List<List<String>> results, int[] board) {
        List<String> cur = new ArrayList();
        for (int i = 0; i < board.length; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < board.length; j++) {
                if (j == board[i]) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            cur.add(new String(sb));
        }
        results.add(cur);
    }
}

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        Arrays.sort(candidates);
        combine(candidates, target, 0, results, cur);
        return results;
    }
    private static void combine(int[] candidates, int target, int index, List<List<Integer>> results, List<Integer> cur) {
        if (target == 0) {
            results.add(new ArrayList(cur));
            return;
        }
        if (target < 0 || index == candidates.length) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            cur.add(candidates[i]);
            combine(candidates, target - candidates[i], i + 1, results, cur);
            cur.remove(cur.size() - 1);
            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                i++;
            }
        }
    }
}

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
  [7],
  [2, 2, 3]
]

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        Arrays.sort(candidates);
        combine(candidates, target, 0, results, cur);
        return results;
    }
    private static void combine(int[] candidates, int target, int index, List<List<Integer>> results, List<Integer> cur) {
        if (target == 0) {
            results.add(new ArrayList(cur));
            return;
        }
        if (target < 0 || index == candidates.length) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            cur.add(candidates[i]);
            combine(candidates, target - candidates[i], i, results, cur);
            cur.remove(cur.size() - 1);
            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                i++;
            }
        }
    }
}

17. Letter Combinations of a Phone Number  QuestionEditorial Solution  My Submissions
Total Accepted: 96686
Total Submissions: 316654
Difficulty: Medium
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

public class Solution {
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        Map<Character, String[]> map = new HashMap<Character, String[]>();
        // map.put('0', new String[] {});
        // map.put('1', new String[] {});
        map.put('2', new String[] { "a", "b", "c" });
        map.put('3', new String[] { "d", "e", "f" });
        map.put('4', new String[] { "g", "h", "i" });
        map.put('5', new String[] { "j", "k", "l" });
        map.put('6', new String[] { "m", "n", "o" });
        map.put('7', new String[] { "p", "q", "r", "s" });
        map.put('8', new String[] { "t", "u", "v"});
        map.put('9', new String[] { "w", "x", "y", "z" });
        result.add("");
        for (int i = 0; i < digits.length(); i++) {
            String[] cur = map.get(digits.charAt(i));
            List<String> temp = new ArrayList();
            for (String str : result) {
                for (int j = 0; j < cur.length; j++) {
                    String strTemp = new String(str);
                    strTemp += cur[j];
                    temp.add(strTemp);
                }
            }
            result = new ArrayList(temp);
        }
        return result;
    }
}

0-1 Knapsack (Required)
Given a knapsack which can hold s pounds of items, and
a set of items with weight w1, w2, ... wn. Try to put items
into the pack as many as possible, print out all the items
that can get the largest weight. Each item can only get
picked once.

public static ArrayList<ArrayList<Integer>> knapsackPrint(int s, int[] weights) {
// get the largest weight
int max = knapsackMax(s, weights, 0);
ArrayList<ArrayList<Integer>> results = new ArrayList<>();
results = combinationSum(weights, max);
return results;
}
public static int knapsackMax(int s, int[] weights, int index) {
if (s == 0 || index == weights.length) {
return 0;
}
if (weights[index] > s) {
return knapsackMax(s, weights, index + 1);
}
return Math.max(knapsackMax(s, weights, index + 1),
weights[index] + knapsackMax(s - weights[index], weights, index + 1));
}

public static ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
combine(candidates, 0, target, results, new ArrayList<Integer>());
return results;
}
public static void combine(int[] candidates, int index, int target,
ArrayList<ArrayList<Integer>> results,
ArrayList<Integer> cur) {
if (target < 0) {
return;
}
if (target == 0) {
results.add(new ArrayList<Integer>(cur));
return;
}
for (int i = index; i < candidates.length; i++) {
cur.add(candidates[i]);
combine(candidates, i + 1, target-candidates[i], results, cur);
cur.remove(cur.size()-1);
while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
i++;
}
}
return;
}

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        if (nums == null) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        Arrays.sort(nums);
        helper(nums, results, cur, 0);
        return results;
    }
    private static void helper(int[] nums, List<List<Integer>> results, List<Integer> cur, int index) {
        results.add(new ArrayList(cur));
        for (int i = index; i < nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }
            cur.add(nums[i]);
            helper(nums, results, cur, i + 1);
            cur.remove(cur.size() - 1);
        }
    }
}

78. Subsets  QuestionEditorial Solution  My Submissions
Total Accepted: 113481
Total Submissions: 334182
Difficulty: Medium
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null) {
            return result;
        }
        List<Integer> cur = new ArrayList();
        helper(nums, result, cur, 0);
        return result;
    }
    private static void helper(int[] nums, List<List<Integer>> result, List<Integer> cur, int index) {
        result.add(new ArrayList(cur));
        for (int i = index; i < nums.length; i++) {
            cur.add(nums[i]);
            helper(nums, result, cur, i + 1);
            cur.remove(cur.size() - 1);
        }
    }
}

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        results.add(cur);
        if (nums == null || nums.length == 0) {
            return results;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = new ArrayList(results);
            for (List<Integer> now : results) {
                List<Integer> nowTemp = new ArrayList(now);
                nowTemp.add(nums[i]);
                temp.add(nowTemp);
            }
            results = new ArrayList(temp);
        }
        return results;
    }
}

47. Permutations II  QuestionEditorial Solution  My Submissions
Total Accepted: 85003
Total Submissions: 287703
Difficulty: Medium
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

public class Solution {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> listNow = new ArrayList();
        results.add(listNow);
        if (nums == null || nums.length == 0) {
            return results;
        }
        for (int i = 0; i < nums.length; ++i) {
            List<List<Integer>> temp = new ArrayList();
            for (List<Integer> list : results) {
                int size = list.size();
                for (int j = 0; j <= size; ++j) {
                    List<Integer> cur = new ArrayList(list);
                    cur.add(j, nums[i]);
                    if (!temp.contains(cur)) {
                        temp.add(cur);
                    }

                }
            }
            results = new ArrayList(temp);
        }
        return results;
    }
}

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        results.add(cur);
        if (nums == null || nums.length == 0) {
            return results;
        }
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = new ArrayList();
            for (List<Integer> now : results) {
                for (int j = 0; j <= now.size(); j++) {
                    List<Integer> nowTemp = new ArrayList(now);
                    nowTemp.add(j, nums[i]);
                    temp.add(nowTemp);
                }
            }
            results = new ArrayList(temp);
        }
        return results;
    }
}

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList();
        if (nums == null || nums.length == 0) {
            return results;
        }
        List<Integer> cur = new ArrayList();
        helper(nums, results, cur);
        return results;
    }
    public static void helper(int[] nums, List<List<Integer>> results, List<Integer> cur) {
        if (cur.size() == nums.length) {
            results.add(new ArrayList(cur));
        }
        for (int i = 0; i < nums.length; i++) {
            if (cur.contains(nums[i])) {
                continue;
            }
            cur.add(nums[i]);
            helper(nums, results, cur);
            cur.remove(cur.size() - 1);
        }
    }
}

Knapsack III
Given a collection of candidate numbers (C) and a target number (T), find all
unique combinations in C where the candidate numbers sums to T.
Candidate numbers may contain duplicate.
Each number in C may only be used once in the combination.

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        int[] w = {2, 3, 6, 7};
        System.out.println(knapsackIII(w, 7));
    }
    public static List<List<Integer>> knapsackIII(int[] w, int sum) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        combine(w, sum, 0, results, cur);
        return results;
    }
    public static void combine(int[] w, int sum, int index, List<List<Integer>> results, List<Integer> cur) {
        if (sum == 0) {
            results.add(new ArrayList(cur));
            return;
        }
        if (sum < 0 || index == w.length) {
            return;
        }
        for (int i = index; i < w.length; i++) {
            cur.add(w[i]);
            combine(w, sum - w[i], i + 1, results, cur);
            cur.remove(cur.size() - 1);
            while (i < w.length - 1 && w[i] == w[i + 1]) {
                i++;
            }
        }
    }
}

Given a set of candidate numbers (C) and a target number (T), find all unique
combinations in C where the candidate numbers sums to T.

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        int[] w = {2, 3, 6, 7};
        System.out.println(knapsackIII(w, 7));
    }
    public static List<List<Integer>> knapsackIII(int[] w, int sum) {
        List<List<Integer>> results = new ArrayList();
        List<Integer> cur = new ArrayList();
        combine(w, sum, 0, results, cur);
        return results;
    }
    public static void combine(int[] w, int sum, int index, List<List<Integer>> results, List<Integer> cur) {
        if (sum == 0) {
            results.add(new ArrayList(cur));
            return;
        }
        if (sum < 0 || index == w.length) {
            return;
        }
        for (int i = index; i < w.length; i++) {
            cur.add(w[i]);
            combine(w, sum - w[i], i, results, cur);
            cur.remove(cur.size() - 1);
        }
    }
}

Given a knapsack which can hold s pounds of items, and a set of items with
weight w1, w2, ... wn. Try to put items into the pack as many as possible, return
the largest weight we can get in the knapsack.

    public static int knapsackII(int[] w, int sum, int index) {
        if (sum == 0 || index == w.length) {
            return 0;
        }
        if (w[index] > sum) {
            return knapsackII(w, sum, index + 1);
        }
        return Math.max(knapsackII(w, sum, index + 1), w[index] + knapsackII(w, sum - w[index], index + 1));
    }

0-1 Knapsack
Given a knapsack which can hold s pounds of items, and a set of items with
weight w1, w2, ... wn. Return whether we can pick specific items so that their total
weight s.

public class Solution {
    public static void main(String[] args) {
        int[] w = {14, 8, 7, 5, 3};
        System.out.println(knapsack(w, 10, 0));

    }

    public static boolean knapsack(int[] w, int sum, int index) {
        if (sum == 0) {
            return true;
        }
        if (index == w.length || sum < 0) {
            return false;
        }
        return knapsack(w, sum - w[index], index + 1) || knapsack(w, sum, index + 1);
    }
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        System.out.println(solveNQueens(8).size());
    }
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList();
        int[] board = new int[n];
        placeNQueens(board, 0, results);
        return results;
    }
    public static void placeNQueens(int[] board, int row, List<List<String>> results) {
        if (row == board.length) {
            save(board, results);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isLegal(row, col, board)) {
                board[row] = col;
                placeNQueens(board, row + 1, results);
            }
        }
    }
    public static boolean isLegal(int row, int col, int[] board) {
        for (int i = row - 1; i >= 0; i--) {
            if (board[i] == col || Math.abs(board[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }
    public static void save(int[] board, List<List<String>> results) {
        List<String> curRow = new ArrayList();
        for (int i = 0; i < board.length; i++) {
            StringBuffer oneLine = new StringBuffer();
            for (int j = 0; j < board.length; j++) {
                if (board[i] == j) {
                    oneLine.append("Q");
                } else {
                    oneLine.append(".");
                }
            }
            curRow.add(oneLine.toString());

        }
        results.add(new ArrayList(curRow));
    }
}

Given a maze and a start point and a target point, print out the path to reach the
target.

public class Solution {
    public static boolean solveMaze(char[][] maze, int startX, int startY, int targetX, int targetY, String path) {
        if (startX < 0 || startX >= maze.length || startY < 0 || startY >= maze[0].length) {
            return false;
        }
        if (startX == targetX && startY == targetY) {
            System.out.println(path);
            return true;
        }
        maze[startX][startY] = 'X';
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        char[] direction = {'D', 'R', 'U', 'L'};
        for (int i = 0; i < 4; i++) {
            String newPath = path + direction[i] + " ";
            if (solveMaze(maze, startX + dx[i], startY + dy[i], targetX, targetY, newPath)) {
                return true;
            }
        }
        return false;
    }

}

0-1 Knapsack
Given a knapsack which can hold s pounds of items, and a set of items with
weight w1, w2, ... wn. Return whether we can pick specific items so that their total
weight s.
Example Input:
s = 20;
w = [14, 8, 7, 5, 3];
Example Output:
True;

public class Solution {
    public static void main(String[] args) {
        int s = 20;
        int[] w = {14, 8, 12, 5, 3};
        System.out.println(knapsack(s, w, 0));
    }
    public static boolean knapsack(int sum, int[] weights, int index) {
        if (sum == 0) {
            return true;
        }
        if (sum < 0 || index >= weights.length) {
            return false;
        }
        return knapsack(sum - weights[index], weights, index + 1) || knapsack(sum, weights, index + 1);
    }
}

public class Solution {
    public static void main(String[] args) {
        int[] w = {-14, -6, 7, 5, -3};
        System.out.println(knapsack(w, -17, 0));
    }

    public static boolean knapsack(int[] w, int sum, int index) {
        if (sum == 0) {
            return true;
        }
        if (index == w.length) {
            return false;
        }
        return knapsack(w, sum - w[index], index + 1) || knapsack(w, sum, index + 1);
    }
}

public class Solution {
    public int hanoi(int n) {
        if (n == 1) {
            return 1;
        }
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}

public class Solution {
    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
    }
    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            System.out.println("Move " + A + " to " + C);
            return;
        }
        hanoi(n - 1, A, C, B);
        System.out.println("Move " + A + " to " + C);
        hanoi(n - 1, B, A, C);
    }
}

There is a building with n stairs, one person can climb 1 or 2 stairs at one time. Print all
the possible ways to climb to the top.

public class Solution {

    public static void main(String[] args) {
        climb(3,"");
    }
    public static void climb(int n, String preWay) {
        if (n == 1) {
            System.out.println(preWay + " 1");
            return;
        }
        if (n == 2) {
            System.out.println(preWay + " 2");
            System.out.println(preWay + " 1 1");
            return;
        }
        climb(n - 1, preWay + " 1");
        climb(n - 2, preWay + " 2");
    }
}

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

public class Solution {
    public int maxArea(int[] height) {
        if (null == height || height.length == 0) {
            return 0;
        }
        int result = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            result = Math.max(result, (right - left) * Math.min(height[left], height[right]));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

public class Solution {
    public int trap(int[] height) {
        if (null == height || height.length == 1) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                int smaller = height[left];
                while (left < right && height[left] <= smaller) {
                    result += smaller - height[left];
                    left++;
                }
            } else {
                int smaller = height[right];
                while (left < right && height[right] <= smaller) {
                    result += smaller - height[right];
                    right--;
                }
            }
        }
        return result;
    }
}

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

class MyStack {
    // Push element x onto stack.
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    public MyStack() {
        queue1 = new LinkedList();
        queue2 = new LinkedList();
    }
    public void push(int x) {
        if (queue1.isEmpty()) {
            queue1.add(x);
            while (!queue2.isEmpty()) {
                queue1.add(queue2.poll());
            }
        } else {
            queue2.add(x);
            while (!queue1.isEmpty()) {
                queue2.add(queue1.poll());
            }
        }
    }

    // Removes the element on top of the stack.
    public void pop() {
        if (!queue1.isEmpty()) {
            queue1.poll();
        } else {
            queue2.poll();
        }
    }

    // Get the top element.
    public int top() {
        if (queue1.isEmpty()) {
            return queue2.peek();
        } else {
            return queue1.peek();
        }
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }
    public void push(int x) {
        stack1.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        stack2.pop();
    }

    // Get the front element.
    public int peek() {
         if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        if (stack1.isEmpty() && stack2.isEmpty()) {
            return true;
        }
        return false;
    }
}

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

import java.util.Stack;

public class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<String>();
        String[] strArray = path.split("/");
        for (int i = 0; i < strArray.length; i++) {
            String str = strArray[i];
            if (str.equals("") || str.equals(".")) {
                continue;
            } else if (str.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(str);
            }
        }
        if (stack.isEmpty()) {
            return "/";
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            String temp = "/" + stack.pop();
            result.insert(0, temp);
        }
        return result.toString();
    }
}

import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int area = 0;
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < heights.length; i++) {
            if (stack.isEmpty() || heights[stack.peek()] < heights[i]) {
                stack.push(i);
            } else {
                int start = stack.pop();
                int width = stack.isEmpty() ? i : i - 1 - stack.peek();
                area = Math.max(area, heights[start] * width);
                i--;
            }
        }
        while (!stack.isEmpty()) {
            int start = stack.pop();
            int width = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
            area = Math.max(area, heights[start] * width);
        }
        return area;
    }
}

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (null == heights || heights.length == 0) {
            return 0;
        }
        int area = 0;
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < heights.length; i++) {
            if (stack.isEmpty() || heights[stack.peek()] < heights[i]) {
                stack.push(i);
            } else {
                int index = stack.pop(); //现在处理的是他。
                int width = stack.isEmpty() ? i : i - (stack.peek() + 1); // 他的宽度是在从i这个位置减去他的前一个的下一个位置
                area = Math.max(area, heights[index] * width);
                i--;
            }
        }
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int width = stack.isEmpty() ? heights.length : heights.length - (stack.peek() + 1);
            area = Math.max(area, heights[index] * width);
        }
        return area;
    }
}

All the cows are facing right, and they can
only see other cows in front of it and
shorter than itself. It can be blocked by
other taller cows.
Example: 6 2 3 1 7 4 Output: 5

public static int seeCows(int[] cow) {
int length = cow.length;
int totalNum = 0;
Stack<Integer> cowStack = new Stack<Integer>();
for(int i = 0; i < length; i ++){
if(cowStack.size() == 0 || cowStack.peek() > cow[i]) {
cowStack.push(cow[i]);
}
else {
while(cowStack.size() > 0 && cowStack.peek() <= cow[i]) {
cowStack.pop();
totalNum += cowStack.size();
}
cowStack.push(cow[i]);
}
}
while(cowStack.size() > 0) {
cowStack.pop();
totalNum += cowStack.size();
}
return totalNum;
}

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

public class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else {
            if (x < minStack.peek()) {
                minStack.push(x);
            } else {
                minStack.push(minStack.peek());
            }
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class Queue<T> {
    private int front;
    private int rear;
    private int capacity;
    private int size;
    T[] queue;
    public Queue(int inCapacity) {
        capacity = inCapacity;
        queue = (T[])new Object[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }
    public int size() {
        return size;
    }
    public void add(T value) {
        if (size == capacity) {
            throw new IllegalStateException("Queue is full.");
        } else {
            queue[rear] = value;
            rear = (rear + 1) % capacity;
            size++;
        }
    }
    public T remove() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty.");
        } else {
            T res = queue[front];
            front = (front + 1) % capacity;
            size--;
            return res;
        }
    }

}

class Stack<T> {
    private int top;
    private int capacity;
    private T[] stack;
    public Stack(int inCapacity) {
        capacity = inCapacity;
        stack = (T[])new Object[capacity];
        top = -1;
    }
    public void push(T value) {
        if (top + 1 == capacity) {
            throw new IllegalStateException("Stack is full.");
        } else {
            stack[++top] = value;
        }
    }
    public T pop() {
        if (top == -1) {
            throw new IllegalStateException("Stack is empty.");
        } else {
            return stack[top--];
        }
    }
    public T peek() {
        if (top == -1) {
            throw new IllegalStateException("Stack is empty.");
        } else {
            return stack[top];
        }
    }
}

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k < 1) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode tail = dummy;
        while (true) {
            int count = k;
            while (count > 0 && tail != null) {
                count--;
                tail = tail.next;
            }
            if (tail == null) {
                break;
            }
            ListNode next = pre.next;
            while (pre.next != tail) {
                ListNode temp = pre.next;
                pre.next = pre.next.next;
                temp.next = tail.next;
                tail.next = temp;
            }
            pre = next;
            tail = next;
        }
        return dummy.next;
    }
}

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode smallDummy = new ListNode(-1);
        ListNode bigDummy = new ListNode(-1);
        ListNode small = smallDummy;
        ListNode big = bigDummy;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = bigDummy.next;
        return smallDummy.next;
    }
}

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // find the middle
        ListNode middle = findMiddle(head);

        // reverse the last part
        System.out.println(middle.val);
        ListNode right = middle.next;
        middle.next = null;
        ListNode newNode = reverse(right);
        // insert
        ListNode first = head;
        ListNode second = newNode;

        while (second != null) {
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;
            first.next = second;
            first.next.next = temp1;
            second = temp2;
            first = temp1;
        }
    }
    public static ListNode findMiddle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public static ListNode reverse(ListNode right) {
        ListNode newNode = null;
        ListNode cur = right;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = newNode;
            newNode = cur;
            cur = temp;
        }
        return newNode;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = head;

        while (cur != null) {
            ListNode pre = dummy;
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            ListNode temp = pre.next;
            pre.next = new ListNode(cur.val);
            pre.next.next = temp;
            cur = cur.next;
        }
        return dummy.next;
    }
}

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3
begin to intersect at node c1.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        if (lenA >= lenB) {
            return getNode(headA, headB, lenA, lenB);
        } else {
            return getNode(headB, headA, lenB, lenA);
        }
    }
    public static ListNode getNode(ListNode max, ListNode min, int maxLen, int minLen) {

        ListNode maxNode = max;
        ListNode minNode = min;
        for (int i = 0; i < maxLen - minLen; i++) {
            maxNode = maxNode.next;
        }
        while (maxNode != null && minNode != null) {
            if (maxNode == minNode) {
                return maxNode;
            }
            maxNode = maxNode.next;
            minNode = minNode.next;
        }
        return null;
    }
    public static int getLength(ListNode head) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
}

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given ->->->, you should ->->->.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            ListNode first = pre.next;
            ListNode second = pre.next.next;
            ListNode temp = second.next;
            pre.next = second;
            second.next = first;
            first.next = temp;
            pre = pre.next.next;
        }
        return dummy.next;
    }
}

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        int value = 0;
        int digit = 0;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode cur = dummy;
        while (cur1 != null && cur2 != null) {
            value = cur1.val + cur2.val + digit;
            digit = value / 10;
            cur.next = new ListNode(value % 10);
            cur = cur.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        while (cur1 != null) {
            value = cur1.val + digit;
            digit = value / 10;
            cur.next = new ListNode(value % 10);
            cur = cur.next;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            value = cur2.val + digit;
            digit = value / 10;
            cur.next = new ListNode(value % 10);
            cur = cur.next;
            cur2 = cur2.next;
        }
        if (digit != 0) {
            cur.next = new ListNode(digit);
        }
        return dummy.next;
    }
}

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m <= 0 || n <= 0) {
            return head;
        }
        // find pre
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode start = pre.next;
        ListNode cur = start.next;
        for (int i = 0; i < n - m; i++) {
            start.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = start.next;
        }
        return dummy.next;
    }
}

Reverse a singly linked list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode newHead = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = temp;
        }
        return newHead;
    }
}

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode node1 = l1;
        ListNode node2 = l2;
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return newHead.next;
    }
}

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            if (pre.next.val == pre.next.next.val) {
                int val = pre.next.val;
                while (pre.next != null && pre.next.val == val) {
                    pre.next = pre.next.next;
                }
            } else {
                pre = pre.next;
            }
        }
        return dummy.next;
    }
}

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            while (next != null && next.val == cur.val) {
                cur.next = next.next;
                next = next.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast != slow) {
            return null;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

Given a linked list, determine if it has a cycle in it.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

class ListNode {
    ListNode head;
    ListNode next;
    int val;
    ListNode(int x) {
        val = x;
    }
}

public class LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(midNode(head).val);
    }
    public static ListNode midNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0) {
            return null;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode first = dummy;
        for (int i = 0; i < n; i++) {
            if (first == null) {
                return head;
            }
            first = first.next;
        }
        ListNode second = dummy;
        while (first.next != null) {
            second = second.next;
            first = first.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

class ListNode {
    ListNode head;
    ListNode next;
    int val;
    ListNode(int x) {
        val = x;
    }
}

public class LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        System.out.println(kthNodeFromEnd(head, 2).val);
    }
    public static ListNode kthNodeFromEnd(ListNode head, int k) {
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < k; i++) {
            if (first == null) {
                return null;
            }
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }
}

class ListNode {
    ListNode head;
    ListNode next;
    int val;
    ListNode(int x) {
        val = x;
    }
}

public class LinkedList {
    private static ListNode head = null;
    private static int length = 0;
    public static boolean checkBoundsExclusive(int index) {
        if (index < 0 || index >= length) {
            System.out.println("ArrayIndexOutOfBoundException");
            return true;
        } else {
            return false;
        }
    }
    public static ListNode getEntry(int index) {
        if (!checkBoundsExclusive(index)) {
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur;
        } else {
            return null;
        }
    }
    public static void set(int index, int value) {
        if (!checkBoundsExclusive(index)) {
            ListNode node = getEntry(index);
            node.val = value;
        }
    }
    public static void add(int index, int value) {
        if (!checkBoundsExclusive(index)) {
            ListNode newNode = new ListNode(value);
            if (index == 0) {
                newNode.next = head;
                head = newNode;
                return;
            }
            ListNode pre = getEntry(index - 1);
            ListNode next = pre.next;
            pre.next = newNode;
            pre.next.next = next;
        }
    }
    public static void remove(int index) {
        if (!checkBoundsExclusive(index)) {
            if (index == 0) {
                head = head.next;
            }
            ListNode pre = getEntry(index - 1);
            pre.next = pre.next.next;
        }
    }
}

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean isNegative = dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0;
        long x = Math.abs((long) dividend);
        long y = Math.abs((long) divisor);
        int result = 0;
        while (x >= y) {
            int shift = 0;
            while (x >= (y << shift)) {
                shift++;
            }
            result += 1 << (shift - 1);
            x = x - (y << (shift - 1));
        }
        return isNegative ? -result : result;
    }
}

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

public class Solution {
    public int numDistinct(String s, String t) {
        if (s == null) {
            return 0;
        }
        if (t == null) {
            return 1;
        }
        int lenS = s.length();
        int lenT = t.length();
        int[][] dp = new int[lenS + 1][lenT + 1];
        // 前lenS，前lenT里面有多少个。
        for (int i = 0; i < lenS; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= lenS; i++) {
            for (int j = 1; j <= lenT; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[lenS][lenT];
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}

iven a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int size = triangle.size();
        for (int i = size - 2; i >= 0; i--) {
            // find the min
            for (int j = 0; j <= i; j++) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[2];
        int max = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i % 2] = Math.max(dp[(i - 1) % 2] + nums[i], nums[i]);
            max = Math.max(max, dp[i % 2]);
        }
        return max;
    }
}

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Subscribe to see which companies asked this question

public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i % 2] = dp[(i - 1) % 2] + dp[(i - 2) % 2];
        }
        return dp[(n - 1) % 2];
    }
}

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[2][n];
        dp[0][0] = grid[0][0];
        // for (int i = 1; i < m; i++) {
        //     dp[i][0] = dp[i - 1][0] + grid[i][0];
        // }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            dp[i % 2][0] = dp[(i - 1) % 2][0] + grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]) + grid[i][j];
            }
        }
        return dp[(m - 1) % 2][n - 1];
    }
}

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        // initialize
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] != 1) {
                dp[i][0] = 1;
            } else {
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] != 1) {
                dp[0][j] = 1;
            } else {
                break;
            }
        }
        // calculate
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[2][n];
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] != 1) {
                dp[0][j] = 1;
            } else {
                break;
            }
        }
        // calculate
        for (int i = 1; i < m; i++) {
            if (dp[(i - 1) % 2][0] != 0 && obstacleGrid[i][0] != 1) {
                dp[i % 2][0] = 1;
            } else {
                dp[i % 2][0] = 0;
            }
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1];
                } else {
                    dp[i % 2][j] = 0;
                }
            }
        }
        return dp[(m - 1) % 2][n - 1];
    }
}

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

public class Solution {
    public int uniquePaths(int m, int n)
    {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Solution {
    public int uniquePaths(int m, int n)
    {
        int[][] dp = new int[2][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i % 2][0] = 1;
            for (int j = 1; j < n; j++) {
                dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1];
            }
        }
        return dp[(m - 1) % 2][n - 1];
    }
}

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int x = m - 1;
        int y = 0;
        // 从左下角开始出发。
        while (x >= 0 && y < n) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                y++;
            } else if (matrix[x][y] > target) {
                x--;
            }
        }
        return false;
    }
}

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (null == matrix || matrix.length == 0) {
            return false;
        }
        // find the row
        int up = 0;
        int down = matrix.length - 1;
        int row = 0;
        while (up <= down) {
            int mid = up + (down - up) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                row = mid;
                up = mid + 1;
            } else {
                down = mid - 1;
            }
        }
        int left = 0;
        int right = matrix[0].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

public class Solution {
    public int findMin(int[] nums) {
        if (null == nums || nums.length == 0) {
            return -1;
        }
        int min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
        }
        return min;
    }
}

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1 || nums[0] < nums[nums.length - 1]) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] < nums[right]) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid - 1;
            } else {
                right--;
            }
        }
        return nums[right + 1];
    }
}

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Subscribe to see which companies asked this question

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] <= nums[right]) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[right] < nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

. Sqrt(x)  QuestionEditorial Solution  My Submissions
Total Accepted:
Total Submissions:
Difficulty: Medium
Implement int sqrt(int x).

Compute and return the square root of x.

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int left = 1;
        int right = x / 2;
        int result = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x / mid == mid) {
                return mid;
            }
            if (x / mid > mid) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > nums[right]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[right] == target) {
                    return true;
                }
                right--;
            }
        }
        return false;
    }
}

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        return -1;
    }
}

Insertion Position
Instead of giving -1 when search fails, give the index that
the number could be inserted and maintain the order
Copyright ©