[关闭]
@Yano 2015-12-30T11:20:27.000000Z 字数 39021 阅读 36736

LeetCode之Array题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

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

参考：LeetCode 001 Two Sum

  1.     public int[] twoSum(int[] nums, int target) {
  3.         if (nums == null || nums.length <= 1) {
  4.             return new int[2];
  5.         }
  7.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  9.         // key = target - nums[i], just one solution
  10.         for (int i = 0; i < nums.length; i++) {
  11.             map.put(target - nums[i], i);
  12.         }
  14.         for (int i = 0; i < nums.length; i++) {
  15.             Integer v = map.get(nums[i]);
  17.             // can't use itself
  18.             if (v != null && v != i) {
  19.                 return new int[] { i + 1, v + 1 };
  20.             }
  21.         }
  23.         return null;
  24.     }

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:

参考：LeetCode 015 3Sum

分析：

  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]，则求出的解肯定重复了。
  1.     public List<List<Integer>> threeSum(int[] nums) {
  3.         if (nums == null || nums.length < 3) {
  4.             return new ArrayList<List<Integer>>();
  5.         }
  7.         Set<List<Integer>> set = new HashSet<List<Integer>>();
  9.         Arrays.sort(nums);
  11.         for (int start = 0; start < nums.length; start++) {
  13.             if (start != 0 && nums[start - 1] == nums[start]) {
  14.                 continue;
  15.             }
  17.             int mid = start + 1, end = nums.length - 1;
  19.             while (mid < end) {
  21.                 int sum = nums[start] + nums[mid] + nums[end];
  23.                 if (sum == 0) {
  25.                     List<Integer> tmp = new ArrayList<Integer>();
  26.                     tmp.add(nums[start]);
  27.                     tmp.add(nums[mid]);
  28.                     tmp.add(nums[end]);
  29.                     set.add(tmp);
  31.                     while (++mid < end && nums[mid - 1] == nums[mid])
  32.                         ;
  33.                     while (--end > mid && nums[end + 1] == nums[end])
  34.                         ;
  35.                 }
  37.                 else if (sum < 0) {
  38.                     mid++;
  39.                 }
  41.                 else {
  42.                     end--;
  43.                 }
  44.             }
  45.         }
  47.         return new ArrayList<List<Integer>>(set);
  48.     }

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

参考：LeetCode 016 3Sum Closest

  1.     public int threeSumClosest(int[] nums, int target) {
  3.         if (nums == null || nums.length < 3) {
  4.             return Integer.MIN_VALUE;
  5.         }
  7.         Arrays.sort(nums);
  9.         int minGap = Integer.MAX_VALUE;
  10.         int result = 0;
  12.         for (int start = 0; start < nums.length; start++) {
  14.             int mid = start + 1, end = nums.length - 1;
  16.             while (mid < end) {
  18.                 int sum = nums[start] + nums[mid] + nums[end];
  19.                 int gap = Math.abs(sum - target);
  21.                 if (gap < minGap) {
  22.                     minGap = gap;
  23.                     result = sum;
  24.                 }
  26.                 if (sum < target) {
  27.                     mid++;
  28.                 } else {
  29.                     end--;
  30.                 }
  31.             }
  32.         }
  34.         return result;
  35.     }

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:

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)

参考：LeetCode 018 4Sum

  1.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         if (nums == null || nums.length < 4) {
  4.             return new ArrayList<List<Integer>>();
  5.         }
  7.         Arrays.sort(nums);
  9.         Set<List<Integer>> set = new HashSet<List<Integer>>();
  11.         // 和3Sum一样，只是多了一个循环
  12.         for (int a = 0; a < nums.length - 3; a++) {
  14.             int target_3Sum = target - nums[a];
  16.             for (int b = a + 1; b < nums.length - 2; b++) {
  18.                 int c = b + 1, d = nums.length - 1;
  20.                 while (c < d) {
  22.                     int sum = nums[b] + nums[c] + nums[d];
  24.                     if (sum == target_3Sum) {
  26.                         // 将结果加入集合
  27.                         List<Integer> tmp = new ArrayList<Integer>();
  28.                         tmp.add(nums[a]);
  29.                         tmp.add(nums[b]);
  30.                         tmp.add(nums[c]);
  31.                         tmp.add(nums[d]);
  32.                         set.add(tmp);
  34.                         // 去重
  35.                         while (++c < d && nums[c - 1] == nums[c])
  36.                             ;
  37.                         while (--d > c && nums[d + 1] == nums[d])
  38.                             ;
  39.                     }
  41.                     else if (sum < target_3Sum) {
  42.                         c++;
  43.                     } else {
  44.                         d--;
  45.                     }
  46.                 }
  47.             }
  48.         }
  50.         return new ArrayList<List<Integer>>(set);
  51.     }

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.

参考：LeetCode 121 Best Time to Buy and Sell Stock

prices 7 2 3 6 1 9
lowest 7 2 2 2 1 1
maxProfit 0 0 1 4 4 8 
  1.     public int maxProfit(int[] prices) {
  3.         if (prices.length <= 1) {
  4.             return 0;
  5.         }
  7.         int maxProfit = 0;
  8.         int lowest = Integer.MAX_VALUE;
  10.         for (int v : prices) {
  11.             lowest = Math.min(v, lowest);
  12.             maxProfit = Math.max(maxProfit, v - lowest);
  13.         }
  15.         return maxProfit;
  16.     }

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

参考：LeetCode 122 Best Time to Buy and Sell Stock II

只要有利润就卖，就是最优解。

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

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:

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

参考：LeetCode 039 Combination Sum

使用递归，注意保存结果时，应该新建一个ArrayList：result.add(new ArrayList< Integer>(cur))。否则result会指向一直变化的cur。

  1.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  3.         if (candidates == null || candidates.length == 0) {
  4.             return new ArrayList<List<Integer>>();
  5.         }
  7.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  8.         ArrayList<Integer> cur = new ArrayList<Integer>();
  10.         Arrays.sort(candidates);
  11.         dfs(0, target, result, cur, candidates);
  13.         return result;
  14.     }
  16.     private void dfs(int start, int target, List<List<Integer>> result,
  17.             ArrayList<Integer> cur, int[] candidates) {
  19.         if (target == 0) {
  20.             result.add(new ArrayList<Integer>(cur));
  21.             return;
  22.         }
  24.         for (int i = start; i < candidates.length; i++) {
  26.             // candidates[i] > target，则递归结束，后面不可能是解
  27.             if (candidates[i] > target) {
  28.                 return;
  29.             }
  31.             cur.add(candidates[i]);
  32.             dfs(i, target - candidates[i], result, cur, candidates);
  33.             cur.remove(cur.size() - 1);
  34.         }
  35.     }

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:

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]

参考：LeetCode 040 Combination Sum II

  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。
  2.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  4.         if (candidates == null || candidates.length == 0) {
  5.             return new ArrayList<List<Integer>>();
  6.         }
  8.         Set<List<Integer>> rt = new HashSet<List<Integer>>();
  9.         ArrayList<Integer> cur = new ArrayList<Integer>();
  11.         Arrays.sort(candidates);
  12.         dfs(0, target, rt, cur, candidates);
  14.         return new ArrayList<List<Integer>>(rt);
  15.     }
  17.     private void dfs(int start, int target, Set<List<Integer>> rt,
  18.             ArrayList<Integer> cur, int[] candidates) {
  20.         if (target == 0) {
  21.             rt.add(new ArrayList<Integer>(cur));
  22.             return;
  23.         }
  25.         for (int i = start; i < candidates.length; i++) {
  27.             // candidates[i] > target，则递归结束，后面不可能是解
  28.             if (candidates[i] > target) {
  29.                 return;
  30.             }
  32.             cur.add(candidates[i]);
  33.             dfs(i + 1, target - candidates[i], rt, cur, candidates);
  34.             cur.remove(cur.size() - 1);
  35.         }
  36.     }

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.

参考：LeetCode 216 Combination Sum III

这次是指定了元素的个数，用一个变量记录即可。

  1.     public List<List<Integer>> combinationSum3(int k, int n) {
  3.         List<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         if (k < 1 || n < 1) {
  6.             return rt;
  7.         }
  9.         List<Integer> cur = new ArrayList<Integer>();
  10.         dfs(rt, cur, 0, k, n, 1);
  11.         return rt;
  12.     }
  14.     private void dfs(List<List<Integer>> rt, List<Integer> cur, int sum, int k,
  15.             int n, int level) {
  17.         if (sum == n && k == 0) {
  18.             rt.add(new ArrayList<Integer>(cur));
  19.             return;
  20.         } else if (sum > n || k <= 0) {
  21.             return;
  22.         }
  24.         for (int i = level; i <= 9; i++) {
  25.             cur.add(i);
  26.             dfs(rt, cur, sum + i, k - 1, n, i + 1);
  27.             cur.remove(cur.size() - 1);
  28.         }
  29.     }

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.

参考：LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

题目要求：根据前序遍历和中序遍历序列，构建二叉树。

前序遍历p[0]是二叉树的根结点，1是i[2]，则：

  1.     int p = 0;
  2.     int[] preorder;
  3.     int[] inorder;
  5.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  7.         this.preorder = preorder;
  8.         this.inorder = inorder;
  10.         return buildTree(0, preorder.length);
  11.     }
  13.     TreeNode buildTree(int start, int end) {
  15.         if (start >= end) {
  16.             return null;
  17.         }
  19.         TreeNode root = new TreeNode(preorder[p]);
  21.         int i;
  22.         for (i = start; i < end && preorder[p] != inorder[i]; i++)
  23.             ;
  25.         p++;
  26.         root.left = buildTree(start, i);
  27.         root.right = buildTree(i + 1, end);
  29.         return root;
  30.     }

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.

参考：LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal

  1.     int p;
  2.     int[] postorder;
  3.     int[] inorder;
  5.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  7.         this.p = postorder.length - 1;
  8.         this.inorder = inorder;
  9.         this.postorder = postorder;
  11.         return buildTree(0, postorder.length);
  12.     }
  14.     TreeNode buildTree(int start, int end) {
  16.         if (start >= end) {
  17.             return null;
  18.         }
  20.         TreeNode root = new TreeNode(postorder[p]);
  22.         int i;
  23.         for (i = start; i < end && postorder[p] != inorder[i]; i++)
  24.             ;
  26.         p--;
  27.         root.right = buildTree(i + 1, end);
  28.         root.left = buildTree(start, i);
  30.         return root;
  31.     }

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.

参考：LeetCode 217 Contains Duplicate

  1.     public boolean containsDuplicate(int[] nums) {
  3.         Set<Integer> s = new HashSet<Integer>();
  5.         for (int n : nums) {
  6.             if (s.contains(n)) {
  7.                 return true;
  8.             }
  9.             s.add(n);
  10.         }
  12.         return false;
  13.     }

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.

参考：LeetCode 219 Contains Duplicate II

建立一个map，key是出现过的元素，value是该元素的下标。若相同元素距离大于k，则更新下标。

  1.     public boolean containsNearbyDuplicate(int[] nums, int k) {
  3.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (map.containsKey(nums[i])) {
  7.                 if (i - map.get(nums[i]) <= k) {
  8.                     return true;
  9.                 }
  10.             }
  11.             map.put(nums[i], i);
  12.         }
  14.         return false;
  15.     }

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.

参考：LeetCode 220 Contains Duplicate III

对于加入的元素，要能够在O(1)时间内查找，同时还要自动排序，维持一个k个元素的TreeSet。

  1.     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  3.         if (k < 1 || t < 0 || nums == null || nums.length < 2) {
  4.             return false;
  5.         }
  7.         SortedSet<Long> set = new TreeSet<Long>();
  9.         for (int j = 0; j < nums.length; j++) {
  11.             SortedSet<Long> subSet = set.subSet((long) nums[j] - t,
  12.                     (long) nums[j] + t + 1);
  14.             // 集合不为空，则表示找到解
  15.             if (!subSet.isEmpty()) {
  16.                 return true;
  17.             }
  19.             if (j >= k) {
  20.                 set.remove((long) nums[j - k]);
  21.             }
  23.             set.add((long) nums[j]);
  24.         }
  26.         return false;
  27.     }

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.

参考：LeetCode 153 Find Minimum in Rotated Sorted Array

数列基本有序，则使用二分查找。假设数列是n，s是起始下标，e是最后下标，m是中间元素下标。分为三种情况：

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

情况1：n[s] < n[e]

0 1 2 4 5 6 7

这种情况，直接返回n[s]。因为数列是有序的，或者只是旋转过一次。如果n[s] < n[e]，则表明没有旋转。最小元素是n[s]。

情况2：n[m] > n[s] > n[e]

4 5 6 7 0 1 2

只需要满足n[m] > n[s]即可，因为第一种情况排除后，n[s]就一定会 > n[e]。

在本例中：

  1. n[s] = 4
  2. n[m] = 7
  3. n[e] = 2

则最小值肯定在7之后，到2之间，即 [m+1, e]。

情况3：n[m] < n[e] < n[s]

6 7 0 1 2 4 5

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

  1. n[s] = 6
  2. n[m] = 1
  3. n[e] = 5

则表明，从m到e，数组已经是上升的，所以最小值在[s, m]。

  1.     public int findMin(int[] nums) {
  3.         if (nums.length == 1) {
  4.             return nums[0];
  5.         }
  7.         if (nums.length == 2) {
  8.             return Math.min(nums[0], nums[1]);
  9.         }
  11.         int s = 0, e = nums.length - 1;
  13.         int m = (s + e) / 2;
  15.         if (nums[s] < nums[e]) {
  16.             return nums[s];
  17.         }
  19.         if (nums[m] > nums[s]) {
  20.             return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));
  21.         }
  23.         return findMin(Arrays.copyOfRange(nums, s, m + 1));
  25.     }

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.

参考：LeetCode 162 Find Peak Element

  1.     public int findPeakElement(int[] nums) {
  3.         int low = 0;
  4.         int high = nums.length - 1;
  6.         while (low < high) {
  7.             int mid = low + (high - low) / 2;
  8.             if (nums[mid] > nums[mid + 1]) {
  9.                 high = mid;
  10.             } else {
  11.                 low = mid + 1;
  12.             }
  13.         }
  15.         return low;
  16.     }

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.

Follow up:

  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.

参考：LeetCode 289 Game of Life

题目中说最好是in-place，因为board是int型的，所以要区分四种状态（dead是0，live是1）：

  1. dead->live    01
  2. dead->dead    00
  3. live->dead    10
  4. live->live    11

或者直接用0,1,2,3四个数字表示四种状态都可以，然后通过移位进行结果的更新。

下面的图片，是一个Game of Life变化图。

这里写图片描述

  1.     public void gameOfLife(int[][] board) {
  3.         if (board == null || board.length == 0 || board[0] == null
  4.                 || board[0].length == 0)
  5.             return;
  7.         int m = board.length;
  8.         int n = board[0].length;
  10.         // 判断每个点，下一时刻的状态
  11.         for (int i = 0; i < m; i++) {
  12.             for (int j = 0; j < n; j++) {
  13.                 int x = getLiveNum(board, i, j);
  14.                 if (board[i][j] == 0) {
  15.                     if (x == 3)
  16.                         board[i][j] += 10;
  17.                 } else {
  18.                     if (x == 2 || x == 3)
  19.                         board[i][j] += 10;
  20.                 }
  21.             }
  22.         }
  24.         // 更新每个点的状态
  25.         for (int i = 0; i < m; i++) {
  26.             for (int j = 0; j < n; j++) {
  27.                 board[i][j] /= 10;
  28.             }
  29.         }
  30.     }
  32.     // 获取board[x][y]邻居live的数量
  33.     private int getLiveNum(int[][] board, int x, int y) {
  34.         int c = 0;
  35.         for (int i = x - 1; i <= x + 1; i++) {
  36.             for (int j = y - 1; j <= y + 1; j++) {
  37.                 if (i < 0 || j < 0 || i > board.length - 1
  38.                         || j > board[0].length - 1 || (i == x && j == y))
  39.                     continue;
  40.                 if (board[i][j] % 10 == 1)
  41.                     c++;
  42.             }
  43.         }
  44.         return c;
  45.     }

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.

参考：LeetCode 055 Jump Game

设变量maxStep为当前能够跳跃的最大步数，超过数组长度，就表示能够跳出；否则不能跳出。

那么maxStep怎么求得呢？nums[i] + i 就代表：从当前位置起跳，所能跳跃的最远位置。

  1.     public boolean canJump(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return false;
  5.         }
  7.         int maxStep = 0;
  9.         for (int i = 0; i < nums.length; i++) {
  11.             if (maxStep >= nums.length - 1) {
  12.                 return true;
  13.             }
  15.             if (nums[i] == 0 && maxStep == i) {
  16.                 return false;
  17.             }
  19.             maxStep = Math.max(maxStep, nums[i] + i);
  20.         }
  22.         return true;
  23.     }

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.

参考：LeetCode 169 Majority Element

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

  1.     public int majorityElement(int[] nums) {
  3.         int m = nums[0];
  4.         int c = 1;
  6.         for (int i = 1; i < nums.length; i++) {
  7.             if (m == nums[i]) {
  8.                 c++;
  9.             } else if (c > 1) {
  10.                 c--;
  11.             } else {
  12.                 m = nums[i];
  13.             }
  14.         }
  16.         return m;
  17.     }

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!

参考：LeetCode 229 Majority Element II

因为题目中说是大于⌊ n/3 ⌋次数的元素，这样的元素最多只能有2个。

  1.     public List<Integer> majorityElement(int[] nums) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  5.         if (nums == null || nums.length == 0) {
  6.             return rt;
  7.         }
  9.         int m1 = nums[0];
  10.         int m2 = 0;
  12.         int c1 = 1;
  13.         int c2 = 0;
  15.         for (int i = 1; i < nums.length; i++) {
  16.             int x = nums[i];
  17.             if (x == m1) {
  18.                 c1++;
  19.             } else if (x == m2) {
  20.                 c2++;
  21.             } else if (c1 == 0) {
  22.                 m1 = x;
  23.                 c1 = 1;
  24.             } else if (c2 == 0) {
  25.                 m2 = x;
  26.                 c2 = 1;
  27.             } else {
  28.                 c1--;
  29.                 c2--;
  30.             }
  31.         }
  33.         c1 = 0;
  34.         c2 = 0;
  36.         for (int i = 0; i < nums.length; i++) {
  37.             if (m1 == nums[i]) {
  38.                 c1++;
  39.             } else if (m2 == nums[i]) {
  40.                 c2++;
  41.             }
  42.         }
  44.         if (c1 > nums.length / 3) {
  45.             rt.add(m1);
  46.         }
  48.         if (c2 > nums.length / 3) {
  49.             rt.add(m2);
  50.         }
  52.         return rt;
  53.     }

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.

参考：LeetCode 053 Maximum Subarray

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

假设数组是[−2,1,−3,4,−1,2,1,−5,4]，首先curSum = -2, maxSum = -2。

  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. 以此类推。

本题只是返回连续最大和，并没有返回数组，所以没有必要记录下标。curSum和maxSum 的计算公式如下：

  1.     public int maxSubArray(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  7.         int curSum = nums[0];
  8.         int maxSum = nums[0];
  10.         for (int i = 1; i < nums.length; i++) {
  11.             curSum = Math.max(curSum + nums[i], nums[i]);
  12.             maxSum = Math.max(curSum, maxSum);
  13.         }
  15.         return maxSum;
  16.     }

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 152 Maximum Product Subarray

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

在解法上是一样的，只是在求和时，是负就舍弃。但是在乘积中，因为负数*负数=正数，所以连续乘积为负数时，并不能舍弃这个数，因为如果数组的元素是负数，它可能成为乘积最大的数。

所以LeetCode第53题Maximum Subarray，只需要定义一个变量，用来记录和；本题要定义两个变量：positive和negative，分别记录当前乘积最大值和最小值。

  1.     public int maxProduct(int[] nums) {
  3.         int max = nums[0];
  4.         int positive = nums[0];
  5.         int negative = nums[0];
  7.         for (int i = 1; i < nums.length; i++) {
  9.             positive *= nums[i];
  10.             negative *= nums[i];
  12.             if (positive < negative) {
  13.                 int t = positive;
  14.                 positive = negative;
  15.                 negative = t;
  16.             }
  18.             positive = Math.max(positive, nums[i]);
  19.             negative = Math.min(negative, nums[i]);
  21.             max = Math.max(max, positive);
  22.         }
  24.         return max;
  25.     }

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.

参考：LeetCode 088 Merge Sorted Array

  1.     public int help(int[] nums, int k) {
  3.         if (k < 0) {
  4.             return Integer.MIN_VALUE;
  5.         }
  7.         return nums[k];
  8.     }
  10.     public void merge(int[] nums1, int m, int[] nums2, int n) {
  12.         if (nums1 == null || nums2 == null) {
  13.             return;
  14.         }
  16.         int t = m + n - 1;
  18.         while (t >= 0) {
  20.             int n1 = help(nums1, m - 1);
  21.             int n2 = help(nums2, n - 1);
  23.             if (n1 > n2) {
  24.                 nums1[t] = n1;
  25.                 m--;
  26.             } else {
  27.                 nums1[t] = n2;
  28.                 n--;
  29.             }
  31.             t--;
  32.         }
  33.     }

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.

参考：LeetCode 064 Minimum Path Sum

建立一个背包dp[m][n]，其中dp[i][j]表示从grid[0][0]到grid[i][j]的最小和。

  1.     public int minPathSum(int[][] grid) {
  3.         if (grid == null || grid[0] == null) {
  4.             return 0;
  5.         }
  7.         int m = grid.length;
  8.         int n = grid[0].length;
  10.         int[][] dp = new int[m][n];
  11.         dp[0][0] = grid[0][0];
  13.         for (int y = 1; y < n; y++) {
  14.             dp[0][y] = dp[0][y - 1] + grid[0][y];
  15.         }
  17.         for (int x = 1; x < m; x++) {
  18.             dp[x][0] = dp[x - 1][0] + grid[x][0];
  19.         }
  21.         for (int y = 1; y < n; y++) {
  22.             for (int x = 1; x < m; x++) {
  23.                 int min = Math.min(dp[x - 1][y], dp[x][y - 1]);
  24.                 dp[x][y] = min + grid[x][y];
  25.             }
  26.         }
  28.         return dp[m - 1][n - 1];
  29.     }

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.

参考：LeetCode 209 Minimum Size Subarray Sum

定义两个指针，st和ed。如果sum>=s，sum从前面元素开始减；如果sum< s，ed++。

  1.     public int minSubArrayLen(int s, int[] nums) {
  3.         int sum = 0;
  4.         int st = 0;
  5.         int min = Integer.MAX_VALUE;
  7.         for (int i = 0; i < nums.length; i++) {
  9.             sum += nums[i];
  11.             if (sum >= s) {
  12.                 while (sum - nums[st] >= s) {
  13.                     sum -= nums[st++];
  14.                 }
  15.                 min = Math.min(min, i - st + 1);
  16.             }
  17.         }
  19.         if (min > nums.length) {
  20.             return 0;
  21.         }
  23.         return min;
  24.     }

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.

参考：LeetCode 268 Missing Number

既然是0~n只差其中一个数，不如再次加入0~n的序列，这样就和LeetCode 136 Single Number一样了，missing number只出现一次，其余都是出现两次。

  1.     public int missingNumber(int[] nums) {
  3.         int rt = nums.length;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             rt = rt ^ nums[i] ^ i;
  7.         }
  9.         return rt;
  10.     }

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.

参考：LeetCode 283 Move Zeroes

  1.     public void moveZeroes(int[] nums) {
  3.         int t = 0;
  5.         // 把非0元素移到前面
  6.         for (int i = 0; i < nums.length; i++) {
  7.             if (nums[i] != 0) {
  8.                 nums[t++] = nums[i];
  9.             }
  10.         }
  12.         // 把后面元素值0
  13.         for (int i = t; i < nums.length; i++) {
  14.             nums[i] = 0;
  15.         }
  16.     }

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,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

参考：LeetCode 031 Next Permutation

  1.     public void nextPermutation(int[] nums) {
  3.         if (nums == null || nums.length < 2) {
  4.             return;
  5.         }
  7.         int p = 0;
  8.         for (int i = nums.length - 2; i >= 0; i--) {
  9.             if (nums[i] < nums[i + 1]) {
  10.                 p = i;
  11.                 break;
  12.             }
  13.         }
  15.         int q = 0;
  16.         for (int i = nums.length - 1; i > p; i--) {
  17.             if (nums[i] > nums[p]) {
  18.                 q = i;
  19.                 break;
  20.             }
  21.         }
  23.         if (p == 0 && q == 0) {
  24.             reverse(nums, 0, nums.length - 1);
  25.             return;
  26.         }
  28.         int temp = nums[p];
  29.         nums[p] = nums[q];
  30.         nums[q] = temp;
  32.         if (p < nums.length - 1) {
  33.             reverse(nums, p + 1, nums.length - 1);
  34.         }
  36.     }
  38.     private void reverse(int[] nums, int left, int right) {
  40.         while (left < right) {
  41.             int temp = nums[left];
  42.             nums[left] = nums[right];
  43.             nums[right] = temp;
  44.             left++;
  45.             right--;
  46.         }
  47.     }

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]
]

参考：LeetCode 118 Pascal's Triangle

  1.     public List<List<Integer>> generate(int numRows) {
  3.         ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         Integer[] pre = null;
  7.         for (int i = 1; i <= numRows; i++) {
  9.             //must be defined as Integer[]
  10.             Integer[] row = new Integer[i];
  12.             row[0] = 1;
  13.             row[i - 1] = 1;
  15.             for (int j = 1; j < i - 1; j++) {
  16.                 row[j] = pre[j] + pre[j - 1];
  17.             }
  19.             rt.add(new ArrayList<Integer>(Arrays.asList(row)));
  20.             pre = row;
  21.         }
  23.         return rt;
  24.     }

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?

参考：LeetCode 119 Pascal's Triangle II

  1.     public List<Integer> getRow(int rowIndex) {
  3.         Integer[] row = new Integer[rowIndex + 1];
  4.         Arrays.fill(row, 1);
  6.         for (int i = 0; i < rowIndex - 1; i++) {
  7.             for (int j = i + 1; j >= 1; j--) {
  8.                 row[j] = row[j] + row[j - 1];
  9.             }
  10.         }
  12.         return Arrays.asList(row);
  13.     }

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.

参考：LeetCode 066 Plus One

  1.     public int[] plusOne(int[] digits) {
  3.         if (digits == null || digits.length == 0) {
  4.             return null;
  5.         }
  7.         int[] rt = new int[digits.length + 1];
  8.         digits[digits.length - 1]++;
  10.         for (int i = digits.length - 1; i >= 0; i--) {
  11.             rt[i + 1] += digits[i];
  12.             rt[i] += rt[i + 1] / 10;
  13.             rt[i + 1] %= 10;
  14.         }
  16.         if (rt[0] == 0) {
  17.             return Arrays.copyOfRange(rt, 1, rt.length);
  18.         } else {
  19.             return rt;
  20.         }
  21.     }

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

Follow up:
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.)

参考：LeetCode 238 Product of Array Except Self

可以定义两个辅助数组，left和right。

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

但是分析一下，空间可以优化，因为我们先从右向左算，再从左向右算，只需要返回的那一个数组就够了。

  1.     public int[] productExceptSelf(int[] nums) {
  3.         int[] rt = new int[nums.length];
  4.         rt[nums.length - 1] = 1;
  6.         for (int i = nums.length - 2; i >= 0; i--) {
  7.             rt[i] = rt[i + 1] * nums[i+1];
  8.         }
  10.         int left = 1;
  11.         for (int i = 0; i < nums.length; i++) {
  12.             rt[i] *= left;
  13.             left *= nums[i];
  14.         }
  16.         return rt;
  17.     }

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.

参考：LeetCode 026 Remove Duplicates from Sorted Array

  1.     public int removeDuplicates(int[] nums) {
  3.         if (nums == null) {
  4.             return -1;
  5.         }
  7.         if (nums.length < 2) {
  8.             return nums.length;
  9.         }
  11.         int len = 0;
  13.         for (int i = 1; i < nums.length; i++) {
  14.             if (nums[len] != nums[i]) {
  15.                 nums[++len] = nums[i];
  16.             }
  17.         }
  19.         return len + 1;
  20.     }

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
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.

参考：LeetCode 080 Remove Duplicates from Sorted Array II

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

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.

参考：LeetCode 027 Remove Element

  1.     public int removeElement(int[] nums, int val) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  7.         int len = 0;
  9.         for (int i = 0; i < nums.length; i++) {
  10.             if (nums[i] != val) {
  11.                 nums[len++] = nums[i];
  12.             }
  13.         }
  15.         return len;
  16.     }

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.

参考：LeetCode 189 Rotate Array

  1.     void reverse(int[] nums, int st, int ed) {
  3.         while (st < ed) {
  4.             int t = nums[st];
  5.             nums[st] = nums[ed];
  6.             nums[ed] = t;
  7.             st++;
  8.             ed--;
  9.         }
  10.     }
  12.     public void rotate(int[] nums, int k) {
  14.         int length = nums.length;
  16.         k = k % length;
  18.         if (length == 1 || k == 0)
  19.             return;
  21.         reverse(nums, 0, length - k - 1);
  22.         reverse(nums, length - k, length - 1);
  23.         reverse(nums, 0, length - 1);
  24.     }

Rotate Image

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

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

参考：LeetCode 048 Rotate Image

这里写图片描述

  1.     public void rotate(int[][] matrix) {
  3.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  4.             return;
  5.         }
  7.         final int mx = matrix.length;
  8.         final int my = matrix[0].length;
  9.         int x, y;
  11.         int t;
  13.         int _my = my - 1;
  14.         for (x = 0; x < mx - 1; x++) {
  15.             for (y = 0; y < _my; y++) {
  16.                 int ny = mx - 1 - x;
  17.                 int nx = my - 1 - y;
  19.                 t = matrix[y][x];
  20.                 matrix[y][x] = matrix[ny][nx];
  21.                 matrix[ny][nx] = t;
  23.             }
  24.             _my--;
  25.         }
  27.         for (x = 0; x < mx; x++) {
  28.             for (y = 0; y < my / 2; y++) {
  29.                 int ny = my - 1 - y;
  30.                 int nx = x;
  32.                 t = matrix[y][x];
  33.                 matrix[y][x] = matrix[ny][nx];
  34.                 matrix[ny][nx] = t;
  35.             }
  36.         }
  38.     }

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:

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

参考：LeetCode 074 Search a 2D Matrix

  1.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         int mx = matrix.length;
  4.         int my = matrix[0].length;
  6.         int l = 0;
  7.         int r = mx * my;
  9.         while (l < r) {
  11.             int m = l + (r - l) / 2;
  13.             // 将m转换成x、y
  14.             int x = m / my;
  15.             int y = m % my;
  17.             // 二分查找：matrix[x][y]转换成一维数组，坐标就是m
  18.             if (matrix[x][y] == target) {
  19.                 return true;
  20.             } else if (matrix[x][y] < target) {
  21.                 l = m + 1;
  22.             } else {
  23.                 r = m;
  24.             }
  25.         }
  27.         return false;
  28.     }

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

参考：LeetCode 034 Search for a Range

  1.     public int[] searchRange(int[] nums, int target) {
  3.         int l = 0, r = nums.length;
  5.         while (l < r) {
  7.             int m = l + (r - l) / 2;
  9.             if (nums[m] == target) {
  11.                 int s = m, e = m;
  13.                 while (s - 1 >= 0 && nums[s - 1] == target) {
  14.                     s--;
  15.                 }
  17.                 while (e + 1 < nums.length && nums[e + 1] == target) {
  18.                     e++;
  19.                 }
  21.                 return new int[] { s, e };
  23.             } else if (nums[m] > target) {
  24.                 r = m;
  25.             } else {
  26.                 l = m + 1;
  27.             }
  28.         }
  30.         return new int[] { -1, -1 };
  31.     }

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.

参考：LeetCode 033 Search in Rotated Sorted Array

  1.     public int search(int[] nums, int target) {
  3.         int l = 0, r = nums.length - 1;
  5.         while (l <= r) {
  7.             int m = (l + r) / 2;
  9.             if (nums[m] == target)
  10.                 return m;
  11.             if (nums[l] < nums[m]) {
  12.                 if (target <= nums[m] && target >= nums[l])
  13.                     r = m - 1;
  14.                 else
  15.                     l = m + 1;
  16.             } else if (nums[l] > nums[m]) {
  17.                 if (target >= nums[l] || target <= nums[m])
  18.                     r = m - 1;
  19.                 else
  20.                     l = m + 1;
  21.             } else
  22.                 l++;
  23.         }
  24.         return -1;
  25.     }

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.

参考：LeetCode 081 Search in Rotated Sorted Array II

  1.     public boolean search(int[] nums, int target) {
  3.         int l = 0, r = nums.length - 1;
  5.         while (l <= r) {
  7.             int m = (l + r) / 2;
  9.             if (nums[m] == target)
  10.                 return true;
  12.             if (nums[l] < nums[m]) {
  13.                 if (target <= nums[m] && target >= nums[l])
  14.                     r = m - 1;
  15.                 else
  16.                     l = m + 1;
  17.             } else if (nums[l] > nums[m]) {
  18.                 if (target >= nums[l] || target <= nums[m])
  19.                     r = m - 1;
  20.                 else
  21.                     l = m + 1;
  22.             } else
  23.                 l++;
  24.         }
  26.         return false;
  27.     }

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

参考：LeetCode 035 Search Insert Position

  1.     public int searchInsert(int[] nums, int target) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  7.         for (int i = 0; i < nums.length; i++) {
  8.             if (target <= nums[i]) {
  9.                 return i;
  10.             }
  11.         }
  13.         return nums.length;
  14.     }

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.

click to show follow up.

Follow up:

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?

参考：LeetCode 073 Set Matrix Zeroes

  1.     public void setZeroes(int[][] matrix) {
  3.         if (matrix == null || matrix.length == 0) {
  4.             return;
  5.         }
  7.         int mx = matrix.length;
  8.         int my = matrix[0].length;
  10.         // 两个变量，判断第一行和第一列是否有0
  11.         boolean xflag = false, yflag = false;
  13.         // 判断第一行是否有0
  14.         for (int i = 0; i < mx; i++) {
  15.             if (matrix[i][0] == 0) {
  16.                 xflag = true;
  17.                 break;
  18.             }
  19.         }
  21.         // 判断第一列是否有0
  22.         for (int i = 0; i < my; i++) {
  23.             if (matrix[0][i] == 0) {
  24.                 yflag = true;
  25.                 break;
  26.             }
  27.         }
  29.         // 其它行、列是否有0
  30.         for (int i = 1; i < mx; i++) {
  31.             for (int j = 1; j < my; j++) {
  32.                 if (matrix[i][j] == 0) {
  33.                     matrix[i][0] = 0;
  34.                     matrix[0][j] = 0;
  35.                 }
  36.             }
  37.         }
  39.         // 对于第一列，为0，则将所在行变成0
  40.         for (int i = 1; i < mx; i++) {
  41.             if (matrix[i][0] == 0) {
  42.                 for (int j = 0; j < my; j++) {
  43.                     matrix[i][j] = 0;
  44.                 }
  45.             }
  46.         }
  48.         // 对于第一行，为0，则将所在列变成0
  49.         for (int i = 0; i < my; i++) {
  50.             if (matrix[0][i] == 0) {
  51.                 for (int j = 0; j < mx; j++) {
  52.                     matrix[j][i] = 0;
  53.                 }
  54.             }
  55.         }
  57.         // 若原来第一行中有0，则将整行置0
  58.         if (xflag) {
  59.             for (int i = 0; i < mx; i++) {
  60.                 matrix[i][0] = 0;
  61.             }
  62.         }
  64.         // 若原来第一列中有0，则将整列置0
  65.         if (yflag) {
  66.             for (int i = 0; i < my; i++) {
  67.                 matrix[0][i] = 0;
  68.             }
  69.         }
  71.     }

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.

click to show follow up.

Follow up:
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?

参考：LeetCode 075 Sort Colors

  1.     public void sortColors(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return;
  5.         }
  7.         // 定义三个变量，存储三种颜色出现次数
  8.         int red = 0;
  9.         int white = 0;
  10.         int blue = 0;
  12.         // 循环一次，记录每种颜色出现次数
  13.         for (int i = 0; i < nums.length; i++) {
  14.             if (nums[i] == 0) {
  15.                 red++;
  16.             } else if (nums[i] == 1) {
  17.                 white++;
  18.             } else {
  19.                 blue++;
  20.             }
  21.         }
  23.         // 对nums数组重新赋值
  24.         int i = 0;
  25.         while (red-- > 0) {
  26.             nums[i++] = 0;
  27.         }
  28.         while (white-- > 0) {
  29.             nums[i++] = 1;
  30.         }
  31.         while (blue-- > 0) {
  32.             nums[i++] = 2;
  33.         }
  34.     }

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

参考：LeetCode 054 Spiral Matrix

  1.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  5.         if (matrix == null || matrix.length == 0) {
  6.             return rt;
  7.         }
  9.         int startx = 0, endx = matrix.length - 1;
  10.         int starty = 0, endy = matrix[0].length - 1;
  12.         while (startx <= endx && starty <= endy) {
  14.             // 上边的行，从左向右
  15.             for (int y = starty; y <= endy; y++) {
  16.                 rt.add(matrix[startx][y]);
  17.             }
  19.             // 右边的列，从上到下
  20.             for (int x = startx + 1; x <= endx; x++) {
  21.                 rt.add(matrix[x][endy]);
  22.             }
  24.             // 如果行或列遍历完，则退出循环
  25.             if (startx == endx || starty == endy) {
  26.                 break;
  27.             }
  29.             // 下边的行，从右向左
  30.             for (int y = endy - 1; y >= starty; y--) {
  31.                 rt.add(matrix[endx][y]);
  32.             }
  34.             // 左边的列，从下到上
  35.             for (int x = endx - 1; x >= startx + 1; x--) {
  36.                 rt.add(matrix[x][starty]);
  37.             }
  39.             startx++;
  40.             starty++;
  41.             endx--;
  42.             endy--;
  43.         }
  45.         return rt;
  46.     }

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 ]
]

参考：LeetCode 059 Spiral Matrix II

  1.     public int[][] generateMatrix(int n) {
  3.         if (n <= 0) {
  4.             return new int[0][0];
  5.         }
  7.         int[][] matrix = new int[n][n];
  9.         int num = 1;
  11.         int startx = 0, endx = n - 1;
  12.         int starty = 0, endy = n - 1;
  14.         while (startx <= endx && starty <= endy) {
  16.             // 上边的行，从左向右
  17.             for (int y = starty; y <= endy; y++) {
  18.                 matrix[startx][y] = num++;
  19.             }
  21.             // 右边的列，从上到下
  22.             for (int x = startx + 1; x <= endx; x++) {
  23.                 matrix[x][endy] = num++;
  24.             }
  26.             // 如果行或列遍历完，则退出循环
  27.             if (startx == endx || starty == endy) {
  28.                 break;
  29.             }
  31.             // 下边的行，从右向左
  32.             for (int y = endy - 1; y >= starty; y--) {
  33.                 matrix[endx][y] = num++;
  34.             }
  36.             // 左边的列，从下到上
  37.             for (int x = endx - 1; x >= startx + 1; x--) {
  38.                 matrix[x][starty] = num++;
  39.             }
  41.             startx++;
  42.             starty++;
  43.             endx--;
  44.             endy--;
  45.         }
  47.         return matrix;
  48.     }

Subsets

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

Note:

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

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

参考：LeetCode 078 Subsets

  1.     int target;// 次数
  2.     Integer[] stack;// 存储每次排列
  4.     List<List<Integer>> rt;// 存储结果
  6.     public void search(int p, int[] nums) {
  8.         // 若长度为k，则stack是其中一个结果，保存结果
  9.         if (p == target) {
  10.             rt.add(new ArrayList<Integer>(Arrays.asList(stack)));
  11.             return;
  12.         }
  14.         for (int i = 0; i < nums.length; i++) {
  16.             if (p > 0 && nums[i] <= stack[p - 1]) {
  17.                 continue;
  18.             }
  20.             stack[p] = nums[i];
  21.             search(p + 1, nums);
  22.         }
  23.     }
  25.     public List<List<Integer>> subsets(int[] nums) {
  27.         Arrays.sort(nums);
  29.         rt = new ArrayList<List<Integer>>();
  31.         // 分别做0~num.length长度的组合
  32.         for (int i = 0; i <= nums.length; i++) {
  33.             target = i;
  34.             stack = new Integer[i];
  35.             search(0, nums);
  36.         }
  38.         return rt;
  39.     }

Subsets II

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

Note:

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

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

参考：LeetCode 090 Subsets II

使用二进制，不需要递归。对于二进制中的每一位，0表示不选择，1表示选择。则有2^n种情况。
使用HashSet，能够直接过滤重复情况（先对数组排序，题目中也要求每个list非降序排列）。

  1.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  3.         if (nums == null) {
  4.             return null;
  5.         }
  7.         if (nums.length == 0) {
  8.             return new ArrayList<List<Integer>>();
  9.         }
  11.         Set<List<Integer>> set = new HashSet<List<Integer>>();
  13.         // 题目中要求每个list是非降序，所以要先从小到大排序
  14.         Arrays.sort(nums);
  16.         // 对于n位，有2^n种情况
  17.         for (int i = 0; i < Math.pow(2, nums.length); i++) {
  19.             List<Integer> list = new ArrayList<Integer>();
  20.             int tmp = i;
  22.             // 对于每种情况，分别求得二进制中1的个数
  23.             // 0代表不选择，1代表选择
  24.             for (int j = 0; j < nums.length; j++) {
  25.                 int bit = tmp & 1;
  26.                 tmp >>= 1;
  27.                 if (bit == 1) {
  28.                     list.add(nums[j]);
  29.                 }
  30.             }
  31.             set.add(list);
  32.         }
  34.         return new ArrayList<List<Integer>>(set);
  35.     }

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.

参考：LeetCode 228 Summary Ranges

  1.     public List<String> summaryRanges(int[] nums) {
  3.         List<String> rt = new ArrayList<String>();
  5.         if (nums == null || nums.length == 0) {
  6.             return rt;
  7.         }
  9.         for (int i = 0; i < nums.length; i++) {
  10.             int st = nums[i];
  11.             int ed = st;
  13.             while (i + 1 < nums.length && nums[i + 1] - ed == 1) {
  14.                 i++;
  15.                 ed++;
  16.             }
  18.             if (ed == st) {
  19.                 rt.add(st + "");
  20.             } else {
  21.                 rt.add(st + "->" + ed);
  22.             }
  23.         }
  25.         return rt;
  26.     }

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.

参考:LeetCode 062 Unique Paths

构造二维数组dp[m][n]，其中：

  1.     public int uniquePaths(int m, int n) {
  3.         if (m <= 0 || n <= 0) {
  4.             return 0;
  5.         }
  7.         int[][] dp = new int[m][n];
  9.         for (int y = 1; y < n; y++) {
  10.             dp[0][y] = 1;
  11.         }
  13.         for (int x = 1; x < m; x++) {
  14.             dp[x][0] = 1;
  15.         }
  17.         for (int y = 1; y < n; y++) {
  18.             for (int x = 1; x < m; x++) {
  19.                 dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
  20.             }
  21.         }
  23.         return dp[m - 1][n - 1];
  24.     }

Unique Paths II

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.

Note: m and n will be at most 100.

参考：LeetCode 063 Unique Paths II

和上一题一样，只是有障碍物的时候（obstacleGrid[i][j]==1），将对应的dp置0（dp[i][j]=0）

  1.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         if (obstacleGrid == null || obstacleGrid[0] == null) {
  4.             return 0;
  5.         }
  7.         if (obstacleGrid[0][0] == 1) {
  8.             return 0;
  9.         }
  11.         int m = obstacleGrid.length;
  12.         int n = obstacleGrid[0].length;
  14.         int[][] dp = new int[m][n];
  16.         for (int y = 1; y < n; y++) {
  17.             if (obstacleGrid[0][y] == 0) {
  18.                 dp[0][y] = 1;
  19.             } else {
  20.                 break;
  21.             }
  22.         }
  24.         for (int x = 1; x < m; x++) {
  25.             if (obstacleGrid[x][0] == 0) {
  26.                 dp[x][0] = 1;
  27.             } else {
  28.                 break;
  29.             }
  30.         }
  32.         for (int y = 1; y < n; y++) {
  33.             for (int x = 1; x < m; x++) {
  34.                 if (obstacleGrid[x][y] == 1) {
  35.                     dp[x][y] = 0;
  36.                 } else {
  37.                     dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
  38.                 }
  40.             }
  41.         }
  43.         return dp[m - 1][n - 1];
  44.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注