LeetCode-Array

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

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
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//暴力破解
// int size = nums.size();
// vector<int> res;
// for(int i=0;i<size;i++){
// int num1=nums[i];
// for(int j=i+1;j<size;j++){
// if(num1+nums[j]==target){
// res.push_back(i);
// res.push_back(j);
// return res;
// }
// }
// }
// return res;

//一次遍历哈希
map<int,int> hashMap;
int size = nums.size();
int temp;
for(int i = 0; i < size; i++){
temp=target - nums[i];
if(hashMap.find(temp)!=hashMap.end())
return std::vector{hashMap[temp],i};
hashMap[nums[i]]=i;
}
return {0};
}
};

Note

According to the experiment, using

faster than using ```map[x]
1
2
3
4
5
6
7
8
9
10
11
12

# Median of Two Sorted Arrays

## Description

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

You may assume **nums1** and **nums2** cannot be both empty.

**Example 1:**

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

The median is 2.0

1
2

**Example 2:**

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## Solution

```c++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
nums1.insert(nums1.end(),nums2.begin(),nums2.end());
sort(nums1.begin(),nums1.end());
int size = nums1.size();
if(size%2==0){
return (nums1[size/2-1]+nums1[size/2])/2.0;
}
else
{
return (nums1[size/2])*1.0;
}
return 1.0;
}
};

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

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
class Solution {
public:
int maxArea(vector<int>& height) {
// 暴力破解
// int max=0;
// int size=height.size();
// for(int i=0;i<size;i++){
// for(int j=i+1;j<size;j++){
// if((j-i)*min(height[i],height[j])>max)
// max = (j-i)*min(height[i],height[j]);
// }
// }
// return max;

//双指针
int maxArea = 0;
int l=0,r=height.size()-1;
while(l<r){
maxArea=max(maxArea,min(height[l],height[r])*(r-l));
if(height[l]<height[r])
l++;
else
r--;
}
return maxArea;
}
};

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

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int size = nums.size();
vector<int> v;
sort(nums.begin(),nums.end());
int p=0;
while(p<size && nums[p]<0)
p++;
for(int p1=0;p1<=p;p1++){
int p3=size-1;
for(int p2=p1+1;p2<p3;p2++){
int temp=nums[p1]+nums[p2];
while(p3>p2+1 && nums[p3]>-temp)
p3--;
if(nums[p3]==-temp){
v.push_back(nums[p1]);
v.push_back(nums[p2]);
v.push_back(nums[p3]);
res.push_back(v);
v.clear();
}
while(p2+1<size && nums[p2+1]==nums[p2])
p2++;
}
while(p1+1<size && nums[p1+1]==nums[p1])
p1++;
}
return res;
}
};

3Sum Closest

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

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
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
//暴力破解
// int res=-9999;
// int size = nums.size();
// for(int i=0; i< size; i++){
// for(int j=i+1;j<size;j++){
// for (int k=j+1;k<size;k++){
// if(abs(target - (nums[i]+nums[j]+nums[k]))<abs(target - res) )
// res = (nums[i]+nums[j]+nums[k]);
// }
// }
// }
// return res;
// }
int size = nums.size();
if (size<3) return -1;
int res= nums[1]+nums[2]+nums[0];
sort(nums.begin(),nums.end());
for( int i=0;i<size-2;i++){
int k=size-1;
int j=i+1;
while(j<k){
if(target ==(nums[i]+nums[j]+nums[k]))
return target;
if(abs(target - (nums[i]+nums[j]+nums[k]))<abs(target - res))
res = (nums[i]+nums[j]+nums[k]);
if(target>(nums[i]+nums[j]+nums[k])){
j++;
}
else {
k--;
}
}
}
return res;
}
};

4Sum

Description

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

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
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
vector<int> temp;
int size = nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<size - 3;i++){
for(int j=i+1;j<size-2;j++){
int r = size -1;
for(int k=j+1;k<r;k++){
while(r-1>k && nums[i]+nums[j]+nums[k]+nums[r]> target)
r--;
if(nums[i]+nums[j]+nums[k]+nums[r]== target){
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
temp.push_back(nums[r]);
res.push_back(temp);
temp.clear();
while (r-1>k && nums[r]==nums[r-1])
r--;
while(k+1<r && nums[k]==nums[k+1])
k++;
}

}
while(j+1<size-2 && nums[j]==nums[j+1])
j++;
}
while(i+1<size -3 && nums[i]==nums[i+1])
i++;
}
return res;
}
};

Remove Duplicates from Sorted Array

Description

Given a sorted array nums, 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 1:

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

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

Solution

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

Remove Element

Description

Given an array nums and a value val, 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 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

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

It doesn't matter what you leave beyond the returned length.

Example 2:

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

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

Solution

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

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,31,3,2
3,2,11,2,3
1,1,51,5,1

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
class Solution {
public:
void change(vector<int>& nums,int l,int r){
int size =l+r;
for(int i=l;i<=size/2;i++){
int temp = nums[i];
nums[i]=nums[size-i];
nums[size-i]=temp;
}
}
void nextPermutation(vector<int>& nums) {
int size = nums.size();
if(size <= 1)
return;
int i=size-2;
while(i>=0 && nums[i]>=nums[i+1])
i--;
if(i<0){
change(nums,0,size-1);
return;
}
int j=size-1;
while(j>=0 && nums[j]<=nums[i])
j--;
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
change(nums,i+1,size-1);
return;
}
};

Search in Rotated Sorted Array

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

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.

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

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

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
class Solution {
public:
int search(vector<int>& nums, int target) {
//暴力O(n^2)
// int size =nums.size();
// for(int i=0;i<size;i++){
// if(nums[i]==target)
// return i;
// }
// return -1;

//O(log(n))
int l=0,r=nums.size()-1;
int mid;
while(l<=r){
mid=l+(r-l)/2;
if(target==nums[mid])
return mid;
if(nums[mid]>=nums[l]){
if(target<nums[l] || target>nums[mid])
l=mid+1;
else
r=mid-1;
}
else
{
if(target>nums[r] || target<nums[mid])
r=mid-1;
else
l=mid+1;
}
}
return -1;
}
};

Note

1、一个典型的越界问题:mid=l+(r-l)/2;

Find First and Last Position of Element in Sorted Array

Description

Given an array of integers nums 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].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

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
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int begin=-1,end=-1,mid;
int l=0,r=nums.size()-1;
vector<int> res;
while(l<=r){
mid=l+(r-l)/2;
if(target==nums[mid]){
begin=mid;
end=mid;
while(begin-1>=0 && nums[begin-1]==nums[mid])
begin--;
while(end+1<=nums.size()-1 && nums[end+1]==nums[mid])
end++;
res.push_back(begin);
res.push_back(end);
return res;
}
if(target>nums[mid])
l=mid+1;
else
r=mid-1;
}
res.push_back(-1);
res.push_back(-1);
return res;
}
};

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.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Solution

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

Combination Sum

Description

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

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

Note:

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

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

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
class Solution {
public:
vector<vector<int>> res;
vector<int> temp;
void func(vector<int>& nums,int sum,int k,int target){
if(sum == target){
res.push_back(temp);
return;
}
if(sum>target)
return;
for(int i=k;i<nums.size() && nums[i]<=target-sum;i++){
sum+=nums[i];
temp.push_back(nums[i]);
func(nums,sum,i,target);
temp.pop_back();
sum-=nums[i];
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int sum=0,k=0;
sort(candidates.begin(),candidates.end());
func(candidates,sum,k,target);
return res;
}
};

Note

经典的回溯法可解。

Combination Sum II

Description

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

Each number in candidates 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.

Example 1:

1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

Example 2:

1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

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
class Solution {
public:
vector<vector<int>> res;
vector<int> v;
void func(vector<int>& nums,int sum,int k,int target){
if(sum==target){
res.push_back(v);
return;
}
if(k>=nums.size() ||sum+nums[k]>target)
return;
for(int i=k;i<nums.size();i++){
if(sum+nums[i]<=target){
sum+=nums[i];
v.push_back(nums[i]);
func(nums,sum,i+1,target);
v.pop_back();
sum-=nums[i];
}
while(i+1<nums.size() && nums[i]==nums[i+1])
i++;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
func(candidates,0,0,target);
return res;
}
};

First Missing Positive

Description

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int size =nums.size();
map<int,int> m;
for(int i=0;i<size;i++)
m[nums[i]]=1;
for(int i=1;i<=size;i++){
if(m.find(i)==m.end())
return i;
}
return size+1;
}
};

Trapping Rain Water

Description

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

Solution

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 trap(vector<int>& height) {
int res=0;
int size = height.size();
if(size<=1)
return res;
vector<int> left(size);
vector<int> right(size);
left[0]=0;
right[size-1]=0;
for(int i=1;i<size;i++)
left[i]=max(left[i-1],height[i-1]);
for(int i=size-2;i>=0;i--)
right[i]=max(right[i+1],height[i+1]);
for(int i=0;i<size;i++){
int temp = min(left[i],right[i]);
if(temp>height[i])
res+=temp-height[i];
}
return res;
}
};

Note

1、vector初始化:

(1): vector ilist1;

默认初始化,vector为空, size为0,意味着还没有分配内存空间。这种初始化方式适用于元素个数未知,需要在程序中动态添加的情况。

(2): vector ilist2(ilist);

vector ilist2 = ilist;

两种方式等价 ,ilist2 初始化为ilist 的拷贝,ilist必须与ilist2 类型相同,也就是同为int的vector类型,ilist2将具有和ilist相同的容量和元素

(3): vector ilist = {1,2,3.0,4,5,6,7};

vector ilist {1,2,3.0,4,5,6,7};

ilist 初始化为列表中元素的拷贝,列表中元素必须与ilist的元素类型相容,本例中必须是与整数类型相容的类型,整形会直接拷贝,其他类型会进行类型转换。

(4): vector ilist3(ilist.begin()+2,ilist.end()-1);

ilist3初始化为两个迭代器指定范围中元素的拷贝,范围中的元素类型必须与ilist3 的元素类型相容,在本例中ilist3被初始化为{3,4,5,6}。注意:由于只要求范围中的元素类型与待初始化的容器的元素类型相容,因此迭代器来自不同的容器是可能的,例如,用一个double的list的范围来初始化ilist3是可行的。另外由于构造函数只是读取范围中的元素进行拷贝,因此使用普通迭代器还是const迭代器来指出范围并没有区别。这种初始化方法特别适合于获取一个序列的子序列。

(5): vector ilist4(7);

默认值初始化,ilist4中将包含7个元素,每个元素进行缺省的值初始化,对于int,也就是被赋值为0,因此ilist4被初始化为包含7个0。当程序运行初期元素大致数量可预知,而元素的值需要动态获取的时候,可采用这种初始化方式。

(6):vector ilist5(7,3);

指定值初始化,ilist5被初始化为包含7个值为3的int。

2、对每一个i,都去计算它能装多少水:如果i值大于它所处的水平面,则无法装水;如果小于它所处的水平面,则能装水平面-i值。

Jump Game II

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

Solution

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:
void rotate(vector<vector<int>>& matrix) {
//it's easy to find the regular
int n = matrix[0].size();
if(n<=1)
return;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=temp;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n/2;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[i][n-1-j];
matrix[i][n-1-j]=temp;
}
}
}
};

Maximum Subarray

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

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
41
42
43
44
45
46
47
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//O(n)
// int size = nums.size();
// int res=-9999999,temp=0;
// if(size<=1)
// return size==1?nums[0]:0;
// for(int i=0;i<size;i++){
// temp+=nums[i];
// if(temp>res)
// res=temp;
// if(temp<0)
// temp=0;
// }
// return res;

//O(logn)
int size=nums.size();
if(size==0)
return 0;
return func(nums,0,size-1);

}
int func(vector<int>& nums,int left,int right){
if(left==right)
return nums[left];
int mid=left+(right-left)/2;
int leftSubSum=func(nums,left,mid);
int rightSubSum=func(nums,mid+1,right);
int leftBorderSum=-99999999,rightBorderSum=-99999999,temp=0;
for(int i=mid;i>=left;i--){
temp+=nums[i];
if(temp>leftBorderSum)
leftBorderSum=temp;
}
temp=0;
for(int i=mid+1;i<=right;i++){
temp+=nums[i];
if(temp>rightBorderSum)
rightBorderSum=temp;
}
if(leftSubSum>rightSubSum)
rightSubSum=leftSubSum;
return max(rightSubSum,leftBorderSum+rightBorderSum);
}
};

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

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
//从外到内依次遍历每一圈即可
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
if(n==0)
return res;
int left=0, right =matrix[0].size()-1;
int up=0, bottom=n-1;
while(left<=right && up<=bottom){
for(int i=left;i<=right;i++) res.push_back(matrix[up][i]);
for(int i=up+1;i<=bottom;i++) res.push_back(matrix[i][right]);
if(left<right && up<bottom){
for(int i=right-1;i>=left;i--) res.push_back(matrix[bottom][i]);
for(int i=bottom-1;i>up;i--) res.push_back(matrix[i][left]);
}
left++;
up++;
right--;
bottom--;
}
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
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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
//从后往前遍历,在当前位置如果能达到最后位置,则更新最后位置为当前位置
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size()-1;
for(int i=n;i>=0;i--){
if(i+nums[i]>=n)
n=i;
}
return n==0;
}
};

56. Merge Intervals

Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
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 considered overlapping.

Solution

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:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> res;
int n = intervals.size();
if(n==0)
return res;
sort(intervals.begin(),intervals.end(),[](Interval a,Interval b){return a.start<b.start;});
res.push_back(intervals[0]);
int p=0;
for(int i=1;i<n;i++){
if(intervals[i].start<= res[p].end){
res[p].end=max(intervals[i].end,res[p].end);
}
else{
res.push_back(intervals[i]);
p++;
}
}
return res;
}
};

57. Insert Interval

Description

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

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
41
42
43
44
45
46
47
//考虑各种边界情况,直接插入即可
class Solution {
public:
void func(vector<Interval>& intervals, int p , vector<Interval>& res){
int n = intervals.size();
while(p<n){
res.push_back(intervals[p]);
p++;
}
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> res;
int n = intervals.size();
if(n==0){
res.push_back(newInterval);
return res;
}
if(newInterval.end<intervals[0].start){
res.push_back(newInterval);
func(intervals,0,res);
return res;
}
if(newInterval.start>intervals[n-1].end){
func(intervals,0,res);
res.push_back(newInterval);
return res;
}
for(int i=0;i<n;i++){
if(intervals[i].end< newInterval.start){
res.push_back(intervals[i]);
}
else{
Interval temp;
temp.start = min(intervals[i].start, newInterval.start);

while(i<n && intervals[i].start<=newInterval.end){
i++;
}
temp.end = max(newInterval.end,intervals[i-1].end);
res.push_back(temp);
func(intervals,i,res);
return res;
}
}
return res;
}
};