代码随想录二刷DAY1~3

Day1

704 二分查找，简单

我也有自己写题解的能力了，而且思维很清晰：

找什么就在if里写什么。

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

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

35 搜索插入的位置，简单

自己想的：找右边界，代码比之前的简洁很多：

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

34 排序数组中查找元素的第一个和最后一个位置，中等

哇神呀，自己写的：

Line 1037: Char 9: runtime error: reference binding to null pointer of type ‘int’ (stl_vector.h)是空指针访问，注意检查nums.size()==0

1. class Solution {
2. private:
3.     int get_left(vector<int>&nums,int target){
4.         int l=0,r=nums.size()-1;
5.         while(l<r){
6.             int mid=l+r>>1;
7.             if(nums[mid]<target) l=mid+1;
8.             else r=mid;
9.         }
10.         if(nums[l]==target) return l;
11.         return -1;
12.     }
13.     int get_right(vector<int>&nums,int target){
14.         int l=0,r=nums.size()-1;
15.         while(l<r){
16.             int mid=(l+r+1)>>1;
17.             if(nums[mid]>target) r=mid-1;
18.             else l=mid;
19.         }
20.         if(nums[l]==target) return l;
21.         return -1;
22.     }
23. public:
24.     vector<int> searchRange(vector<int>& nums, int target) {
25.         if(nums.size()==0) return {-1,-1};
26.         int low=get_left(nums,target);
27.         int high=get_right(nums,target);
28.         return {low,high};
29.     }
30. };

27 移除元素，简单

快慢双指针入门。

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

其实第二句while写错了，但是竟然通过了。说明第二句while根本就没有执行！

性能很差，让我们优化一下：

直接删除第二句while就好了！因为nums[j]==val的话 根本不会进入while，交给for里面的j++来处理就好了：

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

DAY2

977 有序数组的平方，简单

1. class Solution {
2. public:
3.     vector<int> sortedSquares(vector<int>& nums) {
4.         for(auto &n:nums) n*=n;
5.         sort(nums.begin(),nums.end());
6.         return nums;
7.     }
8. };

没什么好说的。

209 长度最小的子数组，中等

最短连续子数组问题，滑动窗口。

怎么就一直学不会滑动窗口呢。。。

没做出来，发现问题了，滑动的应当是右指针for()里面填，这样一来，sum的初始化应当放到for的外面。Res的更新语句放的位置也有问题。我刚开始想错了，应当是：

//最短，一发现符合，就缩

//如果是最长，一发现不符合，就扩

很有收获。

1. class Solution {
2. public:
3.     int minSubArrayLen(int target, vector<int>& nums) {
4.         int bestres = INT_MAX, l = 0, tmpres = 0;
5.         int sum=0;
6.         for (int r = 0; r < nums.size(); r++) {
7.             sum += nums[r];
8.             // 最短，一发现符合，就缩
9.             // 如果是最长，一发现不符合，就扩
10.             while (sum >= target) {
11.                 tmpres = r – l + 1;
12.                 bestres = min(tmpres, bestres);
13.                 sum -= nums[l++];
14.             }
15.         }
16.         if(bestres==INT_MAX) return 0;
17.         return bestres;
18.     }
19. };

59 螺旋矩阵II，中等

不行呀，还是卡住了。

忘记更新x,y了。并且：走过了 !=0 那么就要更新偏移量。

1. class Solution {
2. public:
3.     vector<vector<int>> generateMatrix(int n) {
4.         vector<vector<int>> res(n,vector<int>(n,0));
5.         int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
6.         for(int x=0,y=0,d=0,k=1;k<=n*n;k++){
7.             //走过了或者撞墙
8.             res[x][y]=k;
9.             int a=x+dx[d],b=y+dy[d];
10.             if(a<0||a>n-1||b<0||b>n-1||res[a][b]!=0){
11.                 d=(d+1)%4;
12.                 a=x+dx[d];
13.                 b=y+dy[d];
14.             }
15.             //更新x,y!!
16.             x=a,y=b;
17.         }
18.         return res;
19.     }
20. };

DAY3

203移除链表元素，简单

Runtime error;因为缺少了一个更新当前指针的语句

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     ListNode *next;
6.  *     ListNode() : val(0), next(nullptr) {}
7.  *     ListNode(int x) : val(x), next(nullptr) {}
8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9.  * };
10.  */
11. class Solution {
12. public:
13.     ListNode* removeElements(ListNode* head, int val) {
14.         if(head==nullptr) return head;
15.         ListNode* dummyhead=new ListNode(0);
16.         dummyhead->next=head;
17.         ListNode* p=dummyhead;
18.         //缺少一个更新指针的语句！
19.         while(p->next!=nullptr){
20.             if(p->next->val==val) p->next=p->next->next;
21.             else p=p->next;
22.         }
23.         return dummyhead->next;
24.     }
25. };

ACWING29 删除链表中重复的节点

因为是排序的链表，那么只用针对连续情况去做判断和处理。

只要指针右移了，而且要访问其val或者next，则使用前必须判空（判自己，而不是next），否则会造成段错误。

题面：在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

这题有难度，要求重复的节点不保留，显然需要三指针了。

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     ListNode *next;
6.  *     ListNode(int x) : val(x), next(NULL) {}
7.  * };
8.  */
9. class Solution {
10. public:
11.     ListNode* deleteDuplication(ListNode* head) {
12.         if(head==nullptr) return head;
13.         auto dummy= new ListNode(-1);
14.         dummy->next=head;
15.         auto p=dummy;
16.         auto t=head;
17.         auto q=head->next;
18.         while(q!=nullptr){
19.             while(q!=nullptr&&q->val!=t->val){
20.                 p=t;
21.                 t=q;
22.                 q=q->next;
23.             }
24.             if(q==nullptr) break;
25.             while(q!=nullptr&&q->val==t->val){
26.                 q=q->next;
27.             }
28.             p->next=q;
29.             t=q;
30.             if(q!=nullptr)q=q->next;
31.         }
32.   return dummy->next;
33.     }
34. };

206反转链表，简单

迭代法和递归法都思路不清晰或者说没思路！重新学咯：

代码随想录

迭代法和递归法。

迭代法：

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     ListNode *next;
6.  *     ListNode() : val(0), next(nullptr) {}
7.  *     ListNode(int x) : val(x), next(nullptr) {}
8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9.  * };
10.  */
11. class Solution {
12. public:
13.     ListNode* reverseList(ListNode* head) {
14.         if(head==nullptr) return head;
15.         //这句初始化很重要，我们要让反转后的最后一个元素指向nullptr，那么head的pre自然应该初始化为nullptr
16.         ListNode* pre=nullptr;
17.         ListNode* cur=head;
18.         //条件也重要呀，不用判它的next，手写模拟就知道了。
19.         while(cur!=nullptr){
20.             ListNode* tmp=cur->next;
21.             cur->next=pre;
22.             pre=cur;
23.             cur=tmp;
24.         }
25.         //return 的是什么？好好想想 当然是pre
26.         return pre;
27.     }
28. };

递归法：想不出来呀。

太抽象了，不管了。