当前位置:   article > 正文

代码随想录二刷DAY1~3

代码随想录二刷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<intsearchRange(vector<int>& nums, int target) {
  25.         if(nums.size()==0return {-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<intsortedSquares(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==nullptrreturn 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==nullptrbreak;
  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==nullptrreturn 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. };

递归法:想不出来呀。

太抽象了,不管了。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/750715
推荐阅读
相关标签
  

闽ICP备14008679号