@Yano 2015-12-30T03:20:27.000000Z 字数 39021 阅读 33606

# LeetCode之Array题目汇总

LeetCode

LeetCode 题目汇总

# Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

    public int[] twoSum(int[] nums, int target) {        if (nums == null || nums.length <= 1) {            return new int[2];        }        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        // key = target - nums[i], just one solution        for (int i = 0; i < nums.length; i++) {            map.put(target - nums[i], i);        }        for (int i = 0; i < nums.length; i++) {            Integer v = map.get(nums[i]);            // can't use itself            if (v != null && v != i) {                return new int[] { i + 1, v + 1 };            }        }        return null;    }

# 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)


1. 对数组进行排序；
2. start从0到n-1，对num[start]求另外两个数，这里用mid和end；
3. mid指向start+1，q指向结尾。sum = num[start] + num[mid]+ num[end]；
4. 利用加逼定理求解，终止条件是mid == end；
5. 顺带去重

1. 如果start到了start+1，num[start] == num[start - 1]，则求出的解肯定重复了；
2. 如果mid++，num[mid] = num[mid - 1]，则求出的解肯定重复了。
    public List<List<Integer>> threeSum(int[] nums) {        if (nums == null || nums.length < 3) {            return new ArrayList<List<Integer>>();        }        Set<List<Integer>> set = new HashSet<List<Integer>>();        Arrays.sort(nums);        for (int start = 0; start < nums.length; start++) {            if (start != 0 && nums[start - 1] == nums[start]) {                continue;            }            int mid = start + 1, end = nums.length - 1;            while (mid < end) {                int sum = nums[start] + nums[mid] + nums[end];                if (sum == 0) {                    List<Integer> tmp = new ArrayList<Integer>();                    tmp.add(nums[start]);                    tmp.add(nums[mid]);                    tmp.add(nums[end]);                    set.add(tmp);                    while (++mid < end && nums[mid - 1] == nums[mid])                        ;                    while (--end > mid && nums[end + 1] == nums[end])                        ;                }                else if (sum < 0) {                    mid++;                }                else {                    end--;                }            }        }        return new ArrayList<List<Integer>>(set);    }

# 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


    public int threeSumClosest(int[] nums, int target) {        if (nums == null || nums.length < 3) {            return Integer.MIN_VALUE;        }        Arrays.sort(nums);        int minGap = Integer.MAX_VALUE;        int result = 0;        for (int start = 0; start < nums.length; start++) {            int mid = start + 1, end = nums.length - 1;            while (mid < end) {                int sum = nums[start] + nums[mid] + nums[end];                int gap = Math.abs(sum - target);                if (gap < minGap) {                    minGap = gap;                    result = sum;                }                if (sum < target) {                    mid++;                } else {                    end--;                }            }        }        return result;    }

# 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, abcd)
• The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1,  0, 0, 1)
(-2, -1, 1, 2)
(-2,  0, 0, 2)


    public List<List<Integer>> fourSum(int[] nums, int target) {        if (nums == null || nums.length < 4) {            return new ArrayList<List<Integer>>();        }        Arrays.sort(nums);        Set<List<Integer>> set = new HashSet<List<Integer>>();        // 和3Sum一样，只是多了一个循环        for (int a = 0; a < nums.length - 3; a++) {            int target_3Sum = target - nums[a];            for (int b = a + 1; b < nums.length - 2; b++) {                int c = b + 1, d = nums.length - 1;                while (c < d) {                    int sum = nums[b] + nums[c] + nums[d];                    if (sum == target_3Sum) {                        // 将结果加入集合                        List<Integer> tmp = new ArrayList<Integer>();                        tmp.add(nums[a]);                        tmp.add(nums[b]);                        tmp.add(nums[c]);                        tmp.add(nums[d]);                        set.add(tmp);                        // 去重                        while (++c < d && nums[c - 1] == nums[c])                            ;                        while (--d > c && nums[d + 1] == nums[d])                            ;                    }                    else if (sum < target_3Sum) {                        c++;                    } else {                        d--;                    }                }            }        }        return new ArrayList<List<Integer>>(set);    }

# Best Time to Buy and Sell Stock

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.

• lowest：当前prices最小值
• maxProfit：当前profit最大值
prices 7 2 3 6 1 9
lowest 7 2 2 2 1 1
maxProfit 0 0 1 4 4 8
    public int maxProfit(int[] prices) {        if (prices.length <= 1) {            return 0;        }        int maxProfit = 0;        int lowest = Integer.MAX_VALUE;        for (int v : prices) {            lowest = Math.min(v, lowest);            maxProfit = Math.max(maxProfit, v - lowest);        }        return maxProfit;    }

# Best Time to Buy and Sell Stock II

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).

prices 7 2 3 6 1 9
profit 0 0 1 4 4 12
    public int maxProfit(int[] prices) {        int profit = 0;        for (int i = 1; i < prices.length; i++) {            if (prices[i - 1] < prices[i]) {                profit += prices[i] - prices[i - 1];            }        }        return profit;    }

# Combination Sum

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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• 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 List<List<Integer>> combinationSum(int[] candidates, int target) {        if (candidates == null || candidates.length == 0) {            return new ArrayList<List<Integer>>();        }        List<List<Integer>> result = new ArrayList<List<Integer>>();        ArrayList<Integer> cur = new ArrayList<Integer>();        Arrays.sort(candidates);        dfs(0, target, result, cur, candidates);        return result;    }    private void dfs(int start, int target, List<List<Integer>> result,            ArrayList<Integer> cur, int[] candidates) {        if (target == 0) {            result.add(new ArrayList<Integer>(cur));            return;        }        for (int i = start; i < candidates.length; i++) {            // candidates[i] > target，则递归结束，后面不可能是解            if (candidates[i] > target) {                return;            }            cur.add(candidates[i]);            dfs(i, target - candidates[i], result, cur, candidates);            cur.remove(cur.size() - 1);        }    }

# Combination Sum II

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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• 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]

1. Combination Sum每个元素可以使用多次，所以递归是dfs(i, target - candidates[i], result, cur, candidates);
2. Combination Sum II每个元素只能使用一次，所以递归是dfs(i + 1, target - candidates[i], rt, cur, candidates);因为解可能重复，所以使用set，最后转成list。
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        if (candidates == null || candidates.length == 0) {            return new ArrayList<List<Integer>>();        }        Set<List<Integer>> rt = new HashSet<List<Integer>>();        ArrayList<Integer> cur = new ArrayList<Integer>();        Arrays.sort(candidates);        dfs(0, target, rt, cur, candidates);        return new ArrayList<List<Integer>>(rt);    }    private void dfs(int start, int target, Set<List<Integer>> rt,            ArrayList<Integer> cur, int[] candidates) {        if (target == 0) {            rt.add(new ArrayList<Integer>(cur));            return;        }        for (int i = start; i < candidates.length; i++) {            // candidates[i] > target，则递归结束，后面不可能是解            if (candidates[i] > target) {                return;            }            cur.add(candidates[i]);            dfs(i + 1, target - candidates[i], rt, cur, candidates);            cur.remove(cur.size() - 1);        }    }

# Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]


Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]


Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

    public List<List<Integer>> combinationSum3(int k, int n) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (k < 1 || n < 1) {            return rt;        }        List<Integer> cur = new ArrayList<Integer>();        dfs(rt, cur, 0, k, n, 1);        return rt;    }    private void dfs(List<List<Integer>> rt, List<Integer> cur, int sum, int k,            int n, int level) {        if (sum == n && k == 0) {            rt.add(new ArrayList<Integer>(cur));            return;        } else if (sum > n || k <= 0) {            return;        }        for (int i = level; i <= 9; i++) {            cur.add(i);            dfs(rt, cur, sum + i, k - 1, n, i + 1);            cur.remove(cur.size() - 1);        }    }

# Construct Binary Tree from Preorder and Inorder Traversal

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

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

• 前序遍历p：1 2 4 3 5 6
• 中序遍历i：4 2 1 5 3 6

    1
/ \
2   3
/   / \
4   5   6


• p[1...2]是1的左子树的前序遍历，i[0...1]是1的左子树的中序遍历
• p[3...5]是1的右子树的前序遍历，i[3...5]是1的右子树的中序遍历
• 递归
    int p = 0;    int[] preorder;    int[] inorder;    public TreeNode buildTree(int[] preorder, int[] inorder) {        this.preorder = preorder;        this.inorder = inorder;        return buildTree(0, preorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(preorder[p]);        int i;        for (i = start; i < end && preorder[p] != inorder[i]; i++)            ;        p++;        root.left = buildTree(start, i);        root.right = buildTree(i + 1, end);        return root;    }

# Construct Binary Tree from Inorder and Postorder Traversal

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

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

    int p;    int[] postorder;    int[] inorder;    public TreeNode buildTree(int[] inorder, int[] postorder) {        this.p = postorder.length - 1;        this.inorder = inorder;        this.postorder = postorder;        return buildTree(0, postorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(postorder[p]);        int i;        for (i = start; i < end && postorder[p] != inorder[i]; i++)            ;        p--;        root.right = buildTree(i + 1, end);        root.left = buildTree(start, i);        return root;    }

# Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

    public boolean containsDuplicate(int[] nums) {        Set<Integer> s = new HashSet<Integer>();        for (int n : nums) {            if (s.contains(n)) {                return true;            }            s.add(n);        }        return false;    }

# Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

    public boolean containsNearbyDuplicate(int[] nums, int k) {        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        for (int i = 0; i < nums.length; i++) {            if (map.containsKey(nums[i])) {                if (i - map.get(nums[i]) <= k) {                    return true;                }            }            map.put(nums[i], i);        }        return false;    }

# Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if (k < 1 || t < 0 || nums == null || nums.length < 2) {            return false;        }        SortedSet<Long> set = new TreeSet<Long>();        for (int j = 0; j < nums.length; j++) {            SortedSet<Long> subSet = set.subSet((long) nums[j] - t,                    (long) nums[j] + t + 1);            // 集合不为空，则表示找到解            if (!subSet.isEmpty()) {                return true;            }            if (j >= k) {                set.remove((long) nums[j - k]);            }            set.add((long) nums[j]);        }        return false;    }

# Find Minimum in Rotated Sorted Array

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.

1. n[s] < n[e]
2. n[m] > n[s] > n[e]
3. n[m] < n[e] < n[s]

0 1 2 4 5 6 7

4 5 6 7 0 1 2

n[s] = 4n[m] = 7n[e] = 2

6 7 0 1 2 4 5

n[m] < n[e]，在本例中：

n[s] = 6n[m] = 1n[e] = 5

    public int findMin(int[] nums) {        if (nums.length == 1) {            return nums[0];        }        if (nums.length == 2) {            return Math.min(nums[0], nums[1]);        }        int s = 0, e = nums.length - 1;        int m = (s + e) / 2;        if (nums[s] < nums[e]) {            return nums[s];        }        if (nums[m] > nums[s]) {            return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));        }        return findMin(Arrays.copyOfRange(nums, s, m + 1));    }

# Find Peak Element

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.

Note:

Your solution should be in logarithmic complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

    public int findPeakElement(int[] nums) {        int low = 0;        int high = nums.length - 1;        while (low < high) {            int mid = low + (high - low) / 2;            if (nums[mid] > nums[mid + 1]) {                high = mid;            } else {                low = mid + 1;            }        }        return low;    }

# Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

dead->live    01dead->dead    00live->dead    10live->live    11

    public void gameOfLife(int[][] board) {        if (board == null || board.length == 0 || board[0] == null                || board[0].length == 0)            return;        int m = board.length;        int n = board[0].length;        // 判断每个点，下一时刻的状态        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                int x = getLiveNum(board, i, j);                if (board[i][j] == 0) {                    if (x == 3)                        board[i][j] += 10;                } else {                    if (x == 2 || x == 3)                        board[i][j] += 10;                }            }        }        // 更新每个点的状态        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                board[i][j] /= 10;            }        }    }    // 获取board[x][y]邻居live的数量    private int getLiveNum(int[][] board, int x, int y) {        int c = 0;        for (int i = x - 1; i <= x + 1; i++) {            for (int j = y - 1; j <= y + 1; j++) {                if (i < 0 || j < 0 || i > board.length - 1                        || j > board[0].length - 1 || (i == x && j == y))                    continue;                if (board[i][j] % 10 == 1)                    c++;            }        }        return c;    }

# Jump Game

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 boolean canJump(int[] nums) {        if (nums == null || nums.length == 0) {            return false;        }        int maxStep = 0;        for (int i = 0; i < nums.length; i++) {            if (maxStep >= nums.length - 1) {                return true;            }            if (nums[i] == 0 && maxStep == i) {                return false;            }            maxStep = Math.max(maxStep, nums[i] + i);        }        return true;    }

# Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

A Linear Time Majority Vote Algorithm 一个典型的算法，可以在一次遍历，时间复杂度是O(1)，空间复杂度是O(1)的情况下完成。

    public int majorityElement(int[] nums) {        int m = nums[0];        int c = 1;        for (int i = 1; i < nums.length; i++) {            if (m == nums[i]) {                c++;            } else if (c > 1) {                c--;            } else {                m = nums[i];            }        }        return m;    }

# Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

    public List<Integer> majorityElement(int[] nums) {        List<Integer> rt = new ArrayList<Integer>();        if (nums == null || nums.length == 0) {            return rt;        }        int m1 = nums[0];        int m2 = 0;        int c1 = 1;        int c2 = 0;        for (int i = 1; i < nums.length; i++) {            int x = nums[i];            if (x == m1) {                c1++;            } else if (x == m2) {                c2++;            } else if (c1 == 0) {                m1 = x;                c1 = 1;            } else if (c2 == 0) {                m2 = x;                c2 = 1;            } else {                c1--;                c2--;            }        }        c1 = 0;        c2 = 0;        for (int i = 0; i < nums.length; i++) {            if (m1 == nums[i]) {                c1++;            } else if (m2 == nums[i]) {                c2++;            }        }        if (c1 > nums.length / 3) {            rt.add(m1);        }        if (c2 > nums.length / 3) {            rt.add(m2);        }        return rt;    }

# Maximum Subarray

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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

curSum存储数组当前的和，maxSum存储数组中连续最大的和。

1. 当i=1时，对于数组[-2,1]，curSum + nums[1] = -1, 小于nums[1] = 1。所以以后-2就可以舍弃，计算curSum时就从i=1开始。
2. 当i=2时，对于数组[-2,1,-3]，curSum + nums[2] = -2, 大于nums[2] = -3。虽然没有比原来大，但是至少比nums[2]大，对于以后计算更接近最优解。
3. 以此类推。

    public int maxSubArray(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int curSum = nums[0];        int maxSum = nums[0];        for (int i = 1; i < nums.length; i++) {            curSum = Math.max(curSum + nums[i], nums[i]);            maxSum = Math.max(curSum, maxSum);        }        return maxSum;    }

# Maximum Product Subarray

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.

LeetCode第53题Maximum Subarray是求连续和最大的子数组，本题是求连续乘积最大的子数组。

    public int maxProduct(int[] nums) {        int max = nums[0];        int positive = nums[0];        int negative = nums[0];        for (int i = 1; i < nums.length; i++) {            positive *= nums[i];            negative *= nums[i];            if (positive < negative) {                int t = positive;                positive = negative;                negative = t;            }            positive = Math.max(positive, nums[i]);            negative = Math.min(negative, nums[i]);            max = Math.max(max, positive);        }        return max;    }

# Merge Sorted Array

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 int help(int[] nums, int k) {        if (k < 0) {            return Integer.MIN_VALUE;        }        return nums[k];    }    public void merge(int[] nums1, int m, int[] nums2, int n) {        if (nums1 == null || nums2 == null) {            return;        }        int t = m + n - 1;        while (t >= 0) {            int n1 = help(nums1, m - 1);            int n2 = help(nums2, n - 1);            if (n1 > n2) {                nums1[t] = n1;                m--;            } else {                nums1[t] = n2;                n--;            }            t--;        }    }

# Minimum Path Sum

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 int minPathSum(int[][] grid) {        if (grid == null || grid[0] == null) {            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 y = 1; y < n; y++) {            dp[0][y] = dp[0][y - 1] + grid[0][y];        }        for (int x = 1; x < m; x++) {            dp[x][0] = dp[x - 1][0] + grid[x][0];        }        for (int y = 1; y < n; y++) {            for (int x = 1; x < m; x++) {                int min = Math.min(dp[x - 1][y], dp[x][y - 1]);                dp[x][y] = min + grid[x][y];            }        }        return dp[m - 1][n - 1];    }

# Minimum Size Subarray Sum

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.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

    public int minSubArrayLen(int s, int[] nums) {        int sum = 0;        int st = 0;        int min = Integer.MAX_VALUE;        for (int i = 0; i < nums.length; i++) {            sum += nums[i];            if (sum >= s) {                while (sum - nums[st] >= s) {                    sum -= nums[st++];                }                min = Math.min(min, i - st + 1);            }        }        if (min > nums.length) {            return 0;        }        return min;    }

# Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

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

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    public int missingNumber(int[] nums) {        int rt = nums.length;        for (int i = 0; i < nums.length; i++) {            rt = rt ^ nums[i] ^ i;        }        return rt;    }

# Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    public void moveZeroes(int[] nums) {        int t = 0;        // 把非0元素移到前面        for (int i = 0; i < nums.length; i++) {            if (nums[i] != 0) {                nums[t++] = nums[i];            }        }        // 把后面元素值0        for (int i = t; i < nums.length; i++) {            nums[i] = 0;        }    }

# Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

    public void nextPermutation(int[] nums) {        if (nums == null || nums.length < 2) {            return;        }        int p = 0;        for (int i = nums.length - 2; i >= 0; i--) {            if (nums[i] < nums[i + 1]) {                p = i;                break;            }        }        int q = 0;        for (int i = nums.length - 1; i > p; i--) {            if (nums[i] > nums[p]) {                q = i;                break;            }        }        if (p == 0 && q == 0) {            reverse(nums, 0, nums.length - 1);            return;        }        int temp = nums[p];        nums[p] = nums[q];        nums[q] = temp;        if (p < nums.length - 1) {            reverse(nums, p + 1, nums.length - 1);        }    }    private void reverse(int[] nums, int left, int right) {        while (left < right) {            int temp = nums[left];            nums[left] = nums[right];            nums[right] = temp;            left++;            right--;        }    }

# Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

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


    public List<List<Integer>> generate(int numRows) {        ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();        Integer[] pre = null;        for (int i = 1; i <= numRows; i++) {            //must be defined as Integer[]            Integer[] row = new Integer[i];            row[0] = 1;            row[i - 1] = 1;            for (int j = 1; j < i - 1; j++) {                row[j] = pre[j] + pre[j - 1];            }            rt.add(new ArrayList<Integer>(Arrays.asList(row)));            pre = row;        }        return rt;    }

# Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

    public List<Integer> getRow(int rowIndex) {        Integer[] row = new Integer[rowIndex + 1];        Arrays.fill(row, 1);        for (int i = 0; i < rowIndex - 1; i++) {            for (int j = i + 1; j >= 1; j--) {                row[j] = row[j] + row[j - 1];            }        }        return Arrays.asList(row);    }

# Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

    public int[] plusOne(int[] digits) {        if (digits == null || digits.length == 0) {            return null;        }        int[] rt = new int[digits.length + 1];        digits[digits.length - 1]++;        for (int i = digits.length - 1; i >= 0; i--) {            rt[i + 1] += digits[i];            rt[i] += rt[i + 1] / 10;            rt[i + 1] %= 10;        }        if (rt[0] == 0) {            return Arrays.copyOfRange(rt, 1, rt.length);        } else {            return rt;        }    }

# Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

left[i]：存放nums[i]之前的乘积
right[i]：存放nums[i]之后的乘积

    public int[] productExceptSelf(int[] nums) {        int[] rt = new int[nums.length];        rt[nums.length - 1] = 1;        for (int i = nums.length - 2; i >= 0; i--) {            rt[i] = rt[i + 1] * nums[i+1];        }        int left = 1;        for (int i = 0; i < nums.length; i++) {            rt[i] *= left;            left *= nums[i];        }        return rt;    }

# Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

    public int removeDuplicates(int[] nums) {        if (nums == null) {            return -1;        }        if (nums.length < 2) {            return nums.length;        }        int len = 0;        for (int i = 1; i < nums.length; i++) {            if (nums[len] != nums[i]) {                nums[++len] = nums[i];            }        }        return len + 1;    }

# Remove Duplicates from Sorted Array II

What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

    public int removeDuplicates(int[] nums) {        int cur = 2;        for (int i = cur; i < nums.length; i++) {            // 一个数字，最多出现2次            if (!(nums[i] == nums[cur - 1] && nums[i] == nums[cur - 2])) {                nums[cur++] = nums[i];            }        }        return Math.min(cur, nums.length);    }

# Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

    public int removeElement(int[] nums, int val) {        if (nums == null || nums.length == 0) {            return 0;        }        int len = 0;        for (int i = 0; i < nums.length; i++) {            if (nums[i] != val) {                nums[len++] = nums[i];            }        }        return len;    }

# Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

    void reverse(int[] nums, int st, int ed) {        while (st < ed) {            int t = nums[st];            nums[st] = nums[ed];            nums[ed] = t;            st++;            ed--;        }    }    public void rotate(int[] nums, int k) {        int length = nums.length;        k = k % length;        if (length == 1 || k == 0)            return;        reverse(nums, 0, length - k - 1);        reverse(nums, length - k, length - 1);        reverse(nums, 0, length - 1);    }

# Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Could you do this in-place?

    public void rotate(int[][] matrix) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {            return;        }        final int mx = matrix.length;        final int my = matrix[0].length;        int x, y;        int t;        int _my = my - 1;        for (x = 0; x < mx - 1; x++) {            for (y = 0; y < _my; y++) {                int ny = mx - 1 - x;                int nx = my - 1 - y;                t = matrix[y][x];                matrix[y][x] = matrix[ny][nx];                matrix[ny][nx] = t;            }            _my--;        }        for (x = 0; x < mx; x++) {            for (y = 0; y < my / 2; y++) {                int ny = my - 1 - y;                int nx = x;                t = matrix[y][x];                matrix[y][x] = matrix[ny][nx];                matrix[ny][nx] = t;            }        }    }

# Search a 2D Matrix

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 boolean searchMatrix(int[][] matrix, int target) {        int mx = matrix.length;        int my = matrix[0].length;        int l = 0;        int r = mx * my;        while (l < r) {            int m = l + (r - l) / 2;            // 将m转换成x、y            int x = m / my;            int y = m % my;            // 二分查找：matrix[x][y]转换成一维数组，坐标就是m            if (matrix[x][y] == target) {                return true;            } else if (matrix[x][y] < target) {                l = m + 1;            } else {                r = m;            }        }        return false;    }

# Search for a Range

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 int[] searchRange(int[] nums, int target) {        int l = 0, r = nums.length;        while (l < r) {            int m = l + (r - l) / 2;            if (nums[m] == target) {                int s = m, e = m;                while (s - 1 >= 0 && nums[s - 1] == target) {                    s--;                }                while (e + 1 < nums.length && nums[e + 1] == target) {                    e++;                }                return new int[] { s, e };            } else if (nums[m] > target) {                r = m;            } else {                l = m + 1;            }        }        return new int[] { -1, -1 };    }

# Search in Rotated Sorted Array

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 int search(int[] nums, int target) {        int l = 0, r = nums.length - 1;        while (l <= r) {            int m = (l + r) / 2;            if (nums[m] == target)                return m;            if (nums[l] < nums[m]) {                if (target <= nums[m] && target >= nums[l])                    r = m - 1;                else                    l = m + 1;            } else if (nums[l] > nums[m]) {                if (target >= nums[l] || target <= nums[m])                    r = m - 1;                else                    l = m + 1;            } else                l++;        }        return -1;    }

# Search in Rotated Sorted Array II

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 boolean search(int[] nums, int target) {        int l = 0, r = nums.length - 1;        while (l <= r) {            int m = (l + r) / 2;            if (nums[m] == target)                return true;            if (nums[l] < nums[m]) {                if (target <= nums[m] && target >= nums[l])                    r = m - 1;                else                    l = m + 1;            } else if (nums[l] > nums[m]) {                if (target >= nums[l] || target <= nums[m])                    r = m - 1;                else                    l = m + 1;            } else                l++;        }        return false;    }

# Search Insert Position

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 int searchInsert(int[] nums, int target) {        if (nums == null || nums.length == 0) {            return 0;        }        for (int i = 0; i < nums.length; i++) {            if (target <= nums[i]) {                return i;            }        }        return nums.length;    }

# Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Did you use extra space?
A straight forward solution using O(_m__n_) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

    public void setZeroes(int[][] matrix) {        if (matrix == null || matrix.length == 0) {            return;        }        int mx = matrix.length;        int my = matrix[0].length;        // 两个变量，判断第一行和第一列是否有0        boolean xflag = false, yflag = false;        // 判断第一行是否有0        for (int i = 0; i < mx; i++) {            if (matrix[i][0] == 0) {                xflag = true;                break;            }        }        // 判断第一列是否有0        for (int i = 0; i < my; i++) {            if (matrix[0][i] == 0) {                yflag = true;                break;            }        }        // 其它行、列是否有0        for (int i = 1; i < mx; i++) {            for (int j = 1; j < my; j++) {                if (matrix[i][j] == 0) {                    matrix[i][0] = 0;                    matrix[0][j] = 0;                }            }        }        // 对于第一列，为0，则将所在行变成0        for (int i = 1; i < mx; i++) {            if (matrix[i][0] == 0) {                for (int j = 0; j < my; j++) {                    matrix[i][j] = 0;                }            }        }        // 对于第一行，为0，则将所在列变成0        for (int i = 0; i < my; i++) {            if (matrix[0][i] == 0) {                for (int j = 0; j < mx; j++) {                    matrix[j][i] = 0;                }            }        }        // 若原来第一行中有0，则将整行置0        if (xflag) {            for (int i = 0; i < mx; i++) {                matrix[i][0] = 0;            }        }        // 若原来第一列中有0，则将整列置0        if (yflag) {            for (int i = 0; i < my; i++) {                matrix[0][i] = 0;            }        }    }

# Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

    public void sortColors(int[] nums) {        if (nums == null || nums.length == 0) {            return;        }        // 定义三个变量，存储三种颜色出现次数        int red = 0;        int white = 0;        int blue = 0;        // 循环一次，记录每种颜色出现次数        for (int i = 0; i < nums.length; i++) {            if (nums[i] == 0) {                red++;            } else if (nums[i] == 1) {                white++;            } else {                blue++;            }        }        // 对nums数组重新赋值        int i = 0;        while (red-- > 0) {            nums[i++] = 0;        }        while (white-- > 0) {            nums[i++] = 1;        }        while (blue-- > 0) {            nums[i++] = 2;        }    }

# Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]


You should return [1,2,3,6,9,8,7,4,5].

    public List<Integer> spiralOrder(int[][] matrix) {        List<Integer> rt = new ArrayList<Integer>();        if (matrix == null || matrix.length == 0) {            return rt;        }        int startx = 0, endx = matrix.length - 1;        int starty = 0, endy = matrix[0].length - 1;        while (startx <= endx && starty <= endy) {            // 上边的行，从左向右            for (int y = starty; y <= endy; y++) {                rt.add(matrix[startx][y]);            }            // 右边的列，从上到下            for (int x = startx + 1; x <= endx; x++) {                rt.add(matrix[x][endy]);            }            // 如果行或列遍历完，则退出循环            if (startx == endx || starty == endy) {                break;            }            // 下边的行，从右向左            for (int y = endy - 1; y >= starty; y--) {                rt.add(matrix[endx][y]);            }            // 左边的列，从下到上            for (int x = endx - 1; x >= startx + 1; x--) {                rt.add(matrix[x][starty]);            }            startx++;            starty++;            endx--;            endy--;        }        return rt;    }

# Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]


    public int[][] generateMatrix(int n) {        if (n <= 0) {            return new int[0][0];        }        int[][] matrix = new int[n][n];        int num = 1;        int startx = 0, endx = n - 1;        int starty = 0, endy = n - 1;        while (startx <= endx && starty <= endy) {            // 上边的行，从左向右            for (int y = starty; y <= endy; y++) {                matrix[startx][y] = num++;            }            // 右边的列，从上到下            for (int x = startx + 1; x <= endx; x++) {                matrix[x][endy] = num++;            }            // 如果行或列遍历完，则退出循环            if (startx == endx || starty == endy) {                break;            }            // 下边的行，从右向左            for (int y = endy - 1; y >= starty; y--) {                matrix[endx][y] = num++;            }            // 左边的列，从下到上            for (int x = endx - 1; x >= startx + 1; x--) {                matrix[x][starty] = num++;            }            startx++;            starty++;            endx--;            endy--;        }        return matrix;    }

# Subsets

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

Note:

• Elements in a subset must be in non-descending order.
• 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],
[]
]


    int target;// 次数    Integer[] stack;// 存储每次排列    List<List<Integer>> rt;// 存储结果    public void search(int p, int[] nums) {        // 若长度为k，则stack是其中一个结果，保存结果        if (p == target) {            rt.add(new ArrayList<Integer>(Arrays.asList(stack)));            return;        }        for (int i = 0; i < nums.length; i++) {            if (p > 0 && nums[i] <= stack[p - 1]) {                continue;            }            stack[p] = nums[i];            search(p + 1, nums);        }    }    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums);        rt = new ArrayList<List<Integer>>();        // 分别做0~num.length长度的组合        for (int i = 0; i <= nums.length; i++) {            target = i;            stack = new Integer[i];            search(0, nums);        }        return rt;    }

# Subsets II

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

Note:

• Elements in a subset must be in non-descending order.
• 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 List<List<Integer>> subsetsWithDup(int[] nums) {        if (nums == null) {            return null;        }        if (nums.length == 0) {            return new ArrayList<List<Integer>>();        }        Set<List<Integer>> set = new HashSet<List<Integer>>();        // 题目中要求每个list是非降序，所以要先从小到大排序        Arrays.sort(nums);        // 对于n位，有2^n种情况        for (int i = 0; i < Math.pow(2, nums.length); i++) {            List<Integer> list = new ArrayList<Integer>();            int tmp = i;            // 对于每种情况，分别求得二进制中1的个数            // 0代表不选择，1代表选择            for (int j = 0; j < nums.length; j++) {                int bit = tmp & 1;                tmp >>= 1;                if (bit == 1) {                    list.add(nums[j]);                }            }            set.add(list);        }        return new ArrayList<List<Integer>>(set);    }

# Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    public List<String> summaryRanges(int[] nums) {        List<String> rt = new ArrayList<String>();        if (nums == null || nums.length == 0) {            return rt;        }        for (int i = 0; i < nums.length; i++) {            int st = nums[i];            int ed = st;            while (i + 1 < nums.length && nums[i + 1] - ed == 1) {                i++;                ed++;            }            if (ed == st) {                rt.add(st + "");            } else {                rt.add(st + "->" + ed);            }        }        return rt;    }

# Unique Paths

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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

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

# Unique Paths II

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.

Note: m and n will be at most 100.

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {        if (obstacleGrid == null || obstacleGrid[0] == null) {            return 0;        }        if (obstacleGrid[0][0] == 1) {            return 0;        }        int m = obstacleGrid.length;        int n = obstacleGrid[0].length;        int[][] dp = new int[m][n];        for (int y = 1; y < n; y++) {            if (obstacleGrid[0][y] == 0) {                dp[0][y] = 1;            } else {                break;            }        }        for (int x = 1; x < m; x++) {            if (obstacleGrid[x][0] == 0) {                dp[x][0] = 1;            } else {                break;            }        }        for (int y = 1; y < n; y++) {            for (int x = 1; x < m; x++) {                if (obstacleGrid[x][y] == 1) {                    dp[x][y] = 0;                } else {                    dp[x][y] = dp[x - 1][y] + dp[x][y - 1];                }            }        }        return dp[m - 1][n - 1];    }

• 私有
• 公开
• 删除