P4ul
文章
44
分类
14
评论
6

LeetCode 刷题笔记---（二）

| 算法 •
字数总计 10168 | 阅读时长 25分钟 | 阅读量 32

LeetCode刷题笔记---（二）

字节第二弹

ID：206

反转链表

是一道简单的递归题目，但是不知道为什么没做出来（debug的时候都对的，就是运行报错

我的思路想复杂了，总想着遍历到尾部再一点一点转向，其实就像Swap函数一样，只要有3个节点存在，就可以实现“互换”这里指链表转向

既然是递归，那么只要想清楚以下两个步骤即可

  1. 什么时候结束递归
  2. 每次递归干什么

1->2->3->x 要改成 x<-1<-2<-3

结束递归很好实现检测，检查下标是不是到x 就行

以x<-1为例，当前为1，前值为x

进入迭代时，取出后值备用，当前指向前值，前值变成当前，当前变成后值

整个流程像一条锁链一样，一环扣一环，最后结束的时候可以有多个判断标准，

  • 比如判断当前，因为当前值会在每次迭代结束变成后值，只需要判断当前值是否为nullptr即可，返回前值；

  • 或者判断后值是否为nullptr 这样当前值就是最后一个，返回当前值

    （这种情况要考虑当前是否为空，会多一步判断，而且少一步赋值）

    以后值为终止条件为例，当前还是最后一个值，后值还是x，前值还缺最后一个

所以如果用当前值判断，会好很多

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

头铁用后值

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=nullptr;
        if(!head)return nullptr;
        while(cur->next){
            ListNode* back=cur->next;
            cur->next=pre;
            pre=cur;
            cur=back;
        }
        cur->next=pre;
        return cur;
    }
};

ID：200

一眼连通块，但是忘了怎么做，好像是广度优先还是深度优先来着...

WOC！！！过了！！

过了！！

虽然花了接近40min，但是没看题解，纯靠回忆记起来了，我太屌了（虽然是一路debug出来的）

（而且中间因为不熟悉STL，浪费了很多时间）

思路历程：提前定义好方向向量，上下左右，遍历数组，遇到没访问过的岛屿压栈，然后DFS

栈内岛屿出栈后上下左右走，如果遇到岛屿了就继续压栈（判断边界，判断是否访问过、判断是否为岛屿）

然后每次DFS循环结束，就加一次count，作为连通块数量

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<int>> tensor={{-1,0},{1,0},{0,-1},{0,1}};
        stack<pair<int,int>>res;
        int count=0;
        vector<vector<char>> vist(grid.size(),vector<char> (grid[0].size(),'0'));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(vist[i][j]=='0'&&grid[i][j]=='1'){
                    res.push({i,j});
                    while(!res.empty()){
                        pair tmp =res.top();res.pop();
                        int nowx=tmp.first;int nowy=tmp.second;
                        vist[nowx][nowy]='1';
                        int nextx,nexty;
                        for(int c=0;c<4;c++){
                            nextx=nowx+tensor[c][0];
                            nexty=nowy+tensor[c][1];
                            if(nextx>=0&&nextx<grid.size()&&nexty>=0&&nexty<grid[0].size()){
                                if(vist[nextx][nexty]=='0'&&grid[nextx][nexty]=='1'){
                                    res.push({nextx,nexty});
                                }
                            }
                        }
                    }
                    count++;
                }
            }
        }

        return count;
    }
};

tips 可以更简单一点，不用visit数组，直接把相应的grid 地图改成’0‘ 即把岛屿改成海

减少判断时间，会快一点

ID：103

image-20240111201745712

思路历程：一开始觉得很简单，只要层次遍历就行，细节在于换孩子入队顺序，后来发现不太对

如果孩子顺序换了第二场看不出来，第三层就明显了

比如

1

3 4

56 78

如果是换孩子顺序

的出来的结果是 1 43 78 56 因为4先出队，所以78先入队，56后入队，导致结果不符合题意

后来改了一下，干脆简单点，别想太复杂，直接层序遍历获得正常顺序结果，然后奇数层将结果放入栈，然后逆序取出放入结果，没那么麻烦

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        stack<int> sub2;
        int count =0;
        int depth=0;
        que.push(root);
        if(!root)return res;
        while(!que.empty()){
            count=que.size();//获取当前层的节点个数
            depth++;
            vector<int> subres;
            while(count--){
                TreeNode* tmp=que.front();que.pop();
                
                if(tmp){
                        if(tmp->right)que.push(tmp->right);
                        if(tmp->left)que.push(tmp->left);
                    }
                    if(depth%2==1){
                        sub2.push(tmp->val);
                    }else{
                        subres.push_back(tmp->val);
                    }
                }
            while(!sub2.empty()){
                        subres.push_back(sub2.top());
                        sub2.pop();
                    }
            res.push_back(subres);
            subres={};
        }
        return res;
    }
};

题解给出来的答案更简单，比我的好多了，可以直接用vector插入开头和插入结尾进行存入即可

STL还是不熟练，push_front(a) 插入开头 push_back(a)插入结尾

ID：33

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

思路历程：看上去很像让我用二分查找的意思，就是写个变形的二分查找

首先将两段有序数组看成两个斜坡

image-20240111211312739

  • 你要考虑的情况最简单的一种就是，目标在前面的斜坡上（两点卡住）然后用二分

  • 只有一个数字的情况可以直接判断返回

难的是，不在前面的斜坡上，可能比最大值大，可能比最小值小，这两种情况几乎都是要遍历完的

这样你的头指针（i）不好乱动，尾指针（j）也不好乱移

不过既然不满足前面第一种情况，可以慢慢移动i，同时检查一下num[i]

（已经接近暴力了）但没办法，只能尽量往logn靠，至少我的思路是这样

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i=0;int j=nums.size();
        if(j==1&&nums[0]==target)return 0;
        while(i<j){
            if(nums[i]==target)return i;
            int mid=(i+j)/2;
            if(nums[mid]>target&&nums[i]<target){
                j=mid;
            }else if(nums[mid]==target){
                return mid;
            }else{
                i++;
            }
        }
        return -1;
    }
};

看到题解后，我发现我考虑的部分是题解的一半情况，

另一半我没考虑，不然可以更快，直接上图了，我考虑了前一种情况，后一种其实也可以直接二分

image-20240111212620757

感觉剩下的没啥好讲的，就是分类讨论

ID：255

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

比较简单

主要目的是熟悉一下C++的类怎么写方法和函数

class MyStack {
    private:
    queue<int> que;
    queue<int> tmp;
public:
    MyStack() {
        
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int tmp_num =que.back();
        int count = que.size();
        while(count--){
            
            if(count==0){
                que.pop();
            }else{
                tmp.push(que.front());que.pop();
            }
        }
        count=tmp.size();
        while(count--){
            que.push(tmp.front());tmp.pop();
        }
        return tmp_num;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

如果使用一个队列实现的话

要在push中加操作实现，每添加一个元素，就将所有元素弹出，

先插入最新元素，再将原来的元素插入

ID：25

今天做的第一道206的升级版

image-20240111215308473

思路历程：和上午一样，用递归，这次无非是分组递归，同时保证组之间的顺序不变

AC！！！！！！！！！

虽然花了40分钟，但是纯靠自己AC了！！！

思路就是，在特殊节点的地方进行处理，其他和早上那题没区别

特殊点knode，每段当中的开头点，逆序后的结尾点，

特殊点lastknode，上一段当中逆序过后的结尾点

在进入下一段前，上一段的结尾点指向这段的结尾点（逆序后就是开头点


class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cnt=head;
        ListNode* res;
        int length=1;
        while(cnt->next){
            cnt=cnt->next;
            length++;
        }
        int gp_nums=length/k;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        int i=0;
        ListNode* knode=nullptr;
        ListNode* lastknode=nullptr;
        while(i<k*gp_nums){
            ListNode* back;
            if(cur->next){
                back=cur->next;
            }else{
                back=nullptr;
            }
            if(i%k==0){
                lastknode=knode;
                knode=cur;
            }
            if((i+1)%k==0){
                if(i==k-1)res=cur;
                if(lastknode)lastknode->next=cur;
                cur->next=pre;
                knode->next=back;
                pre=knode;
                cur=back;
            }else{
                cur->next=pre;
                pre=cur;
                cur=back;
            }
            i++;
        }
        return res;
    }
};

美好的一天又结束了，后悔没有早点开始刷题，很难过0.0

时间真的不够用啊...今天说好的复习OS来着...

不过提前把嵌入式报告写完了，还能接受

文章作者： P4ul
本文链接：
版权声明： 本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 打工人驿站！
算法 c++ 杂谈
喜欢就支持一下吧
打赏
微信 微信
支付宝 支付宝