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

代码随想录刷题 | Day2

今日学习目标

一、基础

  • 链表

接下来说一说链表的定义。

链表节点的定义,很多同学在面试的时候都写不好。

这是因为平时在刷leetcode的时候,链表的节点都默认定义好了,直接用就行了,所以同学们都没有注意到链表的节点是如何定义的。

而在面试的时候,一旦要自己手写链表,就写的错漏百出。

这里我给出C/C++的定义链表节点方式,如下所示:

// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

 有同学说了,我不定义构造函数行不行,答案是可以的,C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量,下面我来举两个例子:  

通过自己定义构造函数初始化节点:

ListNode* head = new ListNode(5);

 使用默认构造函数初始化节点:

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话,在初始化的时候就不能直接给变量赋值!

二、算法

 1. 203. 移除链表元素

/*** 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* removeElements(ListNode* head, int val) {while (head != NULL && head->val == val) {ListNode* p = head;head = head->next;delete p;}ListNode* cur = head;while (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {ListNode* p = cur->next;cur->next = cur->next->next;delete p;} else {cur = cur->next;}}return head;}
};

2. 707.设计链表

#include <bits/stdc++.h>
using namespace std;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) {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大于链表的长度,则返回空// 如果index小于0,则在头部插入节点void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点,如果index 大于等于链表的长度,直接return,注意index是从0开始的void 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;//delete命令指示释放了tmp指针原本所指的那部分内存,//被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp,会指向难以预想的内存空间tmp=nullptr;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;};

3. 206.反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == NULL)return head;ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点dummyHead->next = head; // 将虚拟头结点指向head,这样方便后面做删除操作ListNode* p = dummyHead->next;ListNode* q;dummyHead->next = NULL;while (p != NULL) {q = p;p = p->next;q->next = dummyHead->next;dummyHead->next = q;}return dummyHead->next;}
};

4. 24. 两两交换链表中的节点

#include <iostream>
#include <bits/stdc++.h>
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) {}
};
int main(){return 0;
}
ListNode* swapPairs(ListNode* head) {if (head==NULL || head->next==NULL) {return head;}ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *cur  = dummyHead;ListNode *p,*q;while (cur->next!=nullptr &&cur->next->next!=nullptr) {p = cur->next;q = cur->next->next->next;cur->next = p->next;cur->next->next = p;cur->next->next->next = q;cur = cur->next->next;}return dummyHead->next;
}

5. 19.删除链表的倒数第N个节点

#include <bits/stdc++.h>
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) {}
};
int main(){return 0;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {if(head==NULL) return NULL;ListNode *dummyNode = new ListNode();dummyNode->next = head;ListNode *p,*q;p=q=dummyNode;while (n--&&p!=nullptr) {p=p->next;}p=p->next;while(p!=nullptr&&q!=nullptr){p=p->next;q=q->next;}ListNode *temp = q->next;q->next = q->next->next;delete temp;return dummyNode->next;
}

6. 面试题 02.07. 链表相交

#include <bits/stdc++.h>
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) {}
};
int main(){return 0;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int aLen = 0;int bLen = 0;ListNode *pa = headA;ListNode *pb = headB;while(pa!=nullptr){aLen++;pa = pa->next;}while(pb!=nullptr){bLen++;pb = pb->next;}int k;pa = headA;pb = headB;if(aLen<=bLen){k = bLen - aLen;while (k-- && pb!=nullptr) {pb = pb->next;}while(pb!=nullptr){if(pa==pb){return pb;}pa = pa->next;pb = pb->next;}}else{k = aLen - bLen;while (k-- && pa!=nullptr) {pa = pa->next;}while(pa!=nullptr){if(pa==pb){return pa;}pa = pa->next;pb = pb->next;}}return NULL;
}

相关文章:

代码随想录刷题 | Day2

今日学习目标 一、基础 链表 接下来说一说链表的定义。 链表节点的定义&#xff0c;很多同学在面试的时候都写不好。 这是因为平时在刷leetcode的时候&#xff0c;链表的节点都默认定义好了&#xff0c;直接用就行了&#xff0c;所以同学们都没有注意到链表的节点是如何定…...

C++ enum class 如何使用

enum class 是 C11 引入的一种新的枚举类型&#xff0c;它是对传统 C 风格的枚举的一种改进。enum class 提供了更强大的类型安全性和作用域限定。以下是关于 enum class 的详细介绍和用法说明&#xff1a; 1. 基本语法 enum class EnumName {Enumerator1,Enumerator2,// ...…...

攻防技术-单包攻击防范:扫描、畸形、特殊(HCIP)

单包攻击类型介绍 一、扫描窥探攻击 1、地址扫描攻击防范 攻击介绍 运用ping程序探测目标地址&#xff0c;确定目标系统是否存活。也可使用TCP/UDP报文对目标系统发起探测&#xff08;如TCP ping&#xff09;。 防御方法 检测进入防火墙的ICMP、TCP和UDP报文&#xff0c;根…...

基于 Vue3 和 WebSocket 实现的简单网页聊天应用

首先附上项目介绍,后面详细解释技术细节 1. chat-websocket 一个基于Vue3和WebSocket的简易网络聊天室项目&#xff0c;包括服务端和客户端部分。 项目地址 websocket-chat 下面是项目的主要组成部分和功能&#xff1a; 项目结构 chat-websocket/ |-- server/ # WebSocket 服…...

【MYSQL】MYSQL 的学习教程(八)之 12 种慢 SQL 查询原因

日常开发中&#xff0c;我们经常会遇到数据库慢查询。那么导致数据慢查询都有哪些常见的原因呢&#xff1f;今天就跟大家聊聊导致 MySQL 慢查询的 12 个常见原因&#xff0c;以及对应的解决方法&#xff1a; SQL 没加索引SQL 索引失效limit 深分页问题单表数据量太大join 或者…...

C语言例题3

1.设x、y、z和k都是int型变量&#xff0c;则执行表达式&#xff1a;x&#xff08;y4&#xff0c;z16&#xff0c;k32&#xff09;后&#xff0c;x的值为&#xff08;32&#xff09;&#xff1b; x(y4,z16,k32),x的值为32 理解逗号运算符在c语言中的工作方式&#xff1a;逗号运算…...

很实用的ChatGPT网站——httpchat-zh.com

很实用的ChatGPT网站——http://chat-zh.com/ 今天介绍一个好兄弟开发的ChatGPT网站&#xff0c;网址[http://chat-zh.com/]。这个网站功能模块很多&#xff0c;包含生活、美食、学习、医疗、法律、经济等很多方面。下面简单介绍一些部分功能与大家一起分享。 登录和注册页面…...

Python函数中的*args,**kwargs作用与用法

前言 最近在使用Python函数的时候&#xff0c;经常碰见函数中使用*args、**kwargs&#xff0c;而且参数的传递也是非常奇特&#xff0c;就特意对Python函数中*args、**kwargs进行了查询&#xff0c;下面就以实例进行说明。 1 Python中的*args、**kwargs 在 Python 中&#x…...

python可视化界面自动生成,python如何做可视化界面

大家好&#xff0c;小编来为大家解答以下问题&#xff0c;python gui可视化操作界面制作&#xff0c;python做出的炫酷的可视化&#xff0c;现在让我们一起来看看吧&#xff01; 目录 前言 一.环境配置 插件&#xff1a; 1.python 2.Chinese 3.Open In Default Browser 安装pyt…...

力扣热题100道-双指针篇

文章目录 双指针283.移动零11.盛最多水的容器15.三数之和42.接雨水 双指针 283.移动零 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 …...

数据库一般会采取什么样的优化方法?

数据库一般会采取什么样的优化方法&#xff1f; 1、选取适合的字段属性 为了获取更好的性能&#xff0c;可以将表中的字段宽度设得尽可能小。 尽量把字段设置成not null 执行查询的时候&#xff0c;数据库不用去比较null值。 对某些省份或者性别字段&#xff0c;将他们定义为e…...

编程笔记 html5cssjs 015 HTML列表

编程笔记 html5&css&js 015 HTML列表 一、有序列表例1&#xff1a;例2&#xff1a; 二、无序列表例1&#xff1a;例2&#xff1a; 列表是一种特定文字格式&#xff0c;很常用。 HTML 列表。HTML 支持有序、无序和定义列表。 一、有序列表 例1&#xff1a; <!DOCTY…...

【力扣题解】P404-左叶子之和-Java题解

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【力扣题解】 文章目录 【力扣题解】P404-左叶子之和-Java题解&#x1f30f;题目描述&#x1f4a1;题解&#x1f30f;总结…...

elasticsearch 索引数据多了怎么办,如何调优,部署

当Elasticsearch索引的数据量增加时&#xff0c;可能会遇到性能瓶颈&#xff0c;需要进行调优。以下是一些建议和步骤&#xff0c;可帮助你处理数据量增加的情况&#xff1a; 1. 硬件升级&#xff1a; 增加节点数或升级硬件&#xff0c;包括更快的CPU、更大的内存和更快的存储…...

Spring Cloud Gateway之Predicate断言详解

目录 Predicate&#xff08;断言&#xff09;内置Predicate请求参数匹配请求路径匹配Header 属性匹配Cookie 匹配请求方式匹配请求 ip 地址匹配时间匹配组合匹配 Predicate&#xff08;断言&#xff09; 在 Spring Cloud Gateway 中&#xff0c;Predicate&#xff08;断言&…...

JavaScript中的prototype和_proto_的关系是什么

JavaScript中的prototype和_proto_的关系是什么 __proto__ 是 JavaScript 中对象的一个内部属性&#xff0c;它指向该对象的原型。JavaScript 中每个对象都有一个 __proto__ 属性&#xff0c;通过它可以访问对象的原型。prototype 是函数对象特有的属性&#xff0c;每个函数都…...

机器学习(二) -- 数据预处理(3)

系列文章目录 未完待续…… 目录 前言 tips&#xff1a;这里只是总结&#xff0c;不是教程哈。本章开始会用到numpy&#xff0c;pandas以及matplotlib&#xff0c;这些就不在这讲了哈。 “***”开头的是给好奇心重的宝宝看的&#xff0c;其实不太重要可以跳过。 此处以下所有…...

【数学建模美赛M奖速成系列】Matplotlib绘图技巧(三)

Matplotlib绘图技巧&#xff08;三&#xff09; 写在前面7. 雷达图7.1 圆形雷达图7.2 多边形雷达图 8. 极坐标图 subplot9. 折线图 plot10. 灰度图 meshgrid11. 热力图11.1 自定义colormap 12. 箱线图 boxplot 写在前面 终于更新完Matplotlib绘图技巧的全部内容&#xff0c;有…...

手写Spring与基本原理--简易版

文章目录 手写Spring与基本原理解析简介写一个简单的Bean加载容器定义一个抽象所有类的BeanDefinition定义一个工厂存储所有的类测试 实现Bean的注册定义和获取基于Cglib实现含构造函数的类实例化策略Bean对象注入属性和依赖Bean的功能Spring.xml解析和注册Bean对象实现应用上下…...

EasyNTS端口穿透服务新版本发布 0.8.7 增加隧道流量总数记录,可以知晓设备哪个端口耗费流量了

EasyNTS上云平台可通过远程访问内网应用&#xff0c;包含网络桥接、云端运维、视频直播等功能&#xff0c;极大地解决了现场无固定IP、端口不开放、系统权限不开放等问题。平台可提供一站式上云服务&#xff0c;提供直播上云、设备上云、业务上云、运维上云服务&#xff0c;承上…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...

Spring AI中使用ChatMemory实现会话记忆功能

文章目录 1、需求2、ChatMemory中消息的存储位置3、实现步骤1、引入依赖2、配置Spring AI3、配置chatmemory4、java层传递conversaionId 4、验证5、完整代码6、参考文档 1、需求 我们知道大型语言模型 &#xff08;LLM&#xff09; 是无状态的&#xff0c;这就意味着他们不会保…...

TMC2226超静音步进电机驱动控制模块

目前已经使用TMC2226量产超过20K,发现在静音方面做的还是很不错。 一、TMC2226管脚定义说明 二、原理图及下载地址 一、TMC2226管脚定义说明 引脚编号类型功能OB11电机线圈 B 输出 1BRB2线圈 B 的检测电阻连接端。将检测电阻靠近该引脚连接到地。使用内部检测电阻时,将此引…...

Nginx 事件驱动理解

在做埋点采集服务的过程中&#xff0c;主要依靠openresty加lua脚本来实现采集。高并发还是主要依靠nginx来实现。而其核心就是事件驱动/多路io复用&#xff08;epoll机制&#xff09;&#xff0c;不同的linux服务器都有对应的实现方式。 而epoll机制就是&#xff0c;应用启动的…...