hot100 -- 链表(中)
不要觉得力扣核心代码模式麻烦,它确实比不上ACM模式舒服,可以自己处理输入输出
只是你对 链表 和 return 的理解不到位
👂 ▶ 屿前世 (163.com)
👂 ▶ see you tomorrow (163.com)
目录
🎂两数相加
🚩删除链表倒数第 N 个节点
AC 双指针
AC 栈
AC 计算链表长度
🌼两两交换链表中的节点
AC 递归
AC 迭代
🌼K 个一组翻转链表
🎂两数相加
2. 两数相加 - 力扣(LeetCode)
1)l1, l2 长度可能不一样,假设短的后面全是 0,通过三目运算符得到 当前节点的值,比如
n1 = l1 ? l1->val : 0
2)sum = n1 + n2 + 进位,%10 当前位,/10 进位
3)注意给节点赋值方式
tail->next = new ListNode(...);
4)可能漏最后一次进位,while() 结束后还要来一次
时间 O(max(m, n)),空间 O(1)
/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head = nullptr, *tail = nullptr;int temp = 0; // 进位while (l1 || l2) {int n1 = l1 ? l1->val : 0; // l1 的值int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + temp;if (!head) // 第1次head = tail = new ListNode(sum % 10); // 注意赋值方式else {// tail 上一步已经初始化, 所以现在是 tail->nexttail->next = new ListNode(sum % 10); // 先给下一赋值tail = tail->next; // 再移动}temp = sum / 10; // 进位// l1, l2 向后移动if (l1) l1 = l1->next;if (l2) l2 = l2->next;}// 最后一次进位if (temp) tail->next = new ListNode(temp);return head; // 不返回 tail, 防止 nullptr}
};
🚩删除链表倒数第 N 个节点
19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
注意:链表的题,如果出现 Node->next,那么这个 Node 一定不为 nullptr,否则会报错
1,双指针:一前一后,前面的先移动 n 个位置,然后开始同步移动
2,栈:思路类似双指针,最终都是遍历到待删除节点前一个(从栈顶开始出栈)
3,链表长度:思路类似前面,借助哑节点,避免对删除头节点的处理,遍历两次即可
AC 双指针
时间 O(L),空间 O(1),L 链表长度
自己写的
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode *fast = head, *slow = head;// 前后指针 -- 找到倒数第 n 个节点, 即 slowwhile (n--)fast = fast->next;// 删除头节点if (!fast) {ListNode *temp = head;head = temp->next;delete temp;return head;}while (fast->next)slow = slow->next, fast = fast->next;// 删除 slow 下一节点ListNode *bad = slow->next; // 要删除的节点slow->next = slow->next->next;bad->next = nullptr;delete bad;// 上面处理了头节点被删除的情况,所以这里可以 return headreturn head; }
};
官解重写
删除倒数第 n 个节点,通过指针的 next 来操作,最后的 delete 只是为了手动释放堆区数据(自己new的自己delete)
bad 的作用是,防止删的是第一个元素,因为最终会遍历到删除节点的前一个
如果不用 bad,就像前面的代码一样,特殊处理删除节点是头节点的情况
/*** 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* removeNthFromEnd(ListNode* head, int n) {// 初始化 head 上一位置, bad->next = headListNode *bad = new ListNode(0, head); ListNode *fast = head, *slow = bad; // slow 初始化为 badwhile (n--)fast = fast->next;while (fast) {fast = fast->next;slow = slow->next;}// 此时 slow 位于删除节点 上一位置slow->next = slow->next->next; // 更新连接ListNode *ans = bad->next; // 新的头节点delete bad;return ans; // 返回新的头节点}
};
AC 栈
/*** 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* removeNthFromEnd(ListNode* head, int n) {stack<ListNode *> s;// temp 的作用是,防止删的是第一个元素,因为最终会遍历到删除节点的前一个ListNode *temp = new ListNode(0, head);ListNode *cur = temp;// 链表节点全部入栈while (cur) {s.push(cur); // push_back 是 vectorcur = cur->next;}// 弹出 n 个元素后,栈顶就是待删除节点前一个while (n--) s.pop();ListNode *prev = s.top(); prev->next = prev->next->next; // 先重新连接ListNode *ans = temp->next; // 再赋值新的头节点delete temp;return ans;}
};
AC 计算链表长度
同样,类似上面两种,通过头节点前的,哑节点,避免对删除头节点这种情况的处理
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode *temp = new ListNode(0, head); // 哑节点,避免对头节点删除的处理ListNode *cur = temp;int len = 0;// 链表长度while (cur->next) { // 长度容易错len++;cur = cur->next;}cur = temp;int count = len - n;// 哑节点移动 len - n + 1,即待删除节点// 所以,移动 len - n,刚好待删除前一个while (count--) cur = cur->next;cur->next = cur->next->next;ListNode *ans = temp->next; // 新的头节点delete temp;return ans;}
};
🌼两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣(LeetCode)
AC 递归
head之前的不用处理,举个例子,比如
转换后 head = swapPairs(temp->next),把两两视作一个整体,那么两两中的后一个,指向哪里,取决于后面递归的结果,所以只需考虑当前层
时间 O(n),空间 O(n)(递归栈深度 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:// head 表示递归时,当前两两交换节点的前一个ListNode* swapPairs(ListNode* head) {// 递归出口if (head == nullptr || head->next == nullptr)return head; // 只剩0个 或 1个节点// 只看当前层:交换两个节点ListNode *temp = head->next; head->next = swapPairs(temp->next); // 递归交换剩余节点temp->next = head;return temp; // 返回新的头节点}
};
AC 迭代
类似冒泡排序,直接交换,但是需要借助哑节点 temp,比如
temp->Node1->Node2
👇
temp->Node2->Node1
时间 O(n),空间 O(1)
/*** 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* swapPairs(ListNode* head) {ListNode *temp = new ListNode(0, head); // 初始 temp->next == headListNode *tempHead = temp; // 头节点前一个// 递归中的 head 是当前节点// 迭代中的 head 只表示原链表头节点// 所以 while 中不能用 head, 应该用 tempwhile (temp->next != nullptr && temp->next->next != nullptr) {ListNode *Node1 = temp->next;ListNode *Node2 = temp->next->next;// temp->Node1->Node2 ----> temp->Node2->Node1temp->next = Node2;Node1->next = Node2->next;Node2->next = Node1;// 新的哑节点temp = Node1;}ListNode *ans = tempHead->next; // 新链表头节点// delete tempHead; // 删除哑节点return ans; // 新的头节点}
};
🌼K 个一组翻转链表
25. K 个一组翻转链表 - 力扣(LeetCode)
模拟:迭代反转 + 新建连接
以下是新建连接的 3 个步骤
k = 3 也一样
和上/下一组新建连接时,要从外层开始,就是p0->next->next到p0->next最后才是p0
p0->next->next = cur; // 下一组头 p0->next = nex; // 上一组尾 p0 = p1; // 更新p0
时间 O(n),空间 O(1)
/*** 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* reverseKGroup(ListNode* head, int k) {// 链表长度 lenint len = 0;for (ListNode *cur = head; cur; cur = cur->next)len++;// temp->next == head(temp/p0 -- 哑节点/哨兵节点)ListNode *temp = new ListNode(0, head);ListNode *p0 = temp; // p0 k个一组第一个节点的前一个ListNode *nex = nullptr, *cur = head;// k 个一组反转for (; len >= k; len -= k) {// 迭代 -- 反转(参考反转链表I)// 因为哨兵节点的存在,所以是 k 次而不是 k-1 次反转for (int i = 0; i < k; ++i) { // k 次反转ListNode *pre = cur->next; // pre 右移cur->next = nex; // 反转nex = cur; // nex 右移cur = pre; // cur 右移}// 当前组 与 上一组尾&&下一组头 连接ListNode *p1 = p0->next; // 新的p0p0->next->next = cur; // 下一组头p0->next = nex; // 上一组尾p0 = p1; // 更新p0}return temp->next; // 返回新链表的头节点}
};
相关文章:
hot100 -- 链表(中)
不要觉得力扣核心代码模式麻烦,它确实比不上ACM模式舒服,可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 👂 ▶ 屿前世 (163.com) 👂 ▶ see you tomorrow (163.com) 目录 🎂两数相加 🚩删…...
数据结构面试常见问题
数据结构是计算机科学中非常重要的一部分,也是面试中经常被考察的内容。以下是一些在数据结构面试中常见的问题: 1. 数组 (Array): 描述数组和链表的区别。如何在数组中实现循环队列?给定一个数组,如何找到两个数的和等于给定值…...
蓝桥杯2024年第十五届省赛真题-R 格式(高精度乘法 + 加法)
本题链接:蓝桥杯2024年第十五届省赛真题-R 格式 - C语言网 题目: 样例: 输入 2 3.14 输出 13 思路: 根据题意,结合数据范围,这是一道模板的高精度乘以低精度问题。 题意是double 类型 d 与…...
普通人做抖音小店真的能赚钱吗?可以,但更取决于个人
大家好,我是电商花花。 现在做抖音小店的基本上都是一些新商家,对于我们众多零基础的朋友来说,是期待也是一份挑战。 抖音小店作为一个充满机会的新兴平台,许多人都欣喜的投入其中,期望能够借此来改变自己的命运&…...
基于单链表实现通讯管理系统!(有完整源码!)
个人主页:秋风起,再归来~ 文章专栏:C语言实战项目 个人格言:悟已往之不谏,知来者犹可追 克心守己,律己则安! 1、前言 友友们,这篇文章是基于单链…...
MATLAB入门介绍
MATLAB是由MathWorks公司开发的一款专业的数学计算软件,主要用于算法开发、数据可视化、数据分析以及数值计算等领域。它提供了一个易于使用的环境,让用户可以通过矩阵计算、函数和数据绘图、用户界面的创建以及编程和文档编写来解决各种数学问题。 MATL…...
【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations)
【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations) 1、污点(Taints)2、容忍度(Tolerations)3、示例演示-测试污点的具体应用场景3.1 给节点打污点&…...
Angular 使用DomSanitizer防范跨站脚本攻击
跨站脚本Cross-site scripting 简称XSS,是代码注入的一种,是一种网站应用程序的安全漏洞攻击。它允许恶意用户将代码注入到网页上,其他用户在使用网页时就会收到影响,这类攻击通常包含了HTML和用户端脚本语言(JS&…...
(八)PostgreSQL的数据库管理
PostgreSQL的数据库管理 基础信息 OS版本:Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本:16.2 pg软件目录:/home/pg16/soft pg数据目录:/home/pg16/data 端口:57771 创建数据库 CREATE DATABASE创建一…...
外包干了30天,技术倒退明显
先说情况,大专毕业,18年通过校招进入湖南某软件公司,干了接近6年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能…...
ruoyi-nbcio-plus基于vue3的flowable的自定义业务单表例子的升级修改
更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码: https://gitee.com/nbacheng/ruoyi-nbcio 演示地址:RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码:…...
【ENSP】华为三层交换机配置AAA认证,开启telnet服务
配置步骤 1.给交换机配置ip地址,以便登陆 2.配置AAA,用户名,密码,服务类型,用户权限 3.配置接入设备的数量 4.开启telnet服务 LSW2交换机配置 u t m #关闭提示 sys …...
collections模块下的Counter函数讲解
📚博客主页:knighthood2001 ✨公众号:认知up吧 (目前正在带领大家一起提升认知,感兴趣可以来围观一下) 🎃知识星球:【认知up吧|成长|副业】介绍 ❤️感谢大家点赞👍&…...
HarmonyOS开发实例:【分布式邮件】
概述 基于TS扩展的声明式开发范式编程语言编写的一个分布式邮件系统,可以由一台设备拉起另一台设备,每次改动邮件内容,都会同步更新两台设备的信息。效果图如下: 搭建OpenHarmony开发环境 完成本篇Codelab我们首先要完成开发环境…...
llama2.c与chinese-baby-llama2语言模型本地部署推理
文章目录 简介Github文档克隆源码英文模型编译运行中文模型(280M)main函数 简介 llama2.c是一个极简的Llama 2 LLM全栈工具,使用一个简单的 700 行 C 文件 ( run.c ) 对其进行推理。llama2.c涉及LLM微调、模型构建、推理端末部署(…...
008、Python+fastapi,第一个后台管理项目走向第8步:ubutun 20.04下安装vscode+python环境配置
一、说明 白飘了3个月无影云电脑,开始选了个windows server 非常不好用,后台改为ubuntu想升级到22,没成功,那就20.04吧。 今天先安装下开发环境,后续2个月就想把他当做开发服务器,不知道行不行,…...
2024.4.16 驱动开发
思维导图...
如何在 Ubuntu 14.04 上更改 PHP 设置
简介 PHP 是一种服务器端脚本语言,被许多流行的 CMS 和博客平台如 WordPress 和 Drupal 所使用。它也是流行的 LAMP 和 LEMP 堆栈的一部分。更新 PHP 配置设置是设置基于 PHP 的网站时的常见任务。定位确切的 PHP 配置文件可能并不容易。通常在服务器上会有多个 PH…...
【光伏企业】光伏项目怎么做才能提高效率?
一、精细化项目管理 项目规划:在项目启动前,进行充分的调研和规划,明确项目的目标、规模、预算和时间表,确保各项资源得到合理分配。 团队建设:组建一支高效、专业的项目团队,确保团队成员具备光伏领域的…...
毕设选51还是stm32?51太简单?
如果你更倾向于挑战和深入学习,STM32可能是更好的选择。如果你希望更专注于底层硬件原理,51可能更适合。我这里有一套嵌入式入门教程,不仅包含了详细的视频讲解,项目实战。如果你渴望学习嵌入式,不妨点个关注ÿ…...
ip addr和ifconfig区别
ip addr和ifconfig都是用于配置和管理网络接口的工具 1. ifconfig ifconfig是较旧的网络配置工具,属于net-tools套件的一部分。 该命令主要用于配置、显示和控制网络接口的参数,如IP地址、子网掩码、广播地址等。 ifconfig命令的功能相对有限ÿ…...
Springboot+Vue项目-基于Java+MySQL的房产销售系统(附源码+演示视频+LW)
大家好!我是程序猿老A,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:Java毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计 &…...
向量数据库中的向量是什么?
在向量数据库中,向量通常指的是高维空间中的点或方向,它们由一组数值组成,这些数值表示该点在空间中的位置或方向。在机器学习和人工智能领域,向量经常用于表示各种类型的数据,如文本、图像、音频等。 具体来说&#x…...
【重回王座】ChatGPT发布最新模型gpt-4-turbo-2024-04-09
今天,新版GPT-4 Turbo再次在大型模型排行榜上荣登榜首,成功超越了此前领先的Claude 3 Opus。另外,新模型在处理长达64k的上下文时,性能竟能够与旧版在处理26k上下文时的表现相当。 目前GPT-4 Turbo仅限于ChatGPT Plus的用户&…...
NL2SQL基础系列(1):业界顶尖排行榜、权威测评数据集及LLM大模型(Spider vs BIRD)全面对比优劣分析[Text2SQL、Text2DSL]
NL2SQL基础系列(1):业界顶尖排行榜、权威测评数据集及LLM大模型(Spider vs BIRD)全面对比优劣分析[Text2SQL、Text2DSL] Text-to-SQL(或者Text2SQL),顾名思义就是把文本转化为SQL语言,更学术一…...
深度学习基础——计算量、参数量和推理时间
深度学习基础——计算量、参数量和推理时间 在深度学习中,计算量、参数量和推理时间是评估模型性能和效率的重要指标。本文将介绍这三个指标的定义、计算方法以及如何使用Python进行实现和可视化展示,以帮助读者更好地理解和评估深度学习模型。 1. 定义…...
另一棵树的子树
目录 题目 思路 代码1 :相同的树 代码二:解题 注意点 题目 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。 二叉树 tr…...
【hive】单节点搭建hadoop和hive
一、背景 需要使用hive远程debug,尝试使用无hadoop部署hive方式一直失败,无果,还是使用有hadoop方式。最终查看linux内存占用6GB,还在后台运行docker的mysql(bitnami/mysql:8.0),基本满意。 版本选择: &a…...
Aurora 协议学习理解与应用——Aurora 8B10B协议学习
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 Aurora 8B10B协议学习之一,理解协议 概述8B10B数据发送和接收Symbol-Pairs传输调度用户PDU传输过程用户PDU接收过程 流控自然流量控制操作自然流量控制延迟自然流…...
Vue基础使用之V-Model绑定单选、复选、动态渲染选项的值
这里要说明一下,在v-model 绑定的值是id还是value是和<option>中的v-bind保持一致的,如第四个,如果是 <option :value"op[1]" 那v-model绑定的就是数组第二项的值2,4,6 如果是 <option :va…...
室内装修网站模板/朋友圈推广
//这里简单介绍一下Java的Comparable内部比较器和Comparator外部比较器的用法实现//那么我们来做一个关于对象间的排序,首先建一个Model或者叫JavaBen。如下://1.Java的Comparable内部比较器的用法实现://Comparable内部比较器(要让实体类JavaBen(TestCo…...
wordpress 过滤图片/seo网站优化是什么
Written with StackEdit. Description 一家餐厅有 \(n\) 道菜,编号 \(1...n\) ,大家对第 \(i\) 道菜的评价值为 \(a_i(1≤i≤n)\)。 有 \(m\) 位顾客,第 \(i\) 位顾客的期望值为 \(b_i\),而他的偏好值为 \(x_i\) 。因此࿰…...
展馆设计论文/郑州百度搜索优化
文章目录差分介绍差分应用区间加区间求和总结3729. 改变数组元素100. 增减序列文章首发于:My Blog 欢迎大佬们前来逛逛 差分介绍 差分是一种常见的算法,用于快速修改数组中某一段区间的值。 差分的思想就是预处理出数组的差分数组,然后修改…...
无棣网页设计/郭生b如何优化网站
1.数组 public class Test{public static void main(String args[]){int[] intArray new int[] {1,4,3,2,5};//等价于 : int intArray[] new int[] {1,2,3,4,5};System.out.println(intArray.length); //打印长度//使用java.util.Arrays工具类 来操作 数组System.out.pr…...
建筑网官网查询/seo计费怎么刷关键词的
距离上次写博客已经一周多时间了,上周在选择工作中,这周开始加入了新公司,开始了新项目的测试用例编写,此时将测试用例中的一些基本问题进行整理,有不足的地方后续继续进行修改,从最基础的开始写起。 进入新…...
广州建设银行投诉网站/百度知道合伙人官网登录入口
本章概要: 1、创建office集成解决方案使用代码或非代码形式 2、使用内容类型作为能映射到文档库的文档 3、使用InfoPath管理表单 4、使用工作流管理业务流程 5、使用office2010服务端扩大SPS解决方案转载于:https://www.cnblogs.com/tonghounb/p/3482488.html...