当前位置: 首页 > 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;承上…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...