C++刷题笔记(6)——leetcode203、707、206

2024-02-02 19:32

本文主要是介绍C++刷题笔记(6)——leetcode203、707、206,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链表理论基础

1.list容器
2.关于链表,你该了解这些!
3.C++ list(STL list)容器完全攻略

题目1:203.移除链表元素

在这里插入图片描述
解题思路:
以链表 1 4 2 4 来举例,移除元素4。
在这里插入图片描述
但是如果删除的是头节点,移除头结点和移除其他节点的操作是不一样的,因为链表的其他节点都是通过前一个节点来移除当前节点,而头结点没有前一个节点,因此需要用新的方法:

解法一:设置一个虚拟头结点在进行删除操作

在这里插入图片描述
给链表添加一个虚拟头结点为新的头结点,移除这个旧头结点元素1。

在C++中还要从内存中删除移除后的节点

 class Solution {public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);         // 初始化一个空节点,初始值为0,指针指向dummyheaddummyHead->next = head;                        // 将虚拟头结点指向head   上面两句也可以写成:ListNode* dummyHead = new ListNode(0,head)ListNode* cur = dummyHead;                     // 定义一个临时指针,等于虚拟头节点,用来代替虚拟头节点遍历链表(如果用虚拟头节点遍历链表,其值会不停变化,最后不好确定返回值)while (cur->next != NULL) {                    // 临时指针的下一个节点不为空if (cur->next->val == val) {               // 当指针的下一个节点的值等于目标值ListNode* tmp = cur->next;             //定义一个指针指向临时指针指向的节点(可以不写)cur->next = cur->next->next;           // 指针指向下下个值delete tmp;                            // 删除 cur->next}else {cur = cur->next;                       // 指针向后移动遍历指针}}head = dummyHead->next;                        // 重新定义头节点delete dummyHead;                              // 对虚拟头节点进的空间进行释放,防止内存泄漏return head;}};

解法二:直接使用原来的链表来进行删除操作

在这里插入图片描述
要将头结点向后移动一位
在这里插入图片描述
将原头结点从内存中删掉
在这里插入图片描述

 class Solution {public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点,注意这里不是if,因为可能新的头节点指向的值也等于目标值while (head != NULL && head->val == val) { // 头节点不为空且头节点指向的值等于目标值ListNode* tmp = head;                  //定义一个指针指向临时指针指向的节点head = head->next;                     //使 头节点 指向 头节点的下一个delete tmp;                            //清理节点内存}// 删除非头结点ListNode* cur = head;                     //定义一个临时指针指向头节点while (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {          //临时指针指向的节点的值 等于 目标值ListNode* tmp = cur->next;        //定义一个指针指向临时指针指向的节点(即要删除的节点)cur->next = cur->next->next;      //临时指针指向的节点 指向 目前临时指针指向的节点的下一个节点delete tmp;                       //清理节点内存}else {cur = cur->next;                  //没找到目标值,临时指针后移}}return head;}};

解法三:双指针法

评论区大佬给出了五种解法:移除链表元素(五种方法)
这里再记录一种双指针法,这位up也讲解的非常清晰:203.移除链表元素

题目2:707.设计链表

在这里插入图片描述

解法一:单链表

解题思路:
起始这一题看着很长,但主要还是那几行代码的堆叠,只要把那几行代码理解了就不难

以addAtIndex(index,val)为例:
假设链表为1->3->5->7->9,现在要在第2个节点之前插入一个新节点(addAtIndex(2,4))
在这里插入图片描述
那么首先新定义一个节点并赋值,然后将定义虚拟头节点指针
在这里插入图片描述
然后开始遍历index之前的链表:
在这里插入图片描述
然后执行newNode->next = cur->next;
在这里插入图片描述
执行cur->next = newNode;size++;
在这里插入图片描述
其他几种和这个也是差不多的
代码不难,但是要注意定义的临时指针cur什么时候指向虚拟头节点dummyhead、什么时候指向虚拟头节点的下一个节点dummyhead->next

 class MyLinkedList {public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val) :val(val), next(nullptr) {}  //构造函数};// 初始化链表MyLinkedList() {dummyHead = new LinkedNode(0);                   //定义虚拟头结点size = 0;                                        //链表长度}// 获取到第index个节点数值,如果index是非法数值直接返回-1, 注意index是从0开始的,第0个节点就是头结点int get(int index) {if (index > (size - 1) || index < 0) {           //输入的index不在范围内return -1;}LinkedNode* cur = dummyHead->next;               //当前指针指向真正头节点while (index--) {                                //遍历index前面的链表cur = cur->next;}return cur->val;}// 在链表最前面插入一个节点,插入完成后,新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);      //新建节点并赋值newNode->next = dummyHead->next;                //将虚拟头节点的指向赋值给新建节点的指向(即使新建节点的指向与虚拟头节点相同)dummyHead->next = newNode;                      //将虚拟头节点指向新建节点size++;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummyHead;                   //从虚拟头节点开始,防止一开始是空链表while (cur->next != nullptr) {                 //遍历链表到最后位置cur = cur->next;}cur->next = newNode;                           //链表最后面添加一个节点size++;}//在第index个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。//如果index 等于链表的长度,则说明是新插入的节点为链表的尾结点//如果index大于链表的长度,则返回空//void addAtIndex(int index, int val) {//    if (index <= 0) {//        addAtHead(val);//    }//    else if (index == size) {//        addAtTail(val);//    }//    else if (index > size) {//        return;//    }//    else {//        LinkedNode* newNode = new LinkedNode(val);//        LinkedNode* cur = dummyHead;//        while (index--) {//            cur = cur->next;//        }//        newNode->next = cur->next;//        cur->next = newNode;//        size++;//    }//}void addAtIndex(int index, int val) {if (index > size) {                            //大于链表长度返回空return;}     LinkedNode* newNode = new LinkedNode(val);     //包含了等于链表长度的情况LinkedNode* cur = dummyHead;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size++;}// 删除第index个节点,如果index 大于等于链表的长度,直接returnvoid deleteAtIndex(int index) {if (index >= size || index < 0) {return;}LinkedNode* cur = dummyHead;while (index--) {cur = cur->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;size--;}// 打印链表void printLinkedList() {LinkedNode* cur = dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}private:int size;LinkedNode* dummyHead;};

解法二:双链表

class ListsNode
{
public:int val;ListsNode* next;ListsNode* pre;ListsNode(int v, ListsNode* n, ListsNode* p):val(v),next(n),pre(p){}
};class MyLinkedList {
public:ListsNode* root;ListsNode* trail;int size;/** Initialize your data structure here. */MyLinkedList() {root=nullptr;trail=nullptr;size=0;}/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */int get(int index) {int temp=0;ListsNode* cur=root;while(cur!=nullptr){if(temp==index){return cur->val;}cur=cur->next;temp++;}return -1;}/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */void addAtHead(int val) {if(root!=nullptr){ListsNode* newNode=new ListsNode(val, root, nullptr);root->pre=newNode;root=newNode;         }else{root=new ListsNode(val, nullptr,nullptr);trail=root;}size++;}/** Append a node of value val to the last element of the linked list. */void addAtTail(int val) {if(trail!=nullptr){ListsNode* newNode = new ListsNode(val, nullptr, trail);trail->next=newNode;trail=newNode;}else{trail=new ListsNode(val, nullptr, nullptr);root=trail;}size++;}/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */void addAtIndex(int index, int val) {if(index<=0){addAtHead(val);return;}if(index==size){addAtTail(val);return;}int temp=0;ListsNode* pre=nullptr;ListsNode* cur=root;while(cur!=nullptr){if(temp==index){ListsNode* newNode=new ListsNode(val, cur, pre);if(pre!=nullptr){pre->next=newNode;}cur->pre=newNode;size++;return;}pre=cur;cur=cur->next;temp++;}}/** Delete the index-th node in the linked list, if the index is valid. */void deleteAtIndex(int index) {int temp=0;ListsNode* pre=nullptr;ListsNode* cur=root;if(index==0){ListsNode* old=root;root=root->next;if(root!=nullptr){root->pre=nullptr;}delete old;size--;return;}if(index==size-1){ListsNode* old=trail;trail=trail->pre;if(trail!=nullptr){trail->next=nullptr;}delete old;size--;return ;}while(cur!=nullptr){if(temp==index){ListsNode* old=cur;if(pre!=nullptr){pre->next=cur->next;}if(cur->next!=nullptr){cur->next->pre=pre;}delete old;size--;return;}pre=cur;cur=cur->next;temp++;}}
};

题目3:206.反转链表

在这里插入图片描述

解法一:双指针法

解题思路:
只需要将链表的next指针的指向翻转
在这里插入图片描述
定义两个指针,cur指针指向头节点、pre指针指向null空指针;
然后将cur->next指向pre,移动两个指针;
当cur指向null,翻转结束。

 class Solution {public:ListNode* reverseList(ListNode* head) {ListNode* temp;                        // 保存cur的下一个节点ListNode* cur = head;                  // cur指针指向头节点ListNode* pre = NULL;                  // pre指针指向nullwhile (cur) {                          // 遍历链表temp = cur->next;                  // 保存cur的下一个节点,因为接下来要改变cur->nextcur->next = pre;                   // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}};

解法二:递归法

和双指针法的思路差不多

 class Solution {public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur == NULL) return pre;ListNode* temp = cur->next;cur->next = pre;// 可以和双指针法的代码进行对比,如下递归的写法,其实就是做了这两步// pre = cur;// cur = temp;return reverse(cur, temp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur = head;// ListNode* pre = NULL;return reverse(NULL, head);}};

这篇关于C++刷题笔记(6)——leetcode203、707、206的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/671730

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现