当前位置: 首页 > article >正文

C++刷题(一):顺序表 + 单链表

📝前言说明:
本专栏主要记录本人的基础算法学习以及刷题记录,使用语言为C++。
每道题我会给出LeetCode上的题号(如果有题号),题目,以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解,主要是个人见解,如有不正确,欢迎指正,一起进步!

🎬个人简介:努力学习ing
📋本专栏:C++刷题专栏
📋其他专栏:C++学习笔记,C语言入门基础,python入门基础,python刷题专栏
🎀CSDN主页 愚润泽

题目

  • 88.合并两个有序数组
  • 27.移除元素
  • 环形链表的约瑟夫问题
  • 189. 轮转数组
  • 面试题17.04. 消失的数字
  • 链表的回文结构
  • 138. 随机链表的复制
  • 142. 环形链表 II

88.合并两个有序数组

在这里插入图片描述
这道题的关键在于,如何讲nums2的数组元素插入nums1,因为nums1的长度为m+n,也就代表后面有空位,所以可以选择从后往前插入。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 从后往前放,一定有空位
        int p = m + n - 1, p1 = m - 1, p2 = n - 1;
        while(p2 >= 0)
        {
            if (p1 >= 0 && nums1[p1] > nums2[p2]){ // p1 等于0代表p1都排好了,剩下的填p2
                nums1[p--] = nums1[p1--]; // 先使用后--,填入nums1[p1]
            }
            else{
                nums1[p--] = nums2[p2--];
            }
        }
    }
};

27.移除元素

在这里插入图片描述
转换思想:删掉值==val的 → 保留(提取)值!=val

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        for(int x : nums){
            if (x != val){
                nums[i++] = x;
            }
        }
        return i;
    }
};

环形链表的约瑟夫问题

在这里插入图片描述
暴力做法(这题还可以动态规划,但是这里不提供):

class Solution {
public:
    int ysf(int n, int m) 
    {
        vector<int> nums(n);
        for (int i = 0; i < n; i++){
            nums[i] = i;
        }
        int start = 0;
        while(nums.size()!=1){
            int out = (start + m - 1) % nums.size();  // 往后移动m-1个位置是报到m的

            nums.erase(nums.begin() + out);

            start = out;
        }
        return nums[0] + 1;
    }
};

189. 轮转数组

在这里插入图片描述
简单做法:先复制后半部分的,再复制前半部分的,最后再把数组重新赋值回给nums

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        vector<int> nums2(n); // 
        int j = 0;
        for (int i = n - k ;i < n;i++){
            nums2[j] = nums[i];
            j++;
        }
        for(int i = 0; i < n-k; i++){
            nums2[j] = nums[i];
            j++;
        }
        // 将新数组的元素复制回原数组
        for (int i = 0; i < n; i++) 
        {
            nums[i] = nums2[i];
        }
    }
};

时间复杂度:因为要遍历两次数组:O(n),空间复杂度:要开一个跟随问题规模n的同样长的数组+三个整型(常数级):O(n)

改进:时间复杂度:O(n),空间复杂度O(1)的做法:
此图片来自LeetCode灵茶山艾府

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size(); // 轮转 k 次等于轮转 k % n 次
        ranges::reverse(nums);
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

面试题17.04. 消失的数字

在这里插入图片描述
两次遍历,第一次遍历记录是否出现,第二次遍历找出没出现的

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int>nums2 (n + 1, -1); 
        for(auto num : nums)
        {
            nums2[num] = 1;
        }
        int i = 0;
        for(i = 0; i < n; i++)
        {
            if(nums2[i] == -1)
            {
                break;
            }
        }
        return i;
    }
};

链表的回文结构

在这里插入图片描述
不是第一次写回文这道题了,但是再写还是容易出现问题。方法:中间节点+反转链表+依次比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* slow = A;
        ListNode* fast = A;
        while(fast!= nullptr && fast->next != nullptr) // 这判断条件的时候一定要注意
        // 原则:下面能使用到的指针要避免为空,如:fast->next != nullptr
        // 如果要判断 fast->next  ,则前提是fast != nullptr (所以要写两个)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow; 
        // 找到中间节点,然后反转后半部分的链表,反转后按顺序比较
        // 注意:前半部分的长度>=比后半部分长(偶数时>,因为偶数时前半部分的最后一个节点依然指向mid,画图好理解),因此比完短的即可
        ListNode* pre = nullptr;
        ListNode* cur = mid;
        while(cur){
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        // 反转完以后,pre指向原反转链表的最后一个节点,cur指向原最后一个节点的后一个位置
        ListNode* p1 = A; // 第一段链表的开始
        ListNode* p2 = pre; // 第二段反转后链表的开始
        while(p2 != nullptr)
        {
            if(p1->val != p2->val){
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

138. 随机链表的复制

在这里插入图片描述
题解(来源于灵茶山艾府):
在这里插入图片描述

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) { // 这里应该是官方给漏了,实际上可以传3个参数
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr){
            return nullptr;
        }
        for (Node*cur = head; cur; cur = cur->next->next) // 走两步才到原链表的下一个节点
        {
            cur->next = new Node(cur->val, cur->next, nullptr); // 这里就是能传三个参数,我也不晓得为什么
        }

        for (Node* cur = head; cur; cur = cur->next->next){
            if(cur->random){
                cur->next->random = cur->random->next; // 原链表random指向的节点的下一个节点,就是新random要指向的。
            }
        }

        Node* new_head = head->next;
        Node* cur = head;
        for(; cur->next->next; cur = cur->next)
        {
            Node* copy = cur->next; // 记录下新链表的节点
            cur -> next = cur->next->next; // 恢复原来的
            copy -> next = copy -> next->next; // 连接新的
        }
        cur->next = nullptr;
        return new_head;
    }
};

最后的拆分需要注意:混合链表的顺序为:旧1,新1,旧2,新2,旧3,......,旧n,新n,nullptr,两个新节点相连时会丢失一个旧节点(旧节点同理),所以:当一开始记录了旧1新1的位置时,应该先让旧1旧2相连,此时不会丢失新1要连接的下一个节点的信息。

142. 环形链表 II

在这里插入图片描述
这道题也是第二次写了。快慢指针(这里是快的速度是慢的的两倍),快的一定会追上慢的,然后我们探索位置关系:
在这里插入图片描述
这次关系都推出来了,但是还是没想到最后一步,重新让头指针和慢指针一起走,必会在入环口相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                while(head != slow){
                    head = head->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助,那简直是太酷啦!
若有不足,还请大家多多指正,我们一起学习交流!
📢公主,王子:点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持!祝大家都能得偿所愿,天天开心!!!


http://www.kler.cn/a/585837.html

相关文章:

  • OpenHarmony-XTS测试
  • UE5.5 Niagara初始化粒子模块
  • 【技海登峰】Kafka漫谈系列(八)Controller:Zookeeper模式与KRaft模式
  • STAR Decomposition 一种针对极端事件的信号分解方法 论文精读加复现
  • AI大模型测试用例生成平台
  • Nginx正向代理HTTPS配置指南(仅供参考)
  • WPS 搭配 Zotero 插件使用
  • 蓝桥杯 再创新高【省模拟赛】
  • 前端组件封装艺术:设计原则与最佳实践指南
  • c语言经典基础编程题
  • 【免费】2008-2020年各省城镇登记失业率数据
  • 总结 HTTPS 的加密流程
  • 【栈数据结构应用解析:常见算法题详细解答】—— Leetcode
  • 计算机网络——路由器
  • 用 Vue 3.5 TypeScript 重新开发3年前甘特图的核心组件
  • HTML5 Web SQL
  • 我的创作纪念日 打造高效 Python 日记本应用:从基础搭建到功能优化全解析
  • Java EE Web环境安装
  • MCU详解:嵌入式系统的“智慧之心”
  • 【Prometheus】prometheus监控pod资源,ingress,service资源以及如何通过annotations实现自动化监控