首页 > 其他分享 >Offer68题 Day6

Offer68题 Day6

时间:2024-10-31 21:22:32浏览次数:1  
标签:ListNode val Day6 nullptr next l2 l1 Offer68

面试题 18. 删除链表的节点


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* dummy=new ListNode(0,head); // 虚拟头节点的值0,next指向head
        for(ListNode* cur=dummy;cur->next!=nullptr;cur=cur->next){
            if(cur->next->val==val){
                cur->next=cur->next->next;
                break;
            }
        }
        return dummy->next;
        
    }
};
// 时间复杂度O(n),空间复杂度O(1)。其中n为链表的长度。

面试题 19. 正则表达式匹配

面试题 21. 调整数组顺序使奇数位于偶数前面



class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) { // 快慢指针
        int low=0,fast=0;   // low指向奇数存放的位置,fast向右寻找奇数
        while(fast<actions.size()){
            if(actions[fast]&1){   // 找到奇数
                swap(actions[low],actions[fast]);
                low++;
            }
            fast++;
        }
        return actions;    
    }
};
/*
定义快慢双指针 fast 和 low ,fast 在前, low 在后 .
fast 的作用是向前搜索奇数位置,low 的作用是指向下一个奇数应当存放的位置
fast 向前移动,当它搜索到奇数时,将它和 nums[low] 交换,此时 low 向前移动一个位置 .
重复上述操作,直到 fast 指向数组末尾 .
*/

面试题 22. 链表中倒数第 k 个节点


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) { 
         // 快慢指针,fast先走k步,fast到链尾时,slow就是倒数第k个节点
        ListNode* slow=new ListNode(0,head);
        ListNode* fast=new ListNode(0,head);
        while(cnt--){   // fast指向第k个节点
            fast=fast->next;
        }

        while(fast!=nullptr){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

面试题 24. 反转链表


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        if(head==nullptr || head->next==nullptr){ return head;} // 链表为空或只有一个节点
        ListNode* ans=trainningPlan(head->next);  //递去: 深入链表,直到链尾,并返回链尾给ans,ans做反转后的表头节点
        head->next->next=head;   // 归来:反转指针
        head->next=nullptr;
        return ans;   
    }

    /*
    递归的时候是(head->next)->next, ((head->next)->next)->next, .... 这样递归直到链尾,没有改变head, head还是指向原来的头部。 head->1->2->...
    - 归来:返回最深层时处理的是head<-1, 第一个指针;返回第一层的时候,处理的是最后一个和都是第一个的指针

    */
};

面试题 25. 合并两个排序的链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 递归
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;  // 递归终止条件,一个表空
        if(l2==nullptr) return l1;
        if(l1->val<=l2->val){
            l1->next=trainningPlan(l1->next,l2);
            return l1;
        }else{
            l2->next=trainningPlan(l1,l2->next);
            return l2;
        }      
        
    }
};

/*
通过递归,每次选择 l1 或 l2 中较小的节点加入合并链表,并更新该节点的 next 指针指向后续合并的结果。递归层层返回后,最终形成一个新的有序链表。

1. 特判:如果有一个链表为空,返回另一个链表
2. 如果l1节点值比l2小,下一个节点应该是l1,应该return l1,在return之前,指定l1的下一个节点应该是l1.next和l2俩链表的合并后的头结点
3. 如果l1节点值比l2大,下一个节点应该是l2,应该return l2,在return之前,指定l2的下一个节点应该是l1和l2.next俩链表的合并后的头结点

时间复杂度:O(m+n)
空间复杂度:O(m+n)
*/


// 双指针
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode* dummy=new ListNode(0);   // 虚拟头节点
        ListNode* cur=dummy;              
        while(l1!=nullptr && l2!=nullptr){ // cur接上小的
            if(l1->val <l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next = (l1 != nullptr ? l1 : l2); // 哪个表还没空,就接上剩余的
        return dummy->next;
    }
};


标签:ListNode,val,Day6,nullptr,next,l2,l1,Offer68
From: https://www.cnblogs.com/itsinsane/p/18518902

相关文章

  • NOIP2024集训Day65 贪心
    NOIP2024集训Day65贪心A.[NOI2015]荷马史诗简化题意,即构造一颗\(k\)叉树,每个节点的权值为其所有孩子的权值之和,给定的\(n\)个数必须使用,其余空缺处用\(0\)补全。考虑使用优先队列,首先弹入\(n+(n-1)\%(k-1)\)个元素(不足处用0代替),然后每次弹出前\(k\)小的数......
  • Day65 小贪心 & 自选杂题
    哎怎么必可公益赛被爆破了,怎么lifan还加了几道我们的训练题目作为补偿。CF不知道死了多久了,一上午都没有打成duel!今天上午精神状态明显好了很多,可能和咖啡有点关系吧。按照时间顺序写题吧。AT_arc070_b可以进行撤销背包,也可以算前后缀背包,都是记录方案数。不难的。AT_a......
  • Offer68题 Day5
    面试题16.数值的整数次方classSolution{public:doublemyPow(doublex,intn){//快速幂算法通过将底数平方和指数减半的方式,减少了计算时间,从而将复杂度降低到O(logn)//最小的负数的绝对值比最大的正数更大,所以用long存储nlongp=......
  • Offer68题 Day4
    面试题14-I.剪绳子#include<iostream>#include<vector>usingnamespacestd;classSolution{public: staticintcuttingBamboo(constintbamboo_len){ vector<int>dp(bamboo_len+1,0);//dp数组存放乘积max if(bamboo_len<=1)return0; ......
  • offer68题 Day3
    面试题12.矩阵中的路径#include<iostream>#include<vector>#include<functional>usingnamespacestd;classSolution{public: boolexist(vector<vector<char>>&grid,conststring&target)const { constintm=grid.size(......
  • Offer68题 Day2 树的基础算法
    1.前中后序递归遍历//前序遍历classSolution{public:voidtraversal(TreeNode*cur,vector<int>&vec){if(cur==NULL)return;vec.push_back(cur->val);//中traversal(cur->left,vec);//左traversal(cur-&g......
  • Offer68题 Day3 两个基础算法
    1.DFS深度优先算法/* -深度优先算法 DFS从起始节点出发,沿着一条路径尽可能深入地访问每个节点,直到无法继续时再回退,寻找未访问的节点。 -使用递归实现。*/#include<iostream>#include<vector>usingnamespacestd;voidDFS(intnode,vector<vector<int>>&gra......
  • offer68题 Day2
    面试题07.重建二叉树前中序构建要根据二叉树的前序遍历和中序遍历结果来构建二叉树,我们可以利用以下性质:前序遍历的第一个元素总是当前树的根节点。中序遍历中,根节点将二叉树分为左子树和右子树。思路根据前序遍历的第一个元素确定根节点。在中序遍历中找到根节点位置......
  • day6:网络管理
    一,网络模型和通信协议网络模型概述网络模型是为了标准化和简化网络通信的设计框架。最常见的两个网络模型是OSI模型和TCP/IP模型。这两个模型通过分层的结构来定义网络通信的各个步骤和任务,每一层负责不同的功能。1.OSI模型(OpenSystemsInterconnectionModel)OSI......
  • Offer68题 Day1
    LCR120.寻找文件副本classSolution{//offer03public:intfindRepeatDocument(vector<int>&documents){//方法:哈希表,查找元素是否存在unordered_set<int>vsi;for(inti=0;i<documents.size();i++){if(vsi.count(documents......