LeetCode-array类总结（会持续更新...）

算法 , 评论

本文主要是对leetcode中的array类算法的总结，包含了各题的solution和常用的解决方法。

相关源码：code

此类题的常用思路：

1
2
3
4
5
6
if 数组是否有序：
	try 双指针法
	try 反向计算
else：
	try 集合数据结构
	try 打表法

119. Pascal’s Triangle II

Description：

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

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

我的解题思路是：有点动态规划的感觉，运用杨辉三角的特性：当前值 = 上层正对的值 + 上层正对前一个值。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex+1, 1);
        vector<int> temp(rowIndex+1, 1);
        
        for(int i = 0; i<rowIndex; i++){
            for(int j = 1; j <= i; j++){
                result[j] = temp[j] + temp[j-1];
            }
            for(int m=0; m<=rowIndex; m++){
                temp[m] = result[m];
            }
        }
        
        return result;
        
    }
    
};

下面有一个更好的解题思路：大致思路和我上面的差不多，只不过是反向计算的。这样做有个好处：减少空间分配。反向操作是array类解决方案中经常使用到的trick。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> vi(rowIndex + 1);
       	vi[0] = 1;
        for (int i = 0; i <= rowIndex ; ++i)
        {
        	for (int j = i; j > 0; --j)
        	{
	        	vi[j] = vi[j] + vi[j-1];
        	}
        }
        return vi;
    }
};

167. Two Sum II - Input array is sorted

Description:

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

解题思路:使用集合数据结构unordered_map<int, int>，一种map结构，find操作时间复杂度为O(1). 我们将数组中的元素逐个存入map，在存入的过程中检测是否有满足的元素；如果没有，就直接存入map.代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
    vector<int> twoSum(vector<int>& numbers, int target){
      vector<int> result;
      unordered_map<int, int> hash;
      for(int i=0; i < numbers.size(); i++){
          int temp = target - numbers[i];
      	  if(hash.find(temp) != hash.end()){
              result.push_back(hash.find(temp)+1);
              result.push_back(i+1);
              break;
          }
          hash[numbers[i]] = i;
      }
      return result;
    }
};

解题思路二：使用两个指针，一个从左出发，一个从有出发。因为本题使用的数组是有序的，所以这么做是有效的。用这两个指针去适配target。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int l = 0;
        int r = numbers.size()-1;
        while(l < r){
            int sum = numbers[l]+numbers[r];
            if(sum == target){
                result.push_back(l+1);
                result.push_back(r+1);
                break;
            }else if(sum > target){
                r--;
            }else if(sum < target){
                l++;
            }
        }
        
        return result;
    }
};

1. Two Sum

Description:

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:

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

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

解题思路：和上一题一样，但本题的数组有可能是无序的，因此，我们使用集合数据结构unordered_map。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int, int> hash;
        
        for(int i = 0; i<nums.size(); i++){
            int lag = target - nums[i];
            if(hash.find(lag) != hash.end()){
                result.push_back(hash[lag]);
                result.push_back(i);
                break;
            }
            
            hash[nums[i]] = i;
        }
        
        return result;
    }
};

219. Contains Duplicate II

Description:

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.

解题思路：本题要求数组相等的两个元素下标不超过k. 如果根据题意直接解，那么时间复杂度为O(n^2). 由于数组是无序的，我们倾向于使用集合数据结构。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() < 2 || k < 1){
            return false;
        }
        unordered_map<int, int> hash;
        bool flag = false;
        for(int i=0; i<nums.size(); i++){
            if(hash.find(nums[i]) != hash.end()){
                if(i - hash[nums[i]] <= k){
                    flag = true;
                    break;
                }
            }
            hash[nums[i]] = i;
        }
        
        return flag;
    }
};

414. Third Maximum Number

Description:

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:

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

Output: 1

Explanation: The third maximum is 1.

Example 2:

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

Output: 2

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

Example 3:

1
2
3
4
5
6
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.

解题思路：我们看到测试用例中有重复的元素，并且无序。我们考虑使用集合数据结构，加之要求输出的结果是有序的。我们最终使用有序的集合数据结构set.代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> bag;
        for(int i=0; i<nums.size(); i++){
            bag.insert(nums[i]);
            if(bag.size() > 3){
                bag.erase(bag.begin());
            }
        }
        
        return bag.size() == 3 ? *bag.begin() :*bag.rbegin();
    }
};

448. Find All Numbers Disappeared in an Array

Description:

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

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

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

Output:
[5,6]

解题思路：根据题意直接解的话，时间复杂度会为O(n^2)。我们就用空间换时间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        vector<int> extra(nums.size(), 0);
        for(int i = 0 ; i<nums.size(); i++){
            extra[nums[i]-1]++;
        }
        for(int i = 0; i<nums.size(); i++){
            if(extra[i]==0){
                result.push_back(i+1);
            }
        }
        
        return result;
    }
};

561. Array Partition I

Discription:

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

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

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

解题思路：总结规律，发现已排序数组的奇数项的和就是答案，这个可以通过反证法进行证明。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(int i =0; i<nums.size();i+=2){
            sum += nums[i];
        }
        return sum;
    }
};

解题思路二：上面这种解法时间复杂度是O(nlogn)，下面有种O(n)的解法。根据题目提示，给出了数据范围，并且数据无序，我们可以使用集合数据结构，只不过这次使用自己构造的数据结构打表法。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        vector<int> hashtable(20001,0);
        for(size_t i=0;i<nums.size();i++)
        {
            hashtable[nums[i]+10000]++;
        }
        int ret=0;
        int flag=0;
        for(size_t i=0;i<20001;){
            if((hashtable[i]>0)&&(flag==0)){
                ret=ret+i-10000;
                flag=1;
                hashtable[i]--;
            }else if((hashtable[i]>0)&&(flag==1)){
                hashtable[i]--;
                flag=0;
            }else i++;
        }
        return ret;
    }
};

581. Shortest Unsorted Continuous Subarray

Description:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

1
2
3
4
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

解题思路：本题数组部分有序，我们使用双指针，这有个小trick：左右两个指针同时前进，不像之前根据某个状态，单独调节单个指针。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int length = nums.size();
        int beg = -1;
        int end = -2;
        int max = nums[0];
        int min = nums[length-1];
        for(int i=1; i<length; i++){
            max = max<nums[i]?nums[i]:max;
            min = min>nums[length-i-1]?nums[length-i-1]:min;
            if(max>nums[i]) end=i;
            if(min<nums[length-i-1]) beg=length-i-1;
        }
        
        return end-beg+1;
    }
};

66. Plus One

Description:

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.

解题思路：总结规律，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
  vector<int> plusOne(vector<int>& digits){
      int n = digits.size();
      for(int i = n-1; i>=0; i--){
          if(digits[i] == 9){
              digits[i] = 0;
          }else{
              digits[i]++;
              return;
          }
      }
      digits[0] = 1;
      digits.push_back(0);
      return digits;
  }  
};

88. Merge Sorted Array

Description:

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.

解题思路：本题是两个有序的数组，我们要利用这一点，并且有个trick：反向计算。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public:
  		void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
            int i = m-1;
          	int j = n-1;
            int k = m+n-1;
            while(i>=0 && j>=0){
                if(nums1[i] > nums2[j]){
                    nums1[k--] = nums1[i--];
                }else{
                    nums1[k--] = nums2[j--];
                }
            }
           while(j>=0){
               nums1[k--] = nums2[j--];
           }
        }
}

118. Pascal’s Triangle

Description:

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

For example, given numRows = 5,
Return

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

解题思路：本题考察杨辉三角的性质，我们直接利用性质进行解题。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        for(int i=0; i < numRows; i++){
            result[i].resize(i+1);
            for(int j=0; j<=i; j++){
                if(j==i || j==0){
                    result[i][j] = 1;
                }else{
                    result[i][j] = result[i-1][j] + result[i-1][j-1];
                }
            }
        }
        return result;
    }
};

121. Best Time to Buy and Sell Stock

Description:

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:

1
2
3
4
5
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:

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

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

解题思路：观察本题规律，局部有序，关键点是判断极小值点。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2){
            return 0;
        }
        int result = 0;
        int min = 0;
        
        for(int i=0; i< prices.size()-1; i++){
            if(prices[i+1] > prices[i]){
                if(prices[i+1]-prices[min] > result){
                    
                    result = prices[i+1]-prices[min];
                }
            }else{
                if(prices[i+1] < prices[min]){
                    min = i+1;
                }
                
            }
            
        }
        return result;
    }
};

112. Best Time to Buy and Sell Stock II

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 (i.e., buy one and sell one share of the stock multiple times).

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

Example 1:

1
2
3
4
5
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

1
2
3
4
5
6
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <vector>

using namespace std;


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2) return 0;
        int result = 0;
        for(int i=0; i<prices.size()-1; i++){
            if(prices[i+1] > prices[i]){
                result += prices[i+1]-prices[i];
            }
        }
        
        return result;
    }
};

123. Best Time to Buy and Sell Stock III

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 at most two transactions.

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

Example 1:

1
2
3
4
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

1
2
3
4
5
6
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解题思路：经典题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int hold2=INT_MIN, hold1=INT_MIN;
        int release2=0, release1=0;
        for(int n : prices){
            release2=max(release2, hold2+n);
            hold2=max(hold2, release1-n);
            release1=max(release1, hold1+n);
            hold1=max(hold1,-n);
        }
        return release2;
    }
};

605. Can Place Flowers

Description:

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

1
2
3
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

1
2
3
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won’t exceed the input array size.

解题思路：根据本题题意直接作答，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count = 0;
        for(int i=0; i<flowerbed.size(); i++){
            if(flowerbed[i] == 0){
                int next = (i==flowerbed.size()-1) ? 0 : flowerbed[i+1];
                int pre = (i==0) ? 0 : flowerbed[i-1];
                if(next == 0 && pre == 0){
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }
        return count>=n;
    }
};

189. Rotate Array

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i=0; i<k;i++){
            int temp = nums[n-1];
            nums.pop_back();
            nums.insert(nums.begin(), temp);
        }
    }
};

35. Search Insert Position

Description:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
        for(int i=0; i<nums.size(); i++){
            if(i==0 && nums[0] > target){
                return 0;
            }
            if(nums[i] - target == 0){
                return i;
            }
            if(nums[i] > target){
                return i;
            }
        }
        
        return nums.size();
    }
};

53. Maximum Subarray

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

解题思路：本题很经典，使用动态规划，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0){
            return 0;
        }
        if(nums.size() == 1){
            return nums[0];
        }
        int sum = 0;
        int max = nums[0];
        
        for(int i=0; i<nums.size(); i++){
            //sum += nums[i];
            if(sum <= 0){
                sum = nums[i];
            }else{
                sum+= nums[i];
                
            }
            max = max > sum ? max:sum;
        }
        
        return max;
    }
};

665. Non-decreasing Array

Description:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

1
2
3
4
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

1
2
3
4
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        for(int i=1; i<nums.size() && count<=1; i++){
            if(nums[i-1] > nums[i]){
                count++;
                if(i-2<0 || nums[i-2] < nums[i]){
                    nums[i - 1] = nums[i];
                }else{
                    nums[i] = nums[i-1];
                }
            }
        }
        
        return count<=1;
    }
};

532. K-diff Pairs in an Array

Description:

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

1
2
3
4
5
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1
2
3
4
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1
2
3
4
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won’t exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

解题思路：本题有很强技巧性，使用了两个集合数据结构：map和set，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if(k < 0){
            return 0;
        }
        unordered_map<int, int> slot;
        unordered_set<int> result;
        for(int i=0; i<nums.size(); i++){
            if(slot.count(nums[i] - k)){
                result.insert(nums[i]-k);
            }
            if(slot.count(nums[i] + k)){
                result.insert(nums[i]);
            }
            slot[nums[i]] +=1;
        }
        
        return result.size();
    }
};

643. Maximum Average Subarray I

Description:Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

1
2
3
4
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int sum = 0;
        int max = 0;
        for(int i=0; i<nums.size(); i++){
            if(i<k){
                sum += nums[i];
                max = sum;
            }else{
                sum = sum+nums[i]-nums[i-k];
                max = max > sum ? max : sum;
            }
            
        }
        
        return max/(float)k;
    }
    
    double findMaxAverage2(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        int max = sum;
        
        for (int i = k; i < nums.size(); i++) {
            sum += nums[i] - nums[i - k];
            max = max > sum ? max : sum;
        }
        
        return max / 1.0 / k;
    }
};

628. Maximum Product of Three Numbers

Description:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

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

Example 2:

1
2
3
Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        int temp1 = nums[len-1]*nums[0]*nums[1];
        
        int temp2 = nums[len-1]*nums[len-2]*nums[len-3];
        
        return temp1>temp2?temp1:temp2;
    }
};

566. Reshape the Matrix

Description:

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

  1. The height and width of the given matrix is in range [1, 100].
  2. The given r and c are all positive.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int row = nums.size();
        int col = nums[0].size();
        if(row*col != r*c){
            return nums;
        }
        
        vector<vector<int>> result(r);
        for(int i=0; i<r;i++){
            result[i].resize(c);
        }
        
        for(int i=0; i<row*col; i++){
            result[i/c][i%c] = nums[i/col][i%col];
        }
        //delete result;
        return result;
    }
};

645. Set Mismatch

Description:The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

1
2
3
Input: nums = [1,2,2,4]
Output: [2,3]

Note:

  1. The given array size will in the range [2, 10000].
  2. The given array’s numbers won’t have any order.

解题思路：代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int[] res = new int[2];
        for (int i : nums) {
            if (nums[Math.abs(i) - 1] < 0) res[0] = Math.abs(i);
            else nums[Math.abs(i) - 1] *= -1;
        }
        for (int i=0;i<nums.length;i++) {
            if (nums[i] > 0) res[1] = i+1;
        }
        return res;
    }
};

106. Construct Binary Tree from Inorder and Postorder Traversal

Description:

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

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

For example, given

1
2
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //if(inorder.size()！=postorder.size()) return NULL;
        return treeHelper(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
    
    TreeNode* treeHelper(vector<int> &in, int startIn, int endIn, vector<int> &post, int startPost, int endPost){
        if(startIn>endIn ||startPost>endPost) return NULL;
        if(startIn==endIn && startPost== endPost) return new TreeNode(in[startIn]);
        TreeNode* root = new TreeNode(post[endPost]);
        for(int i=startIn;i<=endIn; i++){
            if(post[endPost]==in[i]){
                root->left=treeHelper(in,startIn,i-1,post,startPost,startPost+i-startIn-1);
                root->right=treeHelper(in,i+1,endIn,post,startPost+i-startIn,endPost-1);
            }
        }
        return root;
    }
};

108. Convert Sorted Array to Binary Search Tree

Description:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解题思路：二叉搜索树与有序数组，直观的想法就是中序遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <vector>

using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return NULL;
        if(nums.size()==1) return new TreeNode(nums[0]);
        int mid = nums.size()/2;
        TreeNode* root = new TreeNode(nums[mid]);
        vector<int> l(nums.begin(), nums.begin()+mid);
        vector<int> r(nums.begin()+mid+1,nums.end());
        root->left = sortedArrayToBST(l);
        root->right= sortedArrayToBST(r);
        return root;
    }
};

11. Container With Most Water

Description:

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.

img

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

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

解题思路：双指针法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size();
        if(len<2) return 0;
        int lo=0, hi=len-1, container=0;
        while(lo<hi){
            if(height[lo]<height[hi]){
                if(height[lo]*(hi-lo)>container){
                    container=height[lo]*(hi-lo);
                }
                lo++;
            }
            else{
                if(height[hi]*(hi-lo)>container){
                    container=height[hi]*(hi-lo);
                }
                hi--;
            }
        }
        return container;
    }
};

128. Longest Consecutive Sequence

Description:

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

Your algorithm should run in O(n) complexity.

Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

解题思路：使用集合数据结构，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res=0;
        unordered_map<int, int> hash;
        for(int n : nums){
            if(hash.find(n)==hash.end()){
                int left = hash.find(n-1)!=hash.end()?hash[n-1]:0;
                int right = hash.find(n+1)!=hash.end()?hash[n+1]:0;
                int sum=left+right+1;
                res=max(res,sum);
                hash[n]=sum;
                hash[n-left]=sum;
                hash[n+right]=sum;
            }
            else continue;
        }
        return res;
    }
};

15. 3Sum

Description:

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        if(nums.size()==0) return res;
        for(int i=0; i<nums.size()-1; i++){
            if(i==0 || (i>0 && nums[i]!=nums[i-1])){
                int lo=i+1, hi=nums.size()-1, sum=0-nums[i];
                while(lo<hi){
                    if(nums[lo]+nums[hi]==sum){
                        vector<int> tmp;
                        tmp.push_back(nums[lo]);
                        tmp.push_back(nums[i]);
                        tmp.push_back(nums[hi]);
                        res.push_back(tmp);
                        while(lo<hi && nums[lo]==nums[lo+1]) lo++;
                        while(lo<hi && nums[hi]==nums[hi-1]) hi--;
                        lo++;
                        hi--;
                    }else if(nums[lo]+nums[hi]<sum) lo++;
                    else hi--;
                }
                //res.push_back(tmp);
            }
        }
        return res;
    }
};

154. Find Minimum in Rotated Sorted Array II

Description:

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.

The array may contain duplicates.

Example 1:

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

Example 2:

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

Note:

经典题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo=0, hi=nums.size()-1;
        while(lo<hi){
            int mid = (lo+hi)/2;
            if(nums[mid]>nums[hi]) lo=mid+1;
            else if(nums[mid]<nums[hi]) hi=mid;
            else hi--;
        }
        return nums[lo];
    }
};

16. 3Sum Closet

Description:

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

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        int gap=INT_MAX;
        int res = 0;
        if(len==0) return 0;
        sort(nums.begin(),nums.end());
        for(int i=0; i<len-2; i++){
            if(i==0 || (i>0 && nums[i]!=nums[i-1])){
                int lo=i+1, hi=len-1, sum=target-nums[i];
                while(lo<hi){
                    if(nums[lo]+nums[hi]==sum) return target;
                    else if(nums[lo]+nums[hi]<sum){
                        if(abs(nums[lo]+nums[hi]-sum)<gap){
                            gap=abs(nums[lo]+nums[hi]-sum);
                            res=target-gap;
                        }
                        lo++;
                    }else{
                        if(abs(nums[lo]+nums[hi]-sum)<gap){
                            gap=abs(nums[lo]+nums[hi]-sum);
                            res=target+gap;
                        }
                        hi--;
                    }
                }
            }
        }
        return res;
    }
};

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.

Example:

1
2
3
4
5
6
7
8
Given array nums = [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]
]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len = nums.size();
        vector<vector<int>> res;
        if(len<4) return res;
        sort(nums.begin(),nums.end());
        for(int i=0; i<len-3; i++){
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1; j<len-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                int sum=target-nums[i]-nums[j];
                int m=j+1,n=len-1;
                while(m<n){
                    if(sum==nums[m]+nums[n]){
                        res.push_back(vector<int>{nums[i],nums[j],nums[m],nums[n]});
                        do{m++;}while(nums[m]==nums[m-1]&&m<n);
                        do{n--;}while(nums[n]==nums[n+1]&&m<n);
                    }else if(sum>nums[m]+nums[n]) m++;
                    else n--;
                }
            }
        }
        return res;
    }
};

228. Summary Ranges

Description:

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

Example 1:

1
2
3
4
Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

1
2
3
Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int len = nums.size();
        vector<string> res;
        if(len==0) return res;
        
        for(int i=0;i<len;i++){
            int tmp = nums[i];
            while(i+1<len && nums[i]+1==nums[i+1]) i++;
            if(tmp!=nums[i]) res.push_back(to_string(tmp)+"->"+to_string(nums[i]));
            else res.push_back(to_string(tmp));
        }
        
        return res;
    }
};

229. Majority Element II

Description:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

**Note: **The algorithm should run in linear time and in O(1) space.

Example 1:

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

Example 2:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        if(nums.size()==0) return res;
        int num1=nums[0], num2=nums[0], count1=1, count2=0;
        for(int n :nums){
            if(n==num1) count1++;
            else if(n==num2) count2++;
            else if(count1==0){
                num1=n;
                count1++;
            }else if(count2==0){
                num2=n;
                count2++;
            }else{
                count1--;
                count2--;
            }
        }
        count1=0;
        count2=0;
        for(int n: nums){
            if(n==num1) count1++;
            else if(n==num2) count2++;
        }
        if(count1>nums.size()/3) res.push_back(num1);
        if(count2>nums.size()/3) res.push_back(num2);
        return res;
    }
};

238. Product of Array Except Self

Description:

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

Example:

1
2
3
Input:  [1,2,3,4]
Output: [24,12,8,6]

**Note: **Please solve it without division and in O(n).

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

经典题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len);
        res[0]=1;
        for(int i=1; i<len; i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int right = 1;
        for(int i=len-1; i>=0;i--){
            res[i]*=right;
            right*=nums[i];
        }
        return res;
    }
};

此题有个trick，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m=board.size(), n=m?board[0].size():0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int count = 0;
                for(int I=max(i-1,0); I<min(i+2,m); I++){
                    for(int J=max(j-1,0); J<min(j+2,n); J++){
                        count+=board[I][J]&1;
                    }
                }
                if(count==3 || count-board[i][j]==3){
                    board[i][j] |= 2;
                }
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                board[i][j]>>=1;
            }
        }
    }
};

31. Next Permutation

Description:

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 and use only constant 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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return;
        int index=n-1;
        while(index){
            if(nums[index]>nums[index-1]) break;
            index--;
        }
        if(index==0) reverseSort(nums, 0, n-1);
        else{
            int val = nums[index-1];
            int j=n-1;
            while(j>=index){
                if(nums[j]>val) break;
                j--;
            }
            swap(nums[index-1], nums[j]);
            reverseSort(nums, index, n-1);
        }
        
    }
    
    void reverseSort(vector<int>& nums, int start, int end){
        if(start>end) return;
        for(int i=start; i<=(start+end)/2; i++) swap(nums[i],nums[start-i+end]);
    }
};

41. First Missing Positive

Description:

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

Example 1:

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

Example 2:

1
2
3
Input: [3,4,-1,1]
Output: 2

Example 3:

1
2
3
Input: [7,8,9,11,12]
Output: 1

Note:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            while(nums[i]>0 && nums[i]<=nums.size() && nums[nums[i]-1]!=nums[i]){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int i=0;i<nums.size(); i++){
            if(nums[i]!=i+1) return i+1;
        }
        return nums.size()+1;
    }
};

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

img
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!

Example:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int trap(vector<int>& height) {
        int l=0, r=height.size()-1;
        int lower=0, level=0;
        int water=0;
        while(l<r){
            lower = height[height[l]<height[r]?l++:r--];
            level=max(level,lower);
            water+=level-lower;
        }
        return water;
    }
};

45. Jump Game II

Description:

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.

Example:

1
2
3
4
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if(len<2) return 0;
        int curMax=0,nextMax=0,i=0, level=0;
        while(curMax-i+1>0){
            level++;
            for(;i<=curMax;i++){
                nextMax=max(nextMax,nums[i]+i);
                if(nextMax>=len-1) return level;
            }
            curMax=nextMax;
        }
        return 0;
    }
};

48. Rotate Image

Description:

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]
]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(),matrix.end());
        for(int i=0; i<matrix.size();i++){
            for(int j=i+1;j<matrix[i].size();j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    }
};

54. Spiral Matrix

Description:

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

Example 1:

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

Example 2:

1
2
3
4
5
6
7
Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int cicles = ((rows<cols?rows:cols)-1)/2+1;
        vector<int> res;
        res.clear();
        //if(rows==0) return res;
        for(int i=0; i<cicles; i++){
            for(int j=i;j<cols-i;j++) res.push_back(matrix[i][j]);
            for(int k=i+1;k<rows-i;k++) res.push_back(matrix[k][cols-i-1]);
            for(int m=cols-i-2; m>=i&&rows-i-1!=i;m--) res.push_back(matrix[rows-i-1][m]);
            for(int n=rows-i-2; n>i&&cols-i-1!=i;n--) res.push_back(matrix[n][i]);
        }
        return res;
    }
};

55. Jump Game

Description:

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.

Example 1:

1
2
3
4
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
4
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        int curMax=0, nextMax=0, i=0;
        while(curMax-i+1>0){
            for(;i<=curMax;i++){
                nextMax=max(nextMax,i+nums[i]);
                if(nextMax>=len-1) return true;
            }
            curMax=nextMax;
        }
        return false;
    }
};

56. Merge Intervals

Description:

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
4
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for an interval.*/
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
 
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        if(intervals.empty()) return res;
        sort(intervals.begin(),intervals.end(), [](Interval a, Interval b){return a.start<b.start;});
        res.push_back(intervals[0]);
        for(int i=1; i<intervals.size();i++){
            if(res.back().end<intervals[i].start) res.push_back(intervals[i]);
            else res.back().end=max(res.back().end, intervals[i].end);
        }
        return res;
    }
};

57. Insert Interval

Descripition:

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:

1
2
3
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for an interval.*/
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        auto it = intervals.begin();
        for(;it!=intervals.end();it++){
            if(newInterval.end<(*it).start) break;
            else if(newInterval.start>(*it).end) res.push_back(*it);
            else{
                newInterval.start=min(newInterval.start,(*it).start);
                newInterval.end=max(newInterval.end, (*it).end);
            }
        }
        res.push_back(newInterval);
        for(;it!=intervals.end();++it){
            res.push_back(*it);
        }
        return res;
    }
};

59. Spiral Matrix II

Description:

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

Example:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n));
        if(n==1){
            res[0][0]=1;
            return res;
        }
        int data=1;
        int circle = (n-1)/2+1;
        for(int i=0; i<circle;i++){
            for(int j=i;j<n-i;j++) res[i][j]=data++;
            for(int k=i+1;k<n-i;k++) res[k][n-i-1]=data++;
            for(int m=n-i-2;m>=i&&(n-i-1!=i);m--) res[n-i-1][m]=data++;
            for(int p=n-i-2;p>i&&(n-i-1!=i);p--) res[p][i]=data++;
        }
        return res;
    }
};

73. Set Matrix Zeros

Description:

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

Example 1:

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

Example 2:

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

Follow up:

  • 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?

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> tags;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(matrix[i][j]==0) tags.push_back(vector<int>{i,j});
            }
        }
        for(int k=0;k<tags.size();k++){
            int i=tags[k][0];
            int j=tags[k][1];
            for(int m=0;m<cols;m++) matrix[i][m]=0;
            for(int m=0;m<rows;m++) matrix[m][j]=0;
        }
    }
    
    void setZeroes2(vector<vector<int> > &matrix) {
        int col0 = 1, rows = matrix.size(), cols = matrix[0].size();
        
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) col0 = 0;
            for (int j = 1; j < cols; j++)
                if (matrix[i][j] == 0)
                    matrix[i][0] = matrix[0][j] = 0;
        }
        
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 1; j--)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            if (col0 == 0) matrix[i][0] = 0;
        }
    }
};

75. Sort Colors

Description:

Given an array with n objects colored red, white or blue, sort them **in-place **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.

Example:

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

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 a one-pass algorithm using only constant space?

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    void sortColors(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(int n : nums){
            hash[n]++;
        }
        int index=0;
        for(int i=0; i<3; i++){
            while(hash[i]--){
                nums[index++]=i;
            }
        }
    }
    void sortColors(int A[], int n) {
        int second=n-1, zero=0;
        for (int i=0; i<=second; i++) {
            while (A[i]==2 && i<second) swap(A[i], A[second--]);
            while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
        }
    }
};

84. Largest Rectangle in Histogram

Description:

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.

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

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

Example:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res=0;
        vector<int> index;
        heights.push_back(0);
        for(int i=0; i<heights.size();i++){
            while(index.size()>0 && heights[index.back()]>=heights[i]){
                int h = heights[index.back()];
                index.pop_back();
                int idx = index.size()>0?index.back():-1;
                if(res<h*(i-idx-1)) res=h*(i-idx-1);
            }
            index.push_back(i);
        }
        return res;
    }
};

85. Maximal Rectangle

Description:

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

Example:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        const int m = matrix.size();
        const int n = matrix[0].size();
        int left[n], right[n], height[n];
        fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
        int maxA = 0;
        for(int i=0; i<m; i++) {
            int cur_left=0, cur_right=n;
            for(int j=0; j<n; j++) { // compute height (can do this from either side)
                if(matrix[i][j]=='1') height[j]++;
                else height[j]=0;
            }
            for(int j=0; j<n; j++) { // compute left (from left to right)
                if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
                else {left[j]=0; cur_left=j+1;}
            }
            // compute right (from right to left)
            for(int j=n-1; j>=0; j--) {
                if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
                else {right[j]=n; cur_right=j;}
            }
            // compute the area of rectangle (can do this from either side)
            for(int j=0; j<n; j++)
                maxA = max(maxA,(right[j]-left[j])*height[j]);
        }
        return maxA;
    }
};

ciicA BOCer

个人简介