[关闭]
@Yano 2019-09-20T10:50:56.000000Z 字数 58138 阅读 11760

LeetCode Array 题目汇总（前500题）

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

1 Two Sum

https://leetcode.com/problems/two-sum/

题目描述

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

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

代码

  2. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  4.         if (nums == null || nums.length < 2)
  5.             return null;
  6.         Map<Integer, Integer> map = new HashMap<>();
  7.         for (int i = 0; i < nums.length; i++) {
  8.             map.put(target - nums[i], i);
  9.         }
  10.         for (int i = 0; i < nums.length; i++) {
  11.             Integer v = map.get(nums[i]);
  12.             if (v != null && v != i) {
  13.                 return new int[] { i, v };
  14.             }
  15.         }
  16.         return null;
  17.     }
  18. }

167 Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

题目描述

Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.

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

代码

  2. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  4.         if (nums == null || nums.length < 2)
  5.             return null;
  6.                 int start = 0, end = nums.length - 1;
  7.         while(start < end) {
  8.             int sum = nums[start] + nums[end];
  9.             if(sum == target) return new int[]{start + 1, end + 1};
  10.             else if(sum < target) start++;
  11.             else end--;
  12.         }
  13.         return null;
  14.     }
  15. }

15 3Sum

https://leetcode.com/problems/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: 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]
]

代码

  2. class Solution {
  3.     public List<List<Integer>> threeSum(int[] nums) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if(nums == null || nums.length < 3) return ans;
  6.                 Set<List<Integer>> ansSet = new HashSet<>();
  7.         Arrays.sort(nums);
  8.                 for(int l = 0; l <= nums.length - 3; l++) {
  9.             // 起始位置与前一个值相同，结果不会更多
  10.             if(l > 0 && nums[l] == nums[l - 1]) continue;
  11.             int m = l + 1, r = nums.length - 1, sum = -nums[l];
  12.             while(m < r) {
  13.                 if(nums[m] + nums[r] > sum) {
  14.                     r--;
  15.                 } else if(nums[m] + nums[r] < sum) {
  16.                     m++;
  17.                 } else {
  18.                     ansSet.add(Arrays.asList(nums[l], nums[m], nums[r]));
  19.                     m++;
  20.                 }
  21.             }
  22.         }
  23.         ans.addAll(ansSet);
  24.         return ans;
  25.     }
  26. }

16 3Sum Closest

https://leetcode.com/problems/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).

代码

  2. class Solution {
  3.     public int threeSumClosest(int[] nums, int target) {
  4.         if(nums == null || nums.length < 3) return 0;
  5.         Arrays.sort(nums);
  6.         int minGap = Integer.MAX_VALUE;
  7.         int ans = 0;
  8.                 for(int l = 0; l <= nums.length - 3; l++) {
  9.             // 起始位置与前一个值相同，结果不会更多
  10.             if(l > 0 && nums[l] == nums[l - 1]) continue;
  11.                         for(int m = l + 1, r = nums.length - 1; m < r; ) {
  12.                 int sum = nums[l] + nums[m] + nums[r];
  13.                 int gap = Math.abs(target - sum);
  14.                                 if(gap < minGap) {
  15.                     minGap = gap;
  16.                     ans = sum;
  17.                 }
  18.                                 if(sum == target) {
  19.                     return target;
  20.                 } else if(sum > target) {
  21.                     r--;
  22.                 } else {
  23.                     m++;
  24.                 }
  25.             }
  26.         }
  27.                 return ans;
  28.     }
  29. }

18 4Sum

https://leetcode.com/problems/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: 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]
]

代码

  2. class Solution {
  3.     public List<List<Integer>> fourSum(int[] nums, int target) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if (nums == null || nums.length < 4)
  6.             return ans;
  7.         Set<List<Integer>> ansSet = new HashSet<>();
  8.         Arrays.sort(nums);
  9.         for (int i0 = 0; i0 <= nums.length - 4; i0++) {
  10.             // 结果不会更好
  11.             if (i0 > 0 && nums[i0] == nums[i0 - 1])
  12.                 continue;
  13.             for (int i1 = i0 + 1; i1 <= nums.length - 3; i1++) {
  14.                 int sum = target - nums[i0] - nums[i1];
  15.                 int i2 = i1 + 1, i3 = nums.length - 1;
  16.                 while (i2 < i3) {
  17.                     if (nums[i2] + nums[i3] > sum) {
  18.                         i3--;
  19.                     } else if (nums[i2] + nums[i3] < sum) {
  20.                         i2++;
  21.                     } else {
  22.                         ansSet.add(Arrays.asList(nums[i0], nums[i1], nums[i2], nums[i3]));
  23.                         i2++;
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         ans.addAll(ansSet);
  29.         return ans;
  30.     }
  31. }

4 Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

题目描述

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

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

Example 1:

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

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

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

代码

  2. class Solution {
  3. public:
  4.     double findMedianSortedArrays(int A[], int m, int B[], int n) {
  5.                 int total = m + n;
  6.                 if(total & 0x1) return find_kth(A, m, B, n, total / 2 + 1);
  7.         else return (find_kth(A, m, B, n, total / 2)
  8.                         + find_kth(A, m, B, n, total / 2 + 1))/2.0;
  9.             }
  10.     private:
  11.     static int find_kth(int A[], int m, int B[], int n, int k){
  12.                 //always assume that m is equal or smaller than n
  13.         if(m > n) return find_kth(B, n, A, m, k);
  14.         if(m == 0) return B[k-1];
  15.         if(k == 1) return min(A[0], B[0]);
  16.                 //divide k into two parts
  17.         int ia = min(k / 2, m), ib = k - ia;
  18.                 if (A[ia - 1] < B[ib - 1])
  19.             return find_kth(A + ia, m - ia, B, n, k - ia);
  20.         else if (A[ia - 1] > B[ib - 1])
  21.             return find_kth(A, m, B + ib, n - ib, k - ib);
  22.         else
  23.             return A[ia - 1];
  24.     }
  25. };

11 Container With Most Water

https://leetcode.com/problems/container-with-most-water/

题目描述

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

Note: You may not slant the container and n is at least 2.

代码

  2. public class Solution {
  3.     public int maxArea(int[] nums) {
  4.         if(nums == null) return 0;
  5.         int ans = 0, start = 0, end = nums.length - 1;
  6.         while(start < end) {
  7.             int height = Math.min(nums[start], nums[end]);
  8.             ans = Math.max(ans, (end - start) * height);
  9.             if(nums[start] < nums[end]) {
  10.                 // 没有必要判断start 与右边的桶了，因为短板在 start
  11.                 start++;
  12.             } else {
  13.                 end--;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. }

42 Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

题目描述

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

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

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

代码

  2. class Solution {
  3.     public int trap(int[] height) {
  4.         if(height == null) return 0;
  5.                 int ans = 0, maxLeft = 0, maxRight = 0;
  6.         int left = 0, right = height.length - 1;
  7.                 while(left < right) {
  8.                         // 左位置的左边的最高值，右位置的右边的最高值
  9.             maxLeft = Math.max(maxLeft, height[left]);
  10.             maxRight = Math.max(maxRight, height[right]);
  11.                         if(maxLeft < maxRight) {
  12.                 ans += maxLeft - height[left++];
  13.             } else {
  14.                 ans += maxRight - height[right--];
  15.             }
  16.         }
  17.                 return ans;
  18.     }
  19. }

26 Remove Duplicates from Sorted Array

https://leetcode.com/problems/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 by modifying the input array in-place with O(1) extra memory.

Example:

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

代码

  2. class Solution {
  3.     public int removeDuplicates(int[] nums) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.         int count = 0;
  6.         for(int i = 1; i < nums.length; i++) {
  7.             if(nums[i] != nums[count]) {
  8.                 nums[++count] = nums[i];
  9.             }
  10.         }
  11.         return count + 1;
  12.     }
  13. }

80 Remove Duplicates from Sorted Array II

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int removeDuplicates(int[] nums) {
  4.         if(nums == null || nums.length <= 2) return nums.length;
  5.         int count = 1;
  6.         for(int i = 2; i < nums.length; i++) {
  7.             if(nums[i] != nums[count] || (nums[i] == nums[count] && nums[i] != nums[count - 1])) {
  8.                 nums[++count] = nums[i];
  9.             }
  10.         }
  11.         return count + 1;
  12.     }
  13. }

27 Remove Element

https://leetcode.com/problems/remove-element/

题目描述

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

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

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

Example:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

代码

  2. class Solution {
  3.     public int removeElement(int[] nums, int val) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.         int count = 0;
  6.         for(int i = 0; i < nums.length; i++) {
  7.             if(nums[i] != val) {
  8.                 nums[count++] = nums[i];
  9.             }
  10.         }
  11.         return count;
  12.     }
  13. }

31 Next Permutation

https://leetcode.com/problems/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

代码

  2. class Solution {
  3.     public void nextPermutation(int[] nums) {
  4.         // 1. 向前找首个递减
  5.         for (int i = nums.length - 2; i >= 0; i--) {
  6.             if (nums[i] < nums[i + 1]) {
  7.                 int j = nums.length - 1;
  8.                 // 2. 向前找首个大于nums[i]的索引
  9.                 for (; j > i; j--) {
  10.                     if (nums[j] > nums[i]) {
  11.                         break;
  12.                     }
  13.                 }
  14.                 // 3. 交换两个值
  15.                 swap(nums, i, j);
  16.                 // 4. 交换后面所有
  17.                 reverseSwap(nums, i + 1, nums.length - 1);
  18.                 return;
  19.             }
  20.         }
  21.         reverseSwap(nums, 0, nums.length - 1);
  22.     }
  23.     private void reverseSwap(int[] nums, int start, int end) {
  24.         while (start < end) {
  25.             swap(nums, start++, end--);
  26.         }
  27.     }
  28.     private void swap(int[] nums, int i, int j) {
  29.         int tmp = nums[i];
  30.         nums[i] = nums[j];
  31.         nums[j] = tmp;
  32.     }
  33. }

39 Combination Sum

https://leetcode.com/problems/combination-sum/

题目描述

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

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

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

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

[
  [7],
  [2, 2, 3]
]

代码

  2. class Solution {
  3.     public List<List<Integer>> combinationSum(int[] n, int target) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if(n == null || n.length == 0) return ans;
  6.                 Arrays.sort(n);
  7.         robot(n, 0, target, ans, new ArrayList<Integer>());
  8.         return ans;
  9.     }
  10.         private void robot(int[] n, int start, int left, List<List<Integer>> ans, List<Integer> tmp) {
  11.         if(left == 0) {
  12.             ans.add(new ArrayList<>(tmp));
  13.             return;
  14.         }
  15.                 for(int i = start; i < n.length; i++) {
  16.             // 如果不符合条件，则循环后面可以省略
  17.             if(left >= n[i]) {
  18.                 tmp.add(n[i]);
  19.                 robot(n, i, left - n[i], ans, tmp);
  20.                 tmp.remove(tmp.size() - 1);
  21.             } else {
  22.                 break;
  23.             }
  24.         }
  25.     }
  26. }

40 Combination Sum II

https://leetcode.com/problems/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.
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]
]

代码

  2. class Solution {
  3.     public List<List<Integer>> combinationSum2(int[] n, int target) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if(n == null || n.length == 0) return ans;
  6.                 Arrays.sort(n);
  7.         Set<List<Integer>> ansSet = new HashSet<>();
  8.         robot(n, 0, target, ansSet, new ArrayList<Integer>());
  9.         ans.addAll(ansSet);
  10.         return ans;
  11.     }
  12.         private void robot(int[] n, int start, int left, Set<List<Integer>> ansSet, List<Integer> tmp) {
  13.         if(left == 0) {
  14.             ansSet.add(new ArrayList<>(tmp));
  15.             return;
  16.         }
  17.                 for(int i = start; i < n.length; i++) {
  18.             // 如果不符合条件，则循环后面可以省略
  19.             if(left >= n[i]) {
  20.                 tmp.add(n[i]);
  21.                 robot(n, i + 1, left - n[i], ansSet, tmp);
  22.                 tmp.remove(tmp.size() - 1);
  23.             } else {
  24.                 break;
  25.             }
  26.         }
  27.     }
  28. }

216 Combination Sum III

https://leetcode.com/problems/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.

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.

代码

  2. class Solution {
  3.     public List<List<Integer>> combinationSum3(int k, int n) {
  4.         List<List<Integer>> ans = new ArrayList<>();        
  5.         robot(1, k, n, ans, new ArrayList<Integer>());
  6.         return ans;
  7.     }
  8.         private void robot(int start, int k, int left, List<List<Integer>> ans, List<Integer> tmp) {
  9.         if(k < 0 || left < 0) return;
  10.                 if(k == 0 && left == 0) {
  11.             ans.add(new ArrayList<>(tmp));
  12.             return;
  13.         }
  14.                 for(int i = start; i <= 9; i++) {
  15.             if(left >= i && k > 0) {
  16.                 tmp.add(i);
  17.                 robot(i + 1, k - 1, left - i, ans, tmp);
  18.                 tmp.remove(tmp.size() - 1);
  19.             } else {
  20.                 return;
  21.             }
  22.         }
  23.     }
  24. }

33 Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

题目描述

Suppose an array sorted in ascending order 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.

代码

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         if(nums == null) return -1;
  5.         int start = 0, end = nums.length - 1;
  6.         while(start <= end) {
  7.             int mid = (start + end) / 2;
  8.             if(nums[mid] == target) {
  9.                 return mid;
  10.             } 
  12.             // 左序列连续递增
  13.             if(nums[start] <= nums[mid]) {
  14.                 if(target >= nums[start] && target < nums[mid]) {
  15.                     end = mid - 1;
  16.                 } else {
  17.                     start = mid + 1;
  18.                 }
  19.             }
  21.             // 右序列连续递增
  22.             if(nums[mid] <= nums[end]) {
  23.                 if(target > nums[mid] && target <= nums[end]) {
  24.                     start = mid + 1;
  25.                 } else {
  26.                     end = mid - 1;
  27.                 }
  28.             }
  29.         }
  30.         return -1;
  31.     }
  32. }

81 Search in Rotated Sorted Array II

https://leetcode.com/problems/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?

Suppose an array sorted in ascending order 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).

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

The array may contain duplicates.

代码

  2. public class Solution {
  3.     public boolean search(int[] nums, int target) {
  4.                 int left = 0, right = nums.length - 1;
  5.                 while (left <= right) {
  6.                         int mid = (left + right) / 2;
  7.                         if (nums[mid] == target)
  8.                 return true;
  9.                         if (nums[left] < nums[mid]) {
  10.                 if (target <= nums[mid] && target >= nums[left])
  11.                     right = mid - 1;
  12.                 else
  13.                     left = mid + 1;
  14.             } else if (nums[left] > nums[mid]) {
  15.                 if (target >= nums[left] || target <= nums[mid])
  16.                     right = mid - 1;
  17.                 else
  18.                     left = mid + 1;
  19.             } else
  20.                 left++;
  21.         }
  22.                 return false;
  23.                 }
  24. }

34 Search for a Range

https://leetcode.com/problems/search-for-a-range/

题目描述

Given an array of integers sorted in ascending order, 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].

代码

  2. class Solution {
  3.     public int[] searchRange(int[] nums, int target) {
  4.         if(nums == null) return new int[] {-1, -1};
  5.                 // 先找到一个位置
  6.         int start = 0, end = nums.length - 1, ans = -1;
  7.         while(start <= end) {
  8.             int mid = (start + end) / 2;
  9.             if(nums[mid] == target) {
  10.                 ans = mid;
  11.                 break;
  12.             }
  13.                         if(nums[mid] < target) {
  14.                 start = mid + 1;
  15.             } else {
  16.                 end = mid - 1;
  17.             }
  18.         }
  19.                 if(ans == -1) return new int[] {-1, -1};
  20.         // 找起始点
  21.         int s = ans, e = ans;
  22.         while(s >= 0 && nums[s] == target) {
  23.             s--;
  24.         }
  25.         while(e < nums.length && nums[e] == target) {
  26.             e++;
  27.         }
  28.         return new int[] {s + 1, e - 1};
  29.     }
  30. }

35 Search Insert Position

https://leetcode.com/problems/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.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 1:

Input: [1,3,5,6], 0
Output: 0

代码

  2. class Solution {
  3.     public int searchInsert(int[] nums, int target) {
  4.         if(nums == null) return 0;
  5.                 // 先找到一个位置
  6.         int start = 0, end = nums.length - 1, ans = -1;
  7.         while(start <= end) {
  8.             int mid = (start + end) / 2;
  9.             if(nums[mid] == target) {
  10.                 ans = mid;
  11.                 break;
  12.             }
  13.                         if(nums[mid] < target) {
  14.                 start = mid + 1;
  15.             } else {
  16.                 end = mid - 1;
  17.             }
  18.         }
  19.                 if(ans != -1) return ans;
  20.         // start 和 end 已经包含了插入的信息
  21.         return start > end ? start : end;
  22.     }
  23. }

41 First Missing Positive

https://leetcode.com/problems/first-missing-positive/

题目描述

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

代码

  2. class Solution {
  3.     public int firstMissingPositive(int[] n) {
  4.         if(n == null) return 0;
  5.         for(int i = 0; i < n.length; i++) {
  6.             while(n[i] > 0 && n[i] <= n.length && n[i] != n[n[i] - 1]) {
  7.                 swap(n, i, n[i] - 1);
  8.             }
  9.         }
  10.                 // 遍历，找出n[i] != i + 1的结果
  11.         for(int i = 0; i < n.length; i++) {
  12.             if(n[i] != i + 1) return i + 1;
  13.         }
  14.         return n.length + 1;
  15.     }
  16.         private void swap(int[] n, int a, int b) {
  17.         int tmp = n[a];
  18.         n[a] = n[b];
  19.         n[b] = tmp;
  20.     }
  21. }

55 Jump Game

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public boolean canJump(int[] nums) {
  4.         if(nums == null || nums.length <= 1) return true;
  5.         // farest[i] 表示[0, i]能跳到的最远位置
  6.         int[] farest = new int[nums.length];
  7.         farest[0] = nums[0];
  8.                 for(int i = 1; i < nums.length; i++) {
  9.             // 若前面断档，则后面无解
  10.             if(farest[i - 1] == i - 1) break;
  11.             farest[i] = Math.max(farest[i - 1], nums[i] + i);
  12.         }
  13.                 return farest[nums.length - 1] != 0;
  14.     }
  15. }

45 Jump Game II

https://leetcode.com/problems/jump-game-ii/

题目描述

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

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

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

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

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

Note:
You can assume that you can always reach the last index.

代码

  2. public class Solution {
  3.     public int jump(int[] nums) {
  4.         if (nums.length <= 1) return 0;
  5.         int reach = nums[0];
  6.         int lastreach = 0;
  7.         int step = 0;
  8.                 for (int i = 1; i <= reach && i < nums.length; i++) {
  9.             if (i > lastreach) {
  10.                 step++;
  11.                 lastreach = reach;
  12.             }
  13.             reach = Math.max(reach, i + nums[i]);
  14.         }
  15.         if (reach < nums.length - 1) return 0;
  16.         return step;
  17.     }
  18. }

48 Rotate Image

https://leetcode.com/problems/rotate-image/

题目描述

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

Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 

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

rotate the input matrix in-place such that it becomes:

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

Example 2:

Given input matrix =

[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
],

rotate the input matrix in-place such that it becomes:

[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

代码

  2. class Solution {
  3.     public void rotate(int[][] matrix) {
  4.         if(matrix == null || matrix[0] == null || matrix.length != matrix[0].length) return;
  5.         int n = matrix.length;
  6.         // 中轴互换
  7.         for(int i = 0; i < n / 2; i++) {
  8.             for(int j = 0; j < n; j++) {
  9.                 swap(matrix, i, j, n - i - 1, j);
  10.             }
  11.         }
  12.                 // 正对角线互换
  13.         for(int i = 0; i < n; i++) {
  14.             for(int j = i + 1; j < n; j++) {
  15.                 swap(matrix, i, j, j, i);
  16.             }
  17.         }
  18.     }
  19.         private void swap(int[][] matrix, int x0, int y0, int x1, int y1) {
  20.         int tmp = matrix[x0][y0];
  21.         matrix[x0][y0] = matrix[x1][y1];
  22.         matrix[x1][y1] = tmp;
  23.     }
  24. }

53 Maximum Subarray

https://leetcode.com/problems/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.

click to show more practice.

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.

代码

  2. class Solution {
  3.     public int maxSubArray(int[] nums) {
  4.         if(nums == null) return 0;
  5.         // 数组可省略
  6.         int[] result = new int[nums.length];
  7.         int max = nums[0];
  8.         result[0] = nums[0];
  9.         for(int i = 1; i < nums.length; i++) {
  10.             // f(i + 1) = max(f(i) + n[i + 1], n[i + 1])
  11.             result[i] = Math.max(nums[i] + result[i - 1], nums[i]);
  12.             max = Math.max(max, result[i]);
  13.         }
  14.         return max;
  15.     }
  16. }

54 Spiral Matrix

https://leetcode.com/problems/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].

代码

  2. public class Solution {
  3.     public List<Integer> spiralOrder(int[][] matrix) {
  4.         List<Integer> result = new ArrayList<Integer>();
  5.         if (matrix == null || matrix.length == 0) {
  6.             return result;
  7.         }
  8.         int startx = 0, endx = matrix.length - 1;
  9.         int starty = 0, endy = matrix[0].length - 1;
  10.         while (startx <= endx && starty <= endy) {
  11.             for (int y = starty; y <= endy; y++) {
  12.                 result.add(matrix[startx][y]);
  13.             }
  14.             for (int x = startx + 1; x <= endx; x++) {
  15.                 result.add(matrix[x][endy]);
  16.             }
  17.             if (startx == endx || starty == endy) {
  18.                 break;
  19.             }
  20.             for (int y = endy - 1; y >= starty; y--) {
  21.                 result.add(matrix[endx][y]);
  22.             }
  23.             for (int x = endx - 1; x >= startx + 1; x--) {
  24.                 result.add(matrix[x][starty]);
  25.             }
  26.             startx++;
  27.             starty++;
  28.             endx--;
  29.             endy--;
  30.         }
  31.         return result;
  32.     }
  33. }

59 Spiral Matrix II

https://leetcode.com/problems/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 ]
]

代码

  2. public class Solution {
  3.     public int[][] generateMatrix(int n) {
  4.         if (n <= 0) {
  5.             return new int[0][0];
  6.         }
  7.         int[][] matrix = new int[n][n];
  8.         int num = 1;
  9.         int startx = 0, endx = n - 1;
  10.         int starty = 0, endy = n - 1;
  11.         while (startx <= endx && starty <= endy) {
  12.             for (int y = starty; y <= endy; y++) {
  13.                 matrix[startx][y] = num++;
  14.             }
  15.             for (int x = startx + 1; x <= endx; x++) {
  16.                 matrix[x][endy] = num++;
  17.             }
  18.             if (startx == endx || starty == endy) {
  19.                 break;
  20.             }
  21.             for (int y = endy - 1; y >= starty; y--) {
  22.                 matrix[endx][y] = num++;
  23.             }
  24.             for (int x = endx - 1; x >= startx + 1; x--) {
  25.                 matrix[x][starty] = num++;
  26.             }
  27.             startx++;
  28.             starty++;
  29.             endx--;
  30.             endy--;
  31.         }
  32.         return matrix;
  33.                 }
  34. }

56 Merge Intervals

https://leetcode.com/problems/merge-intervals/

题目描述

Given a collection of intervals, merge all overlapping intervals.

For example,

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

代码

  2. /**
  3.  * Definition for an interval.
  4.  * public class Interval {
  5.  *     int start;
  6.  *     int end;
  7.  *     Interval() { start = 0; end = 0; }
  8.  *     Interval(int s, int e) { start = s; end = e; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public List<Interval> merge(List<Interval> intervals) {
  13.         List<Interval> ans = new ArrayList<>();
  14.         if (intervals == null || intervals.size() == 0) {
  15.             return ans;
  16.         }
  17.                 // sort by start
  18.         Collections.sort(intervals, new Comparator<Interval>() {
  19.             @Override
  20.             public int compare(Interval o1, Interval o2) {
  21.                 return o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end;
  22.             }
  23.         });
  24.                 Interval o1 = intervals.get(0);
  25.         for(int i = 1; i < intervals.size(); i++) {
  26.             Interval o2 = intervals.get(i);
  27.             if (o1.end >= o2.start) {
  28.                 o1 = new Interval(o1.start, Math.max(o1.end, o2.end));
  29.             } else {
  30.                 ans.add(o1);
  31.                 o1 = o2;
  32.             }
  33.         }
  34.                 ans.add(o1);
  35.         return ans;
  36.     }
  37. }

57 Insert Interval

https://leetcode.com/problems/insert-interval/

题目描述

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

代码

  2. /**
  3.  * Definition for an interval.
  4.  * public class Interval {
  5.  *     int start;
  6.  *     int end;
  7.  *     Interval() { start = 0; end = 0; }
  8.  *     Interval(int s, int e) { start = s; end = e; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
  13.         List<Interval> result = new ArrayList<>();
  14.         int i = 0;
  15.         // add all the intervals ending before newInterval starts
  16.         while (i < intervals.size() && intervals.get(i).end < newInterval.start)
  17.             result.add(intervals.get(i++));
  18.         // merge all overlapping intervals to one considering newInterval
  19.         while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
  20.             newInterval = new Interval( // we could mutate newInterval here also
  21.                     Math.min(newInterval.start, intervals.get(i).start),
  22.                     Math.max(newInterval.end, intervals.get(i).end));
  23.             i++;
  24.         }
  25.         result.add(newInterval); // add the union of intervals we got
  26.         // add all the rest
  27.         while (i < intervals.size())
  28.             result.add(intervals.get(i++));
  29.         return result;
  30.     }
  31. }

62 Unique Paths

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int uniquePaths(int m, int n) {
  4.         // 可以优化成一维数组
  5.         int[][] dp = new int[m][n];
  6.         for(int i = 0; i < m; i++) {
  7.             for(int j = 0; j < n; j++) {
  8.                 if(i == 0 || j == 0) {
  9.                     dp[i][j] = 1;
  10.                 } else {
  11.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  12.                 }
  13.             }
  14.         }
  15.                 return dp[m - 1][n - 1];
  16.     }
  17. }

63 Unique Paths II

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int uniquePathsWithObstacles(int[][] grid) {
  4.         if(grid == null || grid.length == 0 ) return 0;
  5.         int m = grid.length, n = grid[0].length;
  6.         int[][] dp = new int[m][n];
  7.                 // 初始化行
  8.         for(int i = 0; i < n; i++) {
  9.             if(grid[0][i] == 1) break;
  10.             dp[0][i] = 1;
  11.         }
  12.                 // 初始化列
  13.         for(int i = 0; i < m; i++) {
  14.             if(grid[i][0] == 1) break;
  15.             dp[i][0] = 1;
  16.         }
  17.                 for(int i = 1; i < m; i++) {
  18.             for(int j = 1; j < n; j++) {
  19.                 if(grid[i][j] == 1) {
  20.                     dp[i][j] = 0;
  21.                 } else {
  22.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  23.                 }
  24.             }
  25.         }
  26.                 return dp[m - 1][n - 1];
  27.     }
  28. }

64 Minimum Path Sum

https://leetcode.com/problems/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.

Example 1:

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

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

代码

  2. class Solution {
  3.     public int minPathSum(int[][] grid) {
  4.         if(grid == null || grid.length == 0 ) return 0;
  5.         int m = grid.length, n = grid[0].length;
  6.         int[][] dp = new int[m][n];
  7.         dp[0][0] = grid[0][0];
  8.                 // 初始化行
  9.         for(int i = 1; i < n; i++) {
  10.             dp[0][i] = grid[0][i] + dp[0][i - 1];
  11.         }
  12.                 // 初始化列
  13.         for(int i = 1; i < m; i++) {
  14.             dp[i][0] = grid[i][0] + dp[i - 1][0];
  15.         }
  16.                 for(int i = 1; i < m; i++) {
  17.             for(int j = 1; j < n; j++) {
  18.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  19.             }
  20.         }
  21.                 return dp[m - 1][n - 1];
  22.     }
  23. }

66 Plus One

https://leetcode.com/problems/plus-one/

题目描述

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

You may assume the integer do not contain any leading zero, except the number 0 itself.

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

代码

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

73 Set Matrix Zeroes

https://leetcode.com/problems/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(mn) 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?

代码

  2. public class Solution {
  3.     public void setZeroes(int[][] matrix) {
  4.         if (matrix == null || matrix.length == 0) {
  5.             return;
  6.         }
  7.         int mx = matrix.length;
  8.         int my = matrix[0].length;
  9.         boolean xflag = false, yflag = false;
  10.         for (int i = 0; i < mx; i++) {
  11.             if (matrix[i][0] == 0) {
  12.                 xflag = true;
  13.                 break;
  14.             }
  15.         }
  16.         for (int i = 0; i < my; i++) {
  17.             if (matrix[0][i] == 0) {
  18.                 yflag = true;
  19.                 break;
  20.             }
  21.         }
  22.         for (int i = 1; i < mx; i++) {
  23.             for (int j = 1; j < my; j++) {
  24.                 if (matrix[i][j] == 0) {
  25.                     matrix[i][0] = 0;
  26.                     matrix[0][j] = 0;
  27.                 }
  28.             }
  29.         }
  30.         for (int i = 1; i < mx; i++) {
  31.             if (matrix[i][0] == 0) {
  32.                 for (int j = 0; j < my; j++) {
  33.                     matrix[i][j] = 0;
  34.                 }
  35.             }
  36.         }
  37.                 for (int i = 0; i < my; i++) {
  38.             if (matrix[0][i] == 0) {
  39.                 for (int j = 0; j < mx; j++) {
  40.                     matrix[j][i] = 0;
  41.                 }
  42.             }
  43.         }
  44.         if (xflag) {
  45.             for (int i = 0; i < mx; i++) {
  46.                 matrix[i][0] = 0;
  47.             }
  48.         }
  49.         if (yflag) {
  50.             for (int i = 0; i < my; i++) {
  51.                 matrix[0][i] = 0;
  52.             }
  53.         }
  54.     }
  55. }

75 Sort Colors

https://leetcode.com/problems/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?

代码

  2. class Solution {
  3.     public void sortColors(int[] nums) {
  4.         int start = 0, end = nums.length - 1;
  5.         for(int i = 0; i <= end; i++) {
  6.             // 顺序不能换，因为i后面可能换到0，但是i前面是不可能有2的
  7.             while(nums[i] == 2 && i < end) swap(nums, i, end--);
  8.             while(nums[i] == 0 && i > start) swap(nums, i, start++);
  9.         }
  10.     }
  11.         private void swap(int[] nums, int i, int j) {
  12.         int tmp = nums[i];
  13.         nums[i] = nums[j];
  14.         nums[j] = tmp;
  15.     }
  16. }

78 Subsets

https://leetcode.com/problems/subsets/

题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

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

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

代码

  2. class Solution {
  3.     public List<List<Integer>> subsets(int[] nums) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if(nums == null) return ans;
  6.         robot(0, nums, ans, new ArrayList<Integer>());
  7.         return ans;
  8.     }
  9.         private void robot(int start, int[] nums, List<List<Integer>> ans, List<Integer> tmp) {
  10.         ans.add(new ArrayList(tmp));
  11.                 for(int i = start; i < nums.length; i++) {
  12.             tmp.add(nums[i]);
  13.             robot(i + 1, nums, ans, tmp);
  14.             tmp.remove(tmp.size() - 1);
  15.         }
  16.     }
  17. }

90 Subsets II

https://leetcode.com/problems/subsets-ii/

题目描述

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

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

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

代码

  1. class Solution {
  2.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         Set<List<Integer>> ansSet = new HashSet<>();
  5.         Arrays.sort(nums); // 先排序
  6.         robot(0, nums, ansSet, new ArrayList<Integer>());
  7.         ans.addAll(ansSet);
  8.         return ans;
  9.     }
  11.     private void robot(int start, int[] nums, Set<List<Integer>> ans, List<Integer> tmp) {
  12.         ans.add(new ArrayList(tmp));
  14.         for(int i = start; i < nums.length; i++) {
  15.             tmp.add(nums[i]);
  16.             robot(i + 1, nums, ans, tmp);
  17.             tmp.remove(tmp.size() - 1);
  18.         }
  19.     }
  20. }

79 Word Search

https://leetcode.com/problems/word-search/

题目描述

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

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

For example,
Given board = 

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

代码

  2. public class Solution {
  3.     public static boolean exist(char[][] board, String word) {
  4.         if (board == null || board[0].length == 0 || board.length == 0
  5.                 || word == null) {
  6.             return false;
  7.         }
  8.         int rows = board.length;
  9.         int cols = board[0].length;
  10.         boolean[] visited = new boolean[rows * cols];
  11.         int pathLength = 0;
  12.         for (int row = 0; row < rows; row++) {
  13.             for (int col = 0; col < cols; col++) {
  14.                 if (dfs(board, rows, cols, row, col, word, pathLength, visited)) {
  15.                     return true;
  16.                 }
  17.             }
  18.         }
  19.         return false;
  20.     }
  21.     public static boolean dfs(char[][] board, int rows, int cols, int row,
  22.             int col, String word, int pathLength, boolean[] visited) {
  23.         if (pathLength == word.length()) {
  24.             return true;
  25.         }
  26.         boolean hasPath = false;
  27.         if (row >= 0 && row < rows && col >= 0 && col < cols
  28.                 && board[row][col] == word.charAt(pathLength)
  29.                 && !visited[row * cols + col]) {
  30.                         pathLength++;
  31.             visited[row * cols + col] = true;
  32.             hasPath = dfs(board, rows, cols, row, col - 1, word, pathLength,
  33.                     visited)
  34.                     || dfs(board, rows, cols, row - 1, col, word, pathLength,
  35.                             visited)
  36.                     || dfs(board, rows, cols, row, col + 1, word, pathLength,
  37.                             visited)
  38.                     || dfs(board, rows, cols, row + 1, col, word, pathLength,
  39.                             visited);
  40.             if (!hasPath) {
  41.                 pathLength--;
  42.                 visited[row * cols + col] = false;
  43.             }
  44.         }
  45.         return hasPath;
  46.     }
  47. }

84 Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

题目描述

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,

Given heights = [2,1,5,6,2,3],
return 10.

代码

  2. class Solution {
  3.     public int largestRectangleArea(int[] A) {
  4.         int area = 0;
  5.         for (int i = 0; i < A.length; i++) {
  6.             // 每找到局部峰值，向前遍历数组
  7.             if(i + 1 < A.length && A[i + 1] >= A[i]) continue;
  8.             int min = A[i];
  9.             for (int j = i; j >= 0; j--) {
  10.                 min = Math.min(min, A[j]);
  11.                 area = Math.max(area, (i + 1 - j) * min);
  12.             }
  13.         }
  14.         return area;
  15.     }
  16. }

85 Maximal Rectangle

https://leetcode.com/problems/maximal-rectangle/

题目描述

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

代码

  2. class Solution {
  3.     public int maximalRectangle(char[][] matrix) {
  4.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
  5.         int m = matrix.length, n = matrix[0].length;
  6.         int[][] height = new int[m][n];
  7.                 // height[i][j] 表示第i行j列的1的高度
  8.         for(int i = 0; i < m; i++) {
  9.             for(int j = 0; j < n; j++) {
  10.                 if(matrix[i][j] == '1') {
  11.                     height[i][j] = (i >= 1 ? height[i - 1][j] : 0) + 1;
  12.                 }
  13.             }
  14.         }
  15.                         int area = 0;
  16.         for(int i = 0; i < m; i++) {
  17.             area = Math.max(area, largestRectangleArea(height[i]));
  18.         }
  19.                 return area; 
  20.     }
  21.         public int largestRectangleArea(int[] A) {
  22.         int area = 0;
  23.         for (int i = 0; i < A.length; i++) {
  24.             // 每找到局部峰值，向前遍历数组
  25.             if(i + 1 < A.length && A[i + 1] >= A[i]) continue;
  26.             int min = A[i];
  27.             for (int j = i; j >= 0; j--) {
  28.                 min = Math.min(min, A[j]);
  29.                 area = Math.max(area, (i + 1 - j) * min);
  30.             }
  31.         }
  32.         return area;
  33.     }
  34. }

88 Merge Sorted Array

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public void merge(int[] A, int m, int[] B, int n) {
  4.         int i = m - 1, j = n - 1, end = m + n - 1;
  5.         while(i >= 0 && j >= 0) {
  6.             if(A[i] > B[j]) A[end--] = A[i--];
  7.             else A[end--] = B[j--];
  8.         }
  9.                 while(j >= 0) A[end--] = B[j--];
  10.     }
  11. }

118 Pascal's Triangle

https://leetcode.com/problems/pascals-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]
]

代码

  2. class Solution {
  3.     public List<List<Integer>> generate(int numRows) {
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         if(numRows <= 0) return ans;
  6.         int count = 0;
  7.         while(count < numRows) {
  8.             List<Integer> last = count > 0 ? ans.get(count - 1) : new ArrayList<>();
  9.             List<Integer> tmp = new ArrayList();
  10.             for(int i = 0; i <= count; i++) {
  11.                 if(i == 0 || i == count) tmp.add(1);
  12.                 else tmp.add(last.get(i - 1) + last.get(i));
  13.             }
  14.             ans.add(tmp);
  15.             count++;
  16.         }
  17.         return ans;
  18.     }
  19. }

119 Pascal's Triangle II

https://leetcode.com/problems/pascals-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?

代码

  2. class Solution {
  3.     public List<Integer> getRow(int rowIndex) {
  4.         List<Integer> tmp = new ArrayList<>();
  5.         if(rowIndex < 0) return tmp;
  6.                 List<Integer> pre = new ArrayList<>();        
  7.         int k = 0;
  8.         while(k <= rowIndex) {
  9.             for(int i = 0; i <= k; i++) {
  10.                 if(i == 0 || i == k) tmp.add(1);
  11.                 else tmp.add(pre.get(i - 1) + pre.get(i));
  12.             }
  13.             pre = new ArrayList(tmp);
  14.             tmp.clear();
  15.             k++;
  16.         }
  17.                     return pre;
  18.     }
  19. }

120 Triangle

https://leetcode.com/problems/triangle/

题目描述

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

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

代码

  2. class Solution {
  3.     public int minimumTotal(List<List<Integer>> triangle) {
  4.         int k = triangle.size();
  5.         if(k == 0) return 0;
  6.         List<Integer> pre = triangle.get(0);
  7.         List<Integer> ans = new ArrayList<>();
  8.         for(int i = 1; i < triangle.size(); i++) {
  9.             List<Integer> now = triangle.get(i);
  10.             for(int j = 0; j < now.size(); j++) {
  11.                 if(j == 0) ans.add(now.get(j) + pre.get(0));
  12.                 else if(j == now.size() - 1) ans.add(now.get(j) + pre.get(j - 1));
  13.                 else ans.add(now.get(j) + Math.min(pre.get(j), pre.get(j - 1)));
  14.             }
  15.             pre = new ArrayList(ans);
  16.             ans.clear();
  17.         }
  18.         return Collections.min(pre);
  19.     }
  20. }

121 Best Time to Buy and Sell Stock

https://leetcode.com/problems/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.

Example 1:

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

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

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

代码

  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         int maxProfit = 0;
  5.         // 存储从prices[0..i]的最小值
  6.         int lowest = Integer.MAX_VALUE;
  7.         for (int v : prices) {
  8.             lowest = Math.min(v, lowest);
  9.             maxProfit = Math.max(maxProfit, v - lowest);
  10.         }
  11.         return maxProfit;
  12.     }
  13. }

122 Best Time to Buy and Sell Stock II

https://leetcode.com/problems/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).

代码

  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         // 只要有利润就卖，就是最优解。
  5.         int profit = 0;
  6.         for(int i = 1; i < prices.length; i++) {
  7.             if(prices[i] > prices[i - 1]) {
  8.                 profit += prices[i] - prices[i - 1];
  9.             }
  10.         }
  11.         return profit;
  12.     }
  13. }

123 Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

题目描述

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

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

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

代码

  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         if (prices == null || prices.length == 0) {
  5.             return 0;
  6.         }
  7.         int n = prices.length;
  8.         /**
  9.          *  l[i][j]： 第i天可进行j次交易，且最后一次交易在最后一天卖出
  10.          *  g[i][j]： 第i天最多j次交易的最大利润
  11.          *  
  12.          *  l[i][j] = max(l[i-1][j], g[i-1][j-1]) + diff 
  13.          *  g[i][j] = max(l[i][j], g[i-1][j])
  14.          *  
  15.          *  l[i][j]（最后一次交易在最后一天卖出）公式分2种情况：
  16.          *  1. l[i-1][j] + diff：最后一次交易在i-1天卖出，加上diff相当于i-1天没卖，最后一天卖，不增加交易次数
  17.          *  2. g[i-1][j-1] + diff： i-1天卖出，结果不会比1好；i-1天未卖出，则可以卖，增加交易次数
  18.          *  
  19.          *  可以转化为一维数组 int[3]
  20.          */
  21.         int[][] l = new int[n][3];
  22.         int[][] g = new int[n][3];
  23.         for (int i = 1; i < n; i++) {
  24.             int diff = prices[i] - prices[i - 1];
  25.             for (int j = 1; j <= 2; j++) {
  26.                 l[i][j] = Math.max(l[i - 1][j], g[i - 1][j - 1]) + diff;
  27.                 g[i][j] = Math.max(l[i][j], g[i - 1][j]);
  28.             }
  29.         }
  30.         return g[n - 1][4];
  31.     }
  32. }

188 Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

题目描述

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

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

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

代码

  1. class Solution {
  2.     public int maxProfit(int k, int[] prices) {
  3.         if (prices == null || prices.length == 0) {
  4.             return 0;
  5.         }
  7.         if(k >= prices.length) return maxProfit(prices);
  9.         int n = prices.length;
  10.         int[] l = new int[k + 1];
  11.         int[] g = new int[k + 1];
  13.         for (int i = 1; i < n; i++) {
  14.             int diff = prices[i] - prices[i - 1];
  15.             for (int j = k; j >= 1; j--) {
  16.                 l[j] = Math.max(l[j], g[j - 1]) + diff;
  17.                 g[j] = Math.max(l[j], g[j]);
  18.             }
  19.         }
  21.         return g[k];
  22.     }
  24.     public int maxProfit(int[] prices) {
  25.         // 只要有利润就卖，就是最优解。
  26.         int profit = 0;
  27.         for(int i = 1; i < prices.length; i++) {
  28.             if(prices[i] > prices[i - 1]) {
  29.                 profit += prices[i] - prices[i - 1];
  30.             }
  31.         }
  32.         return profit;
  33.     }
  34. }

309 Best Time to Buy and Sell Stock with Cooldown

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

题目描述

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) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

代码

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices == null || prices.length == 0) return 0;
  5.         int n = prices.length;
  6.         // buy[i] 表示第i天持有股票，最大利润
  7.         int[] buy = new int[n];
  8.         // sell[i] 表示第i天为持股，最大利润
  9.         int[] sell = new int[n];
  10.         buy[0] = -prices[0];
  11.         sell[0] = 0;
  13.         for(int i = 1; i < n; i++) {
  14.             buy[i] = Math.max(buy[i - 1], (i > 1 ? sell[i - 2] : 0) - prices[i]);
  15.             sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
  16.         }
  18.         return sell[n - 1];
  19.     }
  20. }

714 Best Time to Buy and Sell Stock with Transaction Fee

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

题目描述

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

代码

  1. class Solution {
  2.     public int maxProfit(int[] prices, int fee) {
  3.         if(prices == null || prices.length == 0) return 0;
  5.         int n = prices.length;
  6.         // buy[i] 表示第i天持有股票，最大利润
  7.         int[] buy = new int[n];
  8.         // sell[i] 表示第i天为持股，最大利润
  9.         int[] sell = new int[n];
  10.         buy[0] = -prices[0];
  11.         sell[0] = 0;
  13.         for(int i = 1; i < n; i++) {
  14.             buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
  15.             sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
  16.         }
  18.         return sell[n - 1];
  19.     }
  20. }

128 Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

题目描述

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

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

Your algorithm should run in O(n) complexity.

代码

  2. class Solution {
  3.     public int longestConsecutive(int[] nums) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.         Map<Integer, Integer> map = new HashMap<>();
  6.         int ans = 0;
  7.                 for(int i = 0; i < nums.length; i++) {
  8.             if(!map.containsKey(nums[i])) {
  9.                 int left = map.containsKey(nums[i] - 1) ? map.get(nums[i] - 1) : 0;
  10.                 int right = map.containsKey(nums[i] + 1) ? map.get(nums[i] + 1) : 0;
  11.                             int times = left + right + 1;
  12.                                 map.put(nums[i], times);
  13.                 ans = Math.max(ans, times);
  14.                                 map.put(nums[i] - left, times);
  15.                 map.put(nums[i] + right, times);
  16.             }
  17.         }
  18.                 return ans;
  19.     }
  20. }

152 Maximum Product Subarray

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int maxProduct(int[] nums) {
  4.         int maxLocal = nums[0];
  5.         int minLocal = nums[0];
  6.         int global = nums[0];
  7.                 for(int i = 1; i < nums.length; i++) {
  8.             int temp = maxLocal;
  9.             maxLocal = Math.max(Math.max(nums[i] * temp, nums[i] * minLocal), nums[i]);
  10.             minLocal = Math.min(Math.min(nums[i] * temp, nums[i] * minLocal), nums[i]);
  11.                         global = Math.max(global, maxLocal);
  12.         }
  13.                 return global;
  14.     }
  15. }

153 Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

题目描述

Suppose an array sorted in ascending order 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.

代码

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

162 Find Peak Element

https://leetcode.com/problems/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.

click to show spoilers.

Note:
Your solution should be in logarithmic complexity.

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

代码

  2. class Solution {
  3.     public int findPeakElement(int[] nums) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.                 for(int i = 0; i < nums.length; i++) {
  6.             boolean left = i == 0 ? true : nums[i] > nums[i - 1];
  7.             boolean right = i == nums.length - 1 ? true : nums[i] > nums[i + 1];
  8.                         if(left && right) return i;
  9.         }
  10.                 return 0;
  11.     }
  12. }

169 Majority Element

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int majorityElement(int[] nums) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.         int count = 0, ans = 0;
  6.                 for(int v : nums) {
  7.             if(count == 0) {
  8.                 ans = v;
  9.                 count = 1;
  10.             } else if(v != ans) {
  11.                 count--;
  12.             } else {
  13.                 count++;
  14.             }
  15.         }
  16.                 return ans;
  17.     }
  18. }

229 Majority Element II

https://leetcode.com/problems/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.

代码

  1. class Solution {
  2.     public List<Integer> majorityElement(int[] nums) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         if(nums == null || nums.length == 0) return ans;
  5.         int n1 = 0, n2 = 0, c1 = 0, c2 = 0;
  7.         for(int v : nums) {
  8.             if(v == n1) c1++;
  9.             else if(v == n2) c2++;
  10.             else if(c1 == 0) {
  11.                 c1 = 1;
  12.                 n1 = v;
  13.             }
  14.             else if(c2 == 0) {
  15.                 c2 = 1;
  16.                 n2 = v;
  17.             }
  18.             else {
  19.                 c1--;
  20.                 c2--;
  21.             }
  22.         }
  24.         c1 = 0; c2 = 0;
  26.         for(int v : nums) {
  27.             if(v == n1) c1++;
  28.             else if(v == n2) c2++;
  29.         }
  31.         if(c1 > nums.length / 3) ans.add(n1);
  32.         if(c2 > nums.length / 3) ans.add(n2);
  34.         return ans;
  35.     }
  36. }

189 Rotate Array

https://leetcode.com/problems/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.

代码

  2. public class Solution { static 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.     }
  11.     public static void rotate(int[] nums, int k) {
  12.         int length = nums.length;
  13.         k = k % length;
  14.         if (length == 1 || k == 0)
  15.             return;
  16.         reverse(nums, 0, length - k - 1);
  17.         reverse(nums, length - k, length - 1);
  18.         reverse(nums, 0, length - 1);
  19.     }}

209 Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

题目描述

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

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

click to show more practice.

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.

代码

  2. class Solution {
  3.     public int minSubArrayLen(int s, int[] nums) {
  4.         if(nums == null || nums.length == 0) return 0;
  5.                 int start = 0, end = 0, sum = 0, ans = Integer.MAX_VALUE;
  6.         while(end < nums.length && start < nums.length) {
  7.                         // 滑动窗口，end
  8.             while(end < nums.length && sum < s) {
  9.                 sum += nums[end++];
  10.                 if(sum >= s) {
  11.                     ans = Math.min(ans, end - start);
  12.                 }
  13.             }
  14.                         // 滑动窗口，start
  15.             while(start < nums.length && sum >= s) {
  16.                 sum -= nums[start++];
  17.                 if(sum < s) {
  18.                     ans = Math.min(ans, end - start + 1);
  19.                 }
  20.             }
  21.         }
  22.                 return ans == Integer.MAX_VALUE ? 0 : ans;
  23.     }
  24. }

217 Contains Duplicate

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public boolean containsDuplicate(int[] nums) {
  4.         if(nums == null || nums.length == 0) return false;
  5.         Set<Integer> set = new HashSet<>();
  6.                 for(int v : nums) {
  7.             if(set.contains(v)) return true;
  8.             set.add(v);
  9.         }
  10.                 return false;
  11.     }
  12. }

219 Contains Duplicate II

https://leetcode.com/problems/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 absolute difference between i and j is at most k.

代码

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

238 Product of Array Except Self

https://leetcode.com/problems/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.)

代码

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

268 Missing Number

https://leetcode.com/problems/missing-number/

题目描述

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

Example 1

Input: [3,0,1]
Output: 2

Example 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

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.

代码

  2. class Solution {
  3.     public int missingNumber(int[] nums) {
  4.         if(nums == null) return 0;
  5.         int sum = (1 + nums.length) * nums.length / 2;
  6.                 for(int v : nums) {
  7.             sum -= v;
  8.         }
  9.                 return sum;
  10.     }
  11. }

283 Move Zeroes

https://leetcode.com/problems/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:

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

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

代码

  2. public class Solution {
  3.     public void moveZeroes(int[] nums) {
  4.         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.         }
  11.         // 把后面元素值0
  12.         for (int i = t; i < nums.length; i++) {
  13.             nums[i] = 0;
  14.         }
  15.                 }
  16. }

287 Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/

题目描述

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

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

代码

  2. public class Solution {
  3.     // https://segmentfault.com/a/1190000003817671
  4.     public int findDuplicate(int[] nums) {
  5.         int slow = 0;
  6.         int fast = 0;
  7.         // 找到快慢指针相遇的地方
  8.         do{
  9.             slow = nums[slow];
  10.             fast = nums[nums[fast]];
  11.         } while(slow != fast);
  12.         int find = 0;
  13.         // 用一个新指针从头开始，直到和慢指针相遇
  14.         while(find != slow){
  15.             slow = nums[slow];
  16.             find = nums[find];
  17.         }
  18.         return find;
  19.     }
  20. }

442 Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/

题目描述

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

代码

  2. class Solution {
  3.     public List<Integer> findDuplicates(int[] nums) {
  4.         List<Integer> ans = new ArrayList<>();
  5.         for(int i = 0; i < nums.length; i++) {
  6.             if(nums[i] != nums[nums[i] - 1]) {
  7.                 swap(nums, i, nums[i] - 1);
  8.                 i--;
  9.             }
  10.         }
  11.                 System.out.println(Arrays.toString(nums));
  12.                 for(int i = 0; i < nums.length; i++) {
  13.             if(nums[i] != i + 1) {
  14.                 ans.add(nums[i]);
  15.             }
  16.         }
  17.                 return ans;
  18.     }
  19.         private void swap(int[] nums, int i, int j) {
  20.         int tmp = nums[i];
  21.         nums[i] = nums[j];
  22.         nums[j] = tmp;
  23.     }
  24. }

289 Game of Life

https://leetcode.com/problems/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):

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

Follow up:

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

代码

  2. class Solution {
  3.     public void gameOfLife(int[][] board) {
  4.         final int m = board.length;
  5.         final int n = board[0].length;
  6.         /**
  7.         状态0：死细胞转为死细胞
  8.         状态1：活细胞转为活细胞
  9.         状态2：活细胞转为死细胞
  10.         状态3：死细胞转为活细胞
  11.          **/
  12.                 // encode
  13.         for (int i = 0; i < m; ++i) {
  14.             for (int j = 0; j < n; ++j) {
  15.                 int live = countLive(board, i, j); // number of live cells
  16.                 if (board[i][j] == 0 && live == 3) {
  17.                     board[i][j] = 3;
  18.                 } else if (board[i][j] == 1 && (live < 2 || live > 3)) {
  19.                     board[i][j] = 2;
  20.                 }
  21.             }
  22.         }
  23.         // decode
  24.         for (int i = 0; i < m; ++i) {
  25.             for (int j = 0; j < n; ++j) {
  26.                 board[i][j] %= 2;
  27.             }
  28.         }
  29.     }
  30.         private int countLive(int[][] nums, int i, int j) {
  31.         int count = 0;
  32.         int m = nums.length, n = nums[0].length;
  33.         for(int x = i - 1; x <= i + 1; x++) {
  34.             for(int y = j - 1; y <= j + 1; y++) {
  35.                 if(x == i && y == j) continue;
  36.                 if(x >= 0 && x < m && y >= 0 && y < n && (nums[x][y] == 1 || nums[x][y] == 2)) {
  37.                     count++;
  38.                 }
  39.             }
  40.         }
  41.         return count;
  42.     }
  43. }

380 Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/

题目描述

Design a data structure that supports all following operations in average O(1) time.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

代码

  2. class RandomizedSet {
  3.     private List<Integer> list;
  4.     private Map<Integer, Integer> map;
  5.     private Random random;
  6.     /** Initialize your data structure here. */
  7.     public RandomizedSet() {
  8.         list = new ArrayList<>();
  9.         map = new HashMap<>();
  10.         random = new Random();
  11.     }
  12.     /**
  13.      * Inserts a value to the set. Returns true if the set did not already contain
  14.      * the specified element.
  15.      */
  16.     public boolean insert(int val) {
  17.         if (map.containsKey(val)) {
  18.             return false;
  19.         }
  20.         list.add(val);
  21.         map.put(val, list.size() - 1);
  22.         return true;
  23.     }
  24.     /**
  25.      * Removes a value from the set. Returns true if the set contained the specified
  26.      * element.
  27.      */
  28.     public boolean remove(int val) {
  29.         if (!map.containsKey(val)) {
  30.             return false;
  31.         }
  32.         int index = map.get(val);
  33.         list.set(index, list.get(list.size() - 1));
  34.         map.put(list.get(index), index);
  35.         map.remove(val);
  36.         list.remove(list.size() - 1);
  37.         return true;
  38.     }
  39.     /** Get a random element from the set. */
  40.     public int getRandom() {
  41.         if (list.size() == 0) {
  42.             return 0;
  43.         }
  44.         return list.get(random.nextInt(list.size()));
  45.     }
  46. }

381 Insert Delete GetRandom O(1) - Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

题目描述

Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

代码

  2. class RandomizedCollection {
  3.     private List<Integer> list;
  4.     private Map<Integer, Set<Integer>> map;
  5.     private Random random;
  6.     /** Initialize your data structure here. */
  7.     public RandomizedCollection() {
  8.         list = new ArrayList<>();
  9.         map = new HashMap<>();
  10.         random = new Random();
  11.     }
  12.     /**
  13.      * Inserts a value to the set. Returns true if the set did not already contain
  14.      * the specified element.
  15.      */
  16.     public boolean insert(int val) {
  17.         boolean flag = false;
  18.         if (!map.containsKey(val)) {
  19.             flag = true;
  20.             map.put(val, new HashSet<Integer>());
  21.         }
  22.         map.get(val).add(list.size());
  23.         list.add(val);
  24.         return flag;
  25.     }
  26.     /**
  27.      * Removes a value from the set. Returns true if the set contained the specified
  28.      * element.
  29.      */
  30.     public boolean remove(int val) {
  31.         if (!map.containsKey(val)) {
  32.             return false;
  33.         }
  34.         int removed = map.get(val).iterator().next();
  35.         map.get(val).remove(removed);
  36.         if (removed < list.size() - 1) {
  37.             Integer tail = list.get(list.size() - 1);
  38.             list.set(removed, tail);
  39.             map.get(tail).remove(list.size() - 1);
  40.             map.get(tail).add(removed);
  41.         }
  42.         list.remove(list.size() - 1);
  43.         if (map.get(val).size() == 0) {
  44.             map.remove(val);
  45.         }
  46.         return true;
  47.     }
  48.     /** Get a random element from the set. */
  49.     public int getRandom() {
  50.         if (list.size() == 0) {
  51.             return 0;
  52.         }
  53.         return list.get(random.nextInt(list.size()));
  54.     }
  55. }
  56. /**
  57.  * Your RandomizedCollection object will be instantiated and called as such:
  58.  * RandomizedCollection obj = new RandomizedCollection();
  59.  * boolean param_1 = obj.insert(val);
  60.  * boolean param_2 = obj.remove(val);
  61.  * int param_3 = obj.getRandom();
  62.  */

414 Third Maximum Number

https://leetcode.com/problems/third-maximum-number/

题目描述

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

代码

  2. class Solution {
  3.     public int thirdMax(int[] nums) {
  4.         long max0 = Long.MIN_VALUE;
  5.         long max1 = Long.MIN_VALUE;
  6.         long max2 = Long.MIN_VALUE;
  7.                 for(int v : nums) {
  8.             if(max0 < v) {
  9.                 max2 = max1;
  10.                 max1 = max0;
  11.                 max0 = (long)v;
  12.             } else if(max1 < v && v < max0) {
  13.                 max2 = max1;
  14.                 max1 = (long)v;
  15.             } else if(max2 < v && v < max1){
  16.                 max2 = (long)v;
  17.             }
  18.                     }
  19.                 return (int) (max2 == Long.MIN_VALUE ? max0 : max2);
  20.     }
  21. }

485 Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/

题目描述

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input: [1,1,0,1,1,1]
Output: 3

Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

代码

  2. class Solution {
  3.     public int findMaxConsecutiveOnes(int[] nums) {
  4.         int ans = 0;
  5.         for(int i = 0; i < nums.length; i++) {
  6.             if(nums[i] == 1) {
  7.                 int count = 0;
  8.                 while(i < nums.length && nums[i] == 1) {
  9.                     count++;
  10.                     i++;
  11.                 }
  12.                 ans = Math.max(ans, count);
  13.             }
  14.         }
  15.                 return ans;
  16.     }
  17. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注