LeetCode81-90

81、搜索旋转排序数组 II

二分搜索,注意第 34 行的 L = L + 1 的条件判断,在最坏情况下,会使得该二分搜索退化为 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.size()==0)
return false;
int L = 0, R = nums.size()-1, mid;
while(L <= R){
cout << "L: " << L << ", R: " << R << endl;
mid = (L + R) >> 1;
if(nums[mid]>nums[L]){
if(target==nums[mid])
return true;
else if(target>nums[mid])
L = mid + 1;
else if(target>=nums[L])
R = mid - 1;
else
L = mid + 1;
}
else if(nums[mid]<nums[L]){
if(target==nums[mid])
return true;
else if(target<nums[mid])
R = mid - 1;
else if(target<=nums[R])
L = mid + 1;
else
R = mid - 1;
}
else{ // nums[mid] == nums[L]
if(target==nums[mid])
return true;
else
L = L + 1;
}
}
return false;
}
};

82、删除排序链表中的重复元素 II

模拟题

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:
ListNode* deleteDuplicates(ListNode* head) {
if(!head)
return NULL;
ListNode *new_head = new ListNode(0);
ListNode *new_p = new_head, *ptr=head;
long long int num = 1e10;
while(ptr!=NULL){
if(ptr->next!=NULL && ptr->val==ptr->next->val){
num = ptr->val;
ptr = ptr->next;
}
else if((long long int)(ptr->val)==num){
ptr = ptr->next;
}
else{
new_p->next = ptr;
ptr = ptr->next;
new_p = new_p->next;
new_p->next = NULL;
}
}
return new_head->next;
}
};

83、删除排序链表中的重复元素

模拟题,线上代码铁定不能这么写,内存泄露有木有!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *new_head = head, *p = head;
while(p!=NULL){
if(p->next!=NULL && p->val==p->next->val){
p->next = p->next->next;
continue;
}
p = p->next;
}
return new_head;
}
};

84、柱状图中最大的矩形

一个很自然的想法是,以当前柱子为高,向两边遍历,时间复杂度为 $O(n^2)$。降低复杂度的关键是,如何快速找到以当前柱子为高的左右边界left_index 和 right_index,维护一个单调的递增栈 >=,即可快速找到 left_index 和 right_index。具体如代码第 14 行所示,整体时间复杂度为 $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
24
25
26
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.size()==0)
return 0;
stack<int> index;
index.push(-1);
int max_area = 0, N = heights.size(), h;
for(int i=0; i<N; i++){
if(index.size()>1 && heights[i]<heights[index.top()]){
while(index.size()>1 && heights[i]<heights[index.top()]){
h = heights[index.top()];
index.pop();
max_area = max(max_area, h*(i-index.top()-1));
}
}
index.push(i);
}
while(index.size()>1){
h = heights[index.top()];
index.pop();
max_area = max(max_area, h*(N-index.top()-1));
}
return max_area;
}
};

85、

86、分隔链表

使用两个指针即可。

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:
ListNode* partition(ListNode* head, int x) {
ListNode *big_head = new ListNode(0), *small_head = new ListNode(0);
ListNode *big_p = big_head, *small_p = small_head, *p = head;
while(p){
if(p->val < x){
small_p->next = p;
p = p->next;
small_p = small_p->next;
small_p->next = NULL;
}
else{
big_p->next = p;
p = p->next;
big_p = big_p->next;
big_p->next = NULL;
}
}
small_p->next = big_head->next;
return small_head->next;
}
};

88、合并两个有序数组

一个小的 trick 是从后往前遍历,时间复杂度 $O(n+m)$, 空间复杂度 $O(1)$ 。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m-1, p2 = n-1, index = m+n-1;
while(p1>=0 && p2>=0)
nums1[index--] = nums1[p1]>=nums2[p2]? nums1[p1--] : nums2[p2--];
while(p1+p2>=-1)
nums1[index--] = p1>=0? nums1[p1--] : nums2[p2--];
}
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力,求打赏买面包~~
0%