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

leetcode-链表篇3

leetcode-61

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]

示例 2:

输入:head = [0,1,2], k = 4
输出:[2,0,1]

提示:

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

思路:看图片可以发现,这个题目本质上,是把链表分成两部分,交换前后两部分的顺序

所以重点在于找到分裂点,以及拼接

/*** 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* rotateRight(ListNode* head, int k) {if(!head || !head->next || k == 0) {return head;}auto tmp = head;int count = 0;auto tail = head;while(tmp) {tail = tmp;tmp = tmp->next;++count;}tmp = head;k %= count;if(k == 0) {return head;}k = count - k;while(--k && tmp) {tmp = tmp->next;}auto new_head = tmp->next;tmp->next = nullptr;tail->next = head;return new_head;}   
};

leetcode-206

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

思路:递归法比较简单,还是我们的老模板

void circle(ListNode *head) {if(...) {return }        //边界条件auto res = circle(head->next);//other code//return
}

迭代法也是一器破万法。

关于链表反转的题目,都分成两部分,pre和curr

pre就是已经处理好的部分的尾节点, curr就是你要处理的部分的头节点

所以伪代码如下

//关于翻转链表相关的题目
while(xxx) {process(curr);      //实现翻转的逻辑pre = curr;         //当前部分已经处过,所以pre变成currcurr = curr->next;  //curr->next还没处理过,所以curr指向自己的next继续处理
}
/*** 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* reverseList(ListNode* head) {if(!head || !head->next) {return head;}// auto next = reverseList(head->next);// auto tmp = head->next;// head->next = nullptr;// tmp->next = head;// return next;auto pre = head;pre = nullptr;while(head) {auto next = head->next;head->next = nullptr;head->next = pre;pre = head;head = next;}return pre;}
};

leetcode-92

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例 1:

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶: 你可以使用一趟扫描完成反转吗?

思路,和上题一样,不过是对翻转的区间有限制了。

加上前缀节点pre,找到要翻转的区间的头尾节点,将之翻转后。拼接回原来的链表

/*** 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* reverseBetween(ListNode* head, int left, int right) {if(!head || !head->next) {return head;}auto tmp = new ListNode(-1);tmp->next = head;auto pre = tmp;int count = left;while(--count) {tmp = tmp->next;}auto curr = tmp->next;for(int i=0; i<right-left; i++) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;tmp->next = next;next->next = new_tail;}return pre->next;}
};

leetcode-24

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

思路:还记得我们一器破万法的迭代法模板吗,直接套用就可以

/*** 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) {if(!head || !head->next) {return head;}auto pre = new ListNode(-1);pre->next = head;auto curr = head;auto tmp = pre;while(curr && curr->next) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;next->next = new_tail;tmp->next = next;tmp = curr;curr = curr->next;}return pre->next;}
};

leetcode-25

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:
  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

思路:做了以上几道题目,总结了自己的一器破万法模板之后,发现这个题竟然这么简单

以前被自己视为面试杀手的接雨水,k个一组翻转链表也变得简单起来

这题和上一题的唯一不同就在于,需要遍历一遍算出链表的长度,避免越界

/*** 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) {auto tmp = head;int count=0;while(tmp) {++count;tmp = tmp->next;}if(!head || !head->next || k>count || k<=1) {return head;}auto pre = new ListNode(-1);pre->next = head;tmp = pre;auto curr = head;    for(int i=0; i<count/k; i++) {for(int j=1; j<k; j++) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;next->next = new_tail;tmp->next = next;}tmp = curr;curr = curr->next;}return pre->next;}
};

相关文章:

leetcode-链表篇3

leetcode-61 给你一个链表的头节点 head &#xff0c;旋转链表&#xff0c;将链表每个节点向右移动 k 个位置。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], k 2 输出&#xff1a;[4,5,1,2,3]示例 2&#xff1a; 输入&#xff1a;head [0,1,2], k 4 输出&#x…...

RAG(Retrieval Augmented Generation)及衍生框架:CRAG、Self-RAG与HyDe的深入探讨

近年来&#xff0c;随着大型语言模型&#xff08;LLMs&#xff09;的迅猛发展&#xff0c;我们在寻求更精确、更可靠的语言生成能力上取得了显著进展。其中&#xff0c;检索增强生成&#xff08;Retrieval-Augmented Generation&#xff09;作为一种创新方法&#xff0c;极大地…...

C语言介绍

什么是C语言 C programing language 能干什么 Hello world&#xff1f; 如何学C语言 no reading no learning...

损失函数篇 | YOLOv10 更换损失函数之 MPDIoU | 《2023 一种用于高效准确的边界框回归的损失函数》

论文地址:https://arxiv.org/pdf/2307.07662v1.pdf 边界框回归(Bounding Box Regression,BBR)在目标检测和实例分割中得到了广泛应用,是目标定位的重要步骤。然而,对于边界框回归的大多数现有损失函数来说,当预测的边界框与真值边界框具有相同的长宽比,但宽度和高度的…...

WMware安装WMware Tools(Linux~Ubuntu)

1、这里终端里面输入sudo apt upgrade用于更新最新的包 sudo apt upgrade 2、安装 open-vm-tools-desktop 包&#xff0c; Ps&#xff1a;这里是以为我已经安装好了。 udo apt install open-vm-tools-desktop -y3、最后重启就大功告成了 reboot 4、测试是否成功&#xff1a…...

SLAM ORB-SLAM2(30)关键帧跟踪

SLAM ORB-SLAM2(30)关键帧跟踪 1. 关键帧跟踪2. TrackReferenceKeyFrame2.1. 将当前普通帧的描述子转化为BoW向量2.2. 通过词袋BoW加速当前帧与参考帧之间的特征点匹配2.3. 将上一帧的位姿态作为当前帧位姿的初始值2.4. 通过优化3D-2D的重投影误差来获得位姿2.5. 剔除优化后的…...

k8s 部署 prometheus

创建namespace prometheus-namespace.yaml apiVersion: v1 kind: Namespace metadata:name: ns-prometheus拉取镜像 docker pull swr.cn-north-4.myhuaweicloud.com/ddn-k8s/quay.io/prometheus/prometheus:v2.54.0prometheus配置文件configmap prometheus-configmap.yaml …...

使用VBA快速生成Excel工作表非连续列图片快照

Excel中示例数据如下图所示。 现在需要拷贝A2:A15,D2:D15,J2:J15,L2:L15,R2:R15为图片&#xff0c;然后粘贴到A18单元格&#xff0c;如下图所示。 大家都知道VBA中Range对象有CopyPicture方法可以拷贝为图片&#xff0c;但是如果Range对象为非连续区域&#xff0c;那么将产生10…...

解决GitHub下载速度慢

解决GitHub下载速度慢 方法一&#xff1a;使用git clone 地址 --depth 1来下载 depth 1 表示只科隆最新的一次提交&#xff0c;也就是默认主分支&#xff0c;而不是完整地克隆整个代码仓库&#xff0c;这样可以减少下载地数据&#xff0c;加快克隆操作 可以用git clone 地址 …...

【机器学习(五)】分类和回归任务-AdaBoost算法

文章目录 一、算法概念一、算法原理&#xff08;一&#xff09;分类算法基本思路1、训练集和权重初始化2、弱分类器的加权误差3、弱分类器的权重4、Adaboost 分类损失函数5、样本权重更新6、AdaBoost 的强分类器 &#xff08;二&#xff09;回归算法基本思路1、最大误差的计算2…...

【设计模式-模板】

定义 模板方法模式是一种行为设计模式&#xff0c;它在一个方法中定义了一个算法的骨架&#xff0c;并将一些步骤延迟到子类中实现。通过这种方式&#xff0c;模板方法允许子类在不改变算法结构的情况下重新定义算法中的某些特定步骤。 UML图 组成角色 AbstractClass&#x…...

小程序原生-列表渲染

1. 列表渲染的基础用法 <!--渲染数组列表--> <view wx:for"{{numList}}" wx:key"*this" > 序号&#xff1a;{{index}} - 元素&#xff1a;{{item}}</view> <!--渲染对象属性--> <view wx:for"{{userInfo}}" wx:key&q…...

JAVA认识异常

目录 1. 异常的概念与体系结构 1.1 异常的概念 1. 算术异常 2. 数组越界异常 3. 空指针异常 1.2 异常的分类 1. 编译时异常 2. 运行时异常 2.1 异常的处理 防御式编程 2.2 异常的捕获 2.3.1 异常声明throws 2.3.2 try-catch捕获并处理 2.3.3 finally 总结 1. 异常…...

2024年10月计划(工作为主,Ue5独立游戏为辅,)

我发现一点&#xff0c;就是工作很忙&#xff0c;比如中秋也在远程加班&#xff0c;周末有时也远程加班&#xff0c;国庆节甚至也差点去甲方工作。甚至有可能驻场。可见&#xff0c;小公司确实不能去。 好在&#xff0c;9月份时&#xff0c;通过渲染 除了上班时间外&#xff0…...

并发、并行和异步设计

译者个人领悟,一家之言: 并发和并行确实可以明确区分出来,因为cpu的速度非常快,在执行一个任务时经常要等其他组件,比如网络,磁盘等,如果一直串行等待这样就会造成很大的浪费. (就类似于烧水的同时,可以切菜,不用等烧水完成了才去切菜,我可以烧一会水,火生起来了水壶放上了,随…...

求职Leetcode题目(12)

1.只出现一次的数字 异或运算满足交换律 a⊕bb⊕a &#xff0c;即以上运算结果与 nums 的元素顺序无关。代码如下&#xff1a; class Solution {public int singleNumber(int[] nums) {int ans 0;for(int num:nums){ans^num;}return ans;} } 2.只出现一次的数字II 这是今天滴…...

【YashanDB知识库】如何配置jdbc驱动使getDatabaseProductName()返回Oracle

本文转自YashanDB官网&#xff0c;具体内容请见https://www.yashandb.com/newsinfo/7352676.html?templateId1718516 问题现象 某些三方件&#xff0c;例如 工作流引擎activiti&#xff0c;暂未适配yashandb&#xff0c;使用中会出现如下异常&#xff1a; 问题的风险及影响 …...

Hadoop三大组件之MapReduce(一)

Hadoop之MapReduce 1. MapReduce是什么 MapReduce是一个分布式运算程序的编程框架&#xff0c;旨在帮助用户开发基于Hadoop的数据分析应用。它的核心功能是将用户编写的业务逻辑代码与自带的默认组件整合&#xff0c;形成一个完整的分布式运算程序&#xff0c;并并发运行在一…...

SQL Server 分页查询的学习文章

SQL Server 分页查询的学习文章 一、SQL Server 分页查询1. 什么是分页查询&#xff1f;2. SQL Server 的分页查询方法2.1 使用 OFFSET 和 FETCH NEXT语法&#xff1a;示例&#xff1a; 2.2 使用 ROW_NUMBER() 方法语法&#xff1a;示例&#xff1a; 2.3 性能考虑3. 总结 一、S…...

告别PDF大文件困扰!4款PDF在线压缩工具助你轻松优化!

嘿&#xff0c;档案员小伙伴们&#xff0c;今天咱们来聊聊那些让咱们在档案堆里游刃有余的神器。这些工具啊&#xff0c;简直就是咱们档案员的得力助手&#xff0c;特别是在PDF压缩这块儿&#xff0c;简直就是神器中的神器&#xff01; 1、福昕转换大师 网址&#xff1a;http…...

如何使用Compiler Explorer实时编译原理:揭秘代码到汇编的转换过程

如何使用Compiler Explorer实时编译原理&#xff1a;揭秘代码到汇编的转换过程 【免费下载链接】compiler-explorer Run compilers interactively from your web browser and interact with the assembly 项目地址: https://gitcode.com/gh_mirrors/co/compiler-explorer …...

vscode-drawio扩展依赖更新:安全高效地管理第三方库

vscode-drawio扩展依赖更新&#xff1a;安全高效地管理第三方库 【免费下载链接】vscode-drawio This unofficial extension integrates Draw.io (also known as diagrams.net) into VS Code. 项目地址: https://gitcode.com/gh_mirrors/vs/vscode-drawio vscode-drawio…...

JPEXS Free Flash Decompiler与Web3.0存储:去中心化SWF文件管理的终极指南

JPEXS Free Flash Decompiler与Web3.0存储&#xff1a;去中心化SWF文件管理的终极指南 【免费下载链接】jpexs-decompiler JPEXS Free Flash Decompiler 项目地址: https://gitcode.com/gh_mirrors/jp/jpexs-decompiler JPEXS Free Flash Decompiler是一款功能强大的开源…...

ComfyUI Inpaint实战:5分钟搞定照片路人甲,AI修图从此不求人

ComfyUI Inpaint实战&#xff1a;5分钟搞定照片路人甲&#xff0c;AI修图从此不求人 每次旅行拍照总有几个"不速之客"闯入镜头&#xff1f;社交媒体晒图前总为背景里的路人发愁&#xff1f;别担心&#xff0c;今天我要分享的ComfyUI Inpaint技术&#xff0c;能让这些…...

从零构建一个轻量级WebSocket服务器:基于libwebsockets的实战与事件循环剖析

从零构建一个轻量级WebSocket服务器&#xff1a;基于libwebsockets的实战与事件循环剖析 在当今实时应用盛行的时代&#xff0c;WebSocket技术已成为构建即时通讯、实时数据推送等功能的基石。不同于传统的HTTP请求-响应模式&#xff0c;WebSocket提供了全双工通信能力&#xf…...

基于STM32CubeMX的AD9850驱动开发与频率合成实战

1. 从零开始认识AD9850与STM32CubeMX 第一次接触AD9850这个芯片时&#xff0c;我完全被它的性能震撼到了——这个比指甲盖还小的芯片&#xff0c;居然能产生0.0291Hz分辨率的信号&#xff01;当时我正在做一个射频测试项目&#xff0c;需要生成精确的正弦波信号。市面上常见的…...

低成本搭建AI知识库:Qwen3-Embedding-4B量化版仅需3GB显存教程

低成本搭建AI知识库&#xff1a;Qwen3-Embedding-4B量化版仅需3GB显存教程 1. 引言&#xff1a;为什么选择Qwen3-Embedding-4B&#xff1f; 在构建AI知识库时&#xff0c;文本向量化模型的选择至关重要。传统方案要么性能不足&#xff0c;要么资源消耗过大。Qwen3-Embedding-…...

PHP 反序列化漏洞深度解析:从原理利用到 allowed_classes 防御实战

PHP 反序列化漏洞深度解析&#xff1a;从原理利用到 allowed_classes 防御实战在 PHP 安全领域&#xff0c;反序列化漏洞&#xff08;Deserialization Vulnerability&#xff09; 长期占据高危漏洞的榜首。它允许攻击者在服务器上执行任意代码、删除文件、甚至获取服务器最高权…...

别只盯着显卡!CES上英伟达那个能装进口袋的AI超算,普通人怎么玩?

口袋里的AI革命&#xff1a;如何用英伟达Project DIGITS打造个人智能工作站 当大多数人还在讨论RTX 50系列显卡的游戏性能时&#xff0c;英伟达在CES 2025上悄悄展示了一个可能改变未来的小玩意——Project DIGITS。这个能装进口袋的AI超算&#xff0c;搭载GB10芯片&#xff0c…...

2026论文写作工具红黑榜:AI论文网站怎么选?这份榜单够用!

红榜优先选千笔AI、ThouPen、豆包&#xff0c;适配国内学术规范&#xff1b;黑榜避开低质免费工具、无真实引用平台、过度依赖全文生成的工具&#xff0c;优先按需求匹配三维模型&#xff08;需求匹配度 - 数据可信度 - 成本承受力&#xff09;。 一、红榜&#xff1a;10 款高分…...