代码随想录第四天打卡笔记

链表part2

1)两两交换链表中的节点

在这里插入图片描述
这道题按照三步走方式:
(1)第一步,设置cur指针指向这两个元素的第一个(这里一定要注意保存原结点!),断开cur与第一个节点的链接,指向第二个元素。cur->next = cur->next->next
(2)第二步,此时得到的链表结构为:<cur>——><2>——><3>,<1>——><2>,因此,此时需要将2与3之间的链接断开,使得2指向1。cur->next->next = temp->next
(3)第三步,链接1与3:cur->next->next->next = temp->next->next->next
小细节的话就是使用虚拟结点指向头结点,同时循环的终止条件是最后指向的两个指针不能为空,因为我们需要两两交换。

class solution{
public:ListNode* swapParis(ListNode* head){ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* temp = cur;cur->next = cur->next->next;    // 步骤一cur->next->next = temp->next;          // 步骤二cur->next->next->next = temp->next->next->next;   // 步骤三cur = cur->next->next;}ListNode* result = dummyHead->next;delete dummyHead;return result;}
};

2)删除链表的倒数第N个节点

在这里插入图片描述
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2:
输入:head = [1], n = 1 输出:[] 示例 3:
输入:head = [1,2], n = 1 输出:[1]
双指针的方法,好像这里用它的原因是如果我们要寻找倒数第n个,那么我们要先走到最末尾,然后再倒序寻找,因此这里用两个指针(也可以看作固定的窗长),给出文档里的题解步骤:

  • 定义fast指针和slow指针,初始值为虚拟头结点,如图:
    在这里插入图片描述
  • fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作),如图:
  • fast和slow同时移动,直到fast指向末尾,如题:
    在这里插入图片描述
  • 删除slow指向的下一个节点,如图:
    在这里插入图片描述
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n-- && fast != NULL) {fast = fast->next;}fast = fast->next; // fast再提前走一步,因为需要让slow指向删除节点的上一个节点while (fast != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // ListNode *tmp = slow->next;  C++释放内存的逻辑// slow->next = tmp->next;// delete tmp;return dummyHead->next;}
};

3)链表相交问题

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。图示两个链表在节点 c1 开始相交:

在这里插入图片描述
思路很简单:长的链表先遍历,遍历到剩余的结点数与短链表一至即可。
这里需要两个指针,一个指向A,一个指向B。

class solution{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB = 0;while(curA!=NULL){lenA++;curA = curA->next;}while(curB!=NULL){lenB++;curB = curB->next;}curA = headA;curB = headB;if(lenB > lenA){swap(lenA, lenB);swap(curA, curB);}int gap = lenA - lenB;while(gap--){curA = curA->next;}while(curA != NULL){if(curA == curB){return curA;}curA = curA->next;curB = curB->next;}return NULL;				}
};

4)环形链表2

这题把我CPU干烧了,直接看carl的解答吧

判断链表是否有环

可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。

为什么fast 走两个节点,slow走一个节点,有环的话,一定会在环内相遇呢,而不是永远的错开呢

首先第一点:fast指针一定先进入环中,如果fast指针和slow指针相遇的话,一定是在环中相遇,这是毋庸置疑的。

那么来看一下,为什么fast指针和slow指针一定会相遇呢?

可以画一个环,然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况, 如下图:

在这里插入图片描述
fast和slow各自再走一步, fast和slow就相遇了

这是因为fast是走两步,slow是走一步,其实相对于slow来说,fast是一个节点一个节点的靠近slow的,所以fast一定可以和slow重合。
在这里插入图片描述

如果有环,如何找到这个环的入口

此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:

在这里插入图片描述
那么相遇时: slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针,{y+z)为一圈内节点的个数A。

因为fast指针是一步走两个节点,slow指针一步走一个节点,所以 fast指针走过的节点数 = slow指针走过的节点数*2:(x + y) * 2 = x + y + n (y + z)。两边消掉一个(x+y): x + y = n (y + z)

因为要找环形的入口,那么要求的是x,因为x表示头结点到环形入口节点的的距离。所以要求x ,将x单独放在左面:x = n (y + z) - y ,再从n(y+z)中提出一个(y+z)来,整理公式之后为如下公式:x = (n -1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢?

先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。

当 n为1的时候,公式就化解为 x = z,

这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是环形入口的节点
也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。让index1和index2同时移动,每次移动一个节点,那么他们相遇的地方就是环形入口的节点。

n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;// 快慢指针相遇,此时从head 和 相遇点,同时查找直至相遇if (slow == fast) {ListNode* index1 = fast;ListNode* index2 = head;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index2; // 返回环的入口}}return NULL;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2981438.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

echarts实现云台控制按钮效果,方向按钮

效果图 代码 option {color: [#bfbfbf],tooltip: {show: false},series: [{name: ,type: pie,radius: [40%, 70%],avoidLabelOverlap: true,itemStyle: {// borderRadius: 10,borderColor: #fff,borderWidth: 2},label: {show: true,position: inside,fontSize: 36,color: #f…

CISAW应急服务:网络安全应急响应之路——从经验到认证的体会

随着信息技术的飞速发展&#xff0c;网络安全问题日益凸显。作为一名网络安全从业人员&#xff0c;我深知每一次安全事件给组织甚至国家带来的巨大损失和潜在影响。在多年的实际工作中&#xff0c;我积累了一些网络安全应急服务经验&#xff0c;并参加了信息安全保障人员认证&a…

火绒安全的应用介绍

火绒安全软件是一款集成了杀毒、防御和管控功能的安全软件&#xff0c;旨在为用户提供全面的计算机安全保障。以下是火绒安全软件的一些详细介绍&#xff1a; 系统兼容性强&#xff1a;该软件支持多种操作系统&#xff0c;包括Windows 11、Windows 10、Windows 8、Windows 7、…

深度学习| Attention U-Net(包含Attention Gate代码)

前言&#xff1a;最近在阅读一篇文章&#xff0c;用到了Attention Unet所以特地写了两篇文章&#xff0c;上一篇文章介绍了Attention的基础知识&#xff0c;这篇文化在哪个介绍Attention Unet相关知识以及代码。 Attention U-Net 基础注意力机制软注意力和硬注意力U-Net为什么…

【蓝牙协议栈】【BLE】低功耗蓝牙工作流程(角色\广播\扫描\连接等专业名词介绍)

1. 精讲蓝牙协议栈&#xff08;Bluetooth Stack&#xff09;&#xff1a;SPP/A2DP/AVRCP/HFP/PBAP/IAP2/HID/MAP/OPP/PAN/GATTC/GATTS/HOGP等协议理论 2. 欢迎大家关注和订阅&#xff0c;【精讲蓝牙协议栈】和【Android Bluetooth Stack】专栏会持续更新中.....敬请期待&#x…

✯✯✯宁波ISO45001认证:保障员工健康与安全✯✯✯

&#x1f308;&#x1f308;&#x1f308;最近&#xff0c;我们公司&#x1f970;通过了ISO 45001认证&#xff0c;&#x1f920;这让我感到非常&#x1f60e;兴奋和自豪&#xff01;&#x1f939;作为一个在&#x1f3d9;️宁波工作的员工&#xff0c;&#x1f913;我深深地感…

Golang | Leetcode Golang题解之第48题旋转图像

题目&#xff1a; 题解&#xff1a; func rotate(matrix [][]int) {n : len(matrix)// 水平翻转for i : 0; i < n/2; i {matrix[i], matrix[n-1-i] matrix[n-1-i], matrix[i]}// 主对角线翻转for i : 0; i < n; i {for j : 0; j < i; j {matrix[i][j], matrix[j][i]…

动力学重构/微分方程参数拟合 - 基于模型

这一篇文章&#xff0c;主要是给非线性动力学&#xff0c;对微分方程模型参数拟合感兴趣的朋友写的。笼统的来说&#xff0c;这与混沌系统的预测有关&#xff1b;传统的机器学习的模式识别虽然也会谈论预测结果&#xff0c;但他们一般不会涉及连续的预测。这里我们考虑的是&…

解决双击PDF文件出现打印的问题【Adobe DC】

问题描述 电脑安装Adobe Acrobat DC之后&#xff0c;双击PDF文件就会出现打印&#xff0c;而无法直接打开。 右键PDF文件就会发现&#xff0c;第一栏出现的不是用Adobe打开&#xff0c;而是打印。 重装软件多次仍然无法解决。 原因 右键菜单被改写了。双击其实是执行右键菜…

【氧化镓】影响Ga2O3器件沟道载流子迁移率的关键因素

总结 这篇文章对β-Ga2O3 MOSFETs中的通道载流子迁移率进行了深入研究&#xff0c;通过实验测量和理论分析&#xff0c;揭示了影响迁移率的关键因素&#xff0c;特别是库仑散射的影响。研究结果对于理解和改进β-Ga2O3 MOSFETs的性能具有重要意义&#xff0c;为未来的研究和器…

企业微信知识库为什么这么多企业都在用?原因就在这里

在科技迅猛发展的当下&#xff0c;企业信息化建设逐渐成为推动效率提升和核心竞争力增强的关键因素。而企业微信作为一个集团队沟通、项目管理、办公应用于一体的平台&#xff0c;其知识库功能为什么会受到广泛的欢迎和使用&#xff1f;让我们一探究竟。 首先&#xff0c;企业…

面试中关于 SpringCloud 都需要了解哪些基础?

在面试中&#xff0c;对于Spring Cloud的基础知识了解是至关重要的&#xff0c;因为Spring Cloud是构建分布式系统和微服务架构的关键技术栈之一。以下是在面试中可能会涉及到的相关问题。 1. 微服务架构基础 概念理解&#xff1a;理解微服务架构的概念&#xff0c;包括服务拆…

【C++】手撕list(list的模拟实现)

目录 01.节点 02.迭代器 迭代器运算符重载 03.list类 &#xff08;1&#xff09;构造与析构 &#xff08;2&#xff09;迭代器相关 &#xff08;3&#xff09;容量相关 &#xff08;4&#xff09;访问操作 &#xff08;5&#xff09;插入删除 我们在学习数据结构的时候…

【OceanBase诊断调优 】—— 如何快速定位SQL问题

作者简介&#xff1a; 花名&#xff1a;洪波&#xff0c;OceanBase 数据库解决方案架构师&#xff0c;目前负责 OceanBase 数据库在各大型互联网公司及企事业单位的落地与技术指导&#xff0c;曾就职于互联网大厂和金融科技公司&#xff0c;主导过多项数据库升级、迁移、国产化…

台灯太亮会影响视力吗?分享五款防近视护眼台灯

台灯作为一盏实用的桌面照明灯具&#xff0c;是孩子学习过程中必不可少的“好伴侣”&#xff0c;不过大多数家长只关注到台灯的光线是否够亮&#xff0c;认为只要亮度足够就可以了&#xff0c;那么台灯太亮会影响视力吗&#xff1f; 答案是会的。首先太暗的环境肯定是不够支撑孩…

用友NC Cloud importhttpscer接口任意文件上传漏洞

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 一、漏洞描述 用友NC Cloud的importhttpscer接口如果存在任意文件上传…

【pycharm】调试模式中四个常用按钮介绍

【pycharm】调试模式中四个常用按钮介绍 在 PyCharm 的调试模式中&#xff0c;有四个常用的按钮&#xff0c;它们的功能如下&#xff1a; Step Over (F8)&#xff1a;单步执行&#xff0c;但在遇到函数调用时&#xff0c;不会进入函数内部&#xff0c;而是将整个函数作为一步执…

【八股】计算机网络篇

网络模型 应用层【HTTP&#x1f449;报文/消息】 传输层【TCP或UDP&#x1f449;段&#x1f449;MSS】网络层【IP、寻址和路由&#x1f449;MTU】 ①IP&#xff08;Internet Protocol&#xff0c;网际协议&#xff09;主要作用是定义数据包的格式、对数据包进行路由和寻址&…

计算机网络物理层思维导图+大纲笔记

大纲笔记&#xff1a; 物理层的基本概念 解决如何在连接各种计算机的传输媒体上传输数据比特流&#xff0c;而不是具体的传输媒体 主要任务 确定与传输媒体接口有关的一些特性 机械特性 电气特性 功能特性 规程特性信道上传送的信号 基带信号 来自信源的信号&#xff0c;直接表…

CentOS-7部署mysql、clickhouse并通过普罗米修斯、grafna监控告警

一、准备工作 1、系统环境 所用镜像&#xff1a;CentOS-7-x86_64-DVD-2009.iso 2、涉及安装包 3、克隆4台虚拟机 用途IP主机名Prometneus服务器192.168.15.129master被监控服务器1192.168.15.133node1mysql、clickhouse、grafana服务器192.168.15.134node2被监控服务器219…