【题解】判断链表中是否有环、链表中环的入口结点
文章目录
- 判断链表中是否有环
- 链表中环的入口结点
判断链表中是否有环
题目链接:判断链表中是否有环
解题思路1:快慢指针
代码如下:
bool hasCycle(ListNode *head) {if(head == nullptr) return false;ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;}
解题思路2:hash法
我们把所有的节点放到哈希表中,我们遍历整个链表,如果存在重复的相同节点,那就证明链表中有环
代码如下:
bool hasCycle(ListNode *head) {map<ListNode*, int> mp;ListNode* cur = head;while(cur != nullptr){if(mp[cur] == 1) return true;mp[cur] = 1;cur = cur->next;}return false;}
链表中环的入口结点
题目链接:链表中环的入口结点
解题思路1:hash法,记录第一次重复的节点
代码如下:
ListNode* EntryNodeOfLoop(ListNode* pHead) {map<ListNode*, int> mp;ListNode* cur = pHead;while (cur != nullptr) {if (mp[cur] == 1) return cur;mp[cur] = 1;cur = cur->next;}return nullptr;}
解题思路2:快慢指针
上面我们用快慢指针来判断一个链表是否有环,我们也可以通过快慢指针来找到环的入口节点。我们要找到快慢指针之间步数的数学关系,借助数学关系来找到环的入口节点
假设从头结点到环的入口节点一共有a个节点,环中的节点一共有b个,设快指针走的步数为f,慢指针走的步数为s,那么有步数之间有这样的数学关系:
- f = 2 * s ;快指针一次走两步,慢指针一次走一步
- f = s + nb ;当快慢指针相遇时,快指针一定比慢指针多走了nb步,意思就是多绕环了n圈
所以可以得出:s = nb,f = 2nb;
当快慢指针相遇时,慢指针已经走了nb步,快指针走了2nb步,同时我们要走到环的入口节点需要走a + kb 步,而这时慢指针的nb只要再走a步即可到达入口,所以我们把快指针移动到头节点,之后,再让两个指针一次走一步往前走,当他们相遇时所处的节点就是入口节点
代码如下:
ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast = pHead;ListNode* slow = pHead;while(fast != nullptr){slow = slow->next;if(fast->next == nullptr) return nullptr;//链表中无环fast = fast->next->next;if(fast == slow){//快慢指针相遇fast = pHead;//让快指针重新指向pHeadwhile(fast != slow){//通过两个指针的相遇,控制fast走a步fast = fast->next;slow = slow->next;}return fast;//此时fast即是入口节点,直接返回}}return nullptr;}
相关文章:
【题解】判断链表中是否有环、链表中环的入口结点
文章目录 判断链表中是否有环链表中环的入口结点 判断链表中是否有环 题目链接:判断链表中是否有环 解题思路1:快慢指针 代码如下: bool hasCycle(ListNode *head) {if(head nullptr) return false;ListNode* fast head;ListNode* slow …...

Pytorch 最全入门介绍,Pytorch入门看这一篇就够了
本文通过详细且实践性的方式介绍了 PyTorch 的使用,包括环境安装、基础知识、张量操作、自动求导机制、神经网络创建、数据处理、模型训练、测试以及模型的保存和加载。 1. Pytorch简介 在这一部分,我们将会对Pytorch做一个简单的介绍,包括它…...
Lambda 表达式的作用域
在Lambda表达式中访问外层作用域和旧版本的匿名对象中的方式类似。你可以直接访问标记了final的外层局部变量,或者实例的字段以及静态变量。 Lambda表达式不会从超类(supertype)中继承任何变量名,也不会引入一个新的作用域。Lambd…...

【portswigger】第二专题-XSS(二)
portswigger 靶场(第二章节)XSS 视频同步更新至bilibili bibi地址 【【portswigger】第二专题-XSS(一前置知识)】 https://www.bilibili.com/video/BV1mp4y157xA/?share_sourcecopy_web 【【portswigger】第二专题-XSSÿ…...

【计算机视觉|人脸建模】3D人脸重建基础知识(入门)
本系列博文为深度学习/计算机视觉论文笔记,转载请注明出处 一、三维重建基础 三维重建(3D Reconstruction)是指根据单视图或者多视图的图像重建三维信息的过程。 1. 常见三维重建技术 人工几何模型仪器采集基于图像的建模描述基于几何建模…...

使用Jetpack Glance创建Android Widget
使用Jetpack Glance创建Android Widget Jetpack Glance发布,让我们使用Google提供的Jetpack Glance创建一个联系人列表小部件。 https://developer.android.com/jetpack/compose/glance 什么是Glance? Jetpack Glance是一个使用Kotlin API创建小型、轻…...

【MyBatis 学习三】子段不一致问题 多表查询 动态SQL
目录 一、解决Java实体类属性与数据库表字段不一致问题 🌷现象1:显示字段不对应:使用ResultType查询结果为null; 🌷解决办法:字段不对应:使用ResultMap解决。 二、数据库的多表查询 &#…...

15. Spring AOP 的实现原理 代理模式
目录 1. 代理模式 2. 静态代理 3. 动态代理 3.1 JDK 动态代理 3.2 CGLIB 动态代理 4. JDK 动态代理和 CGLIB 动态代理对比 5. Spring代理选择 6. Spring AOP 实现原理 6.1 织入 7. JDK 动态代理实现 8. CGLIB 动态代理实现 9. 总结 1. 代理模式 代理模式…...
死锁产生的原因以及解决方案
一.原因: 1.使用互斥锁. 2.除非主动释放,负责不能被抢占. 3.占用一把锁不释放,等待其它锁资源(保持现状). 4.锁形成环路. 二.解决方案: 给锁编号,上锁的时候从小到大依次上锁,譬如如果一个线程要上1号和2号两把锁,如果1号锁被占用,不能上2号锁,等其它线程释放1号锁资源后…...

【构造】CF1758 D
Problem - D - Codeforces 题意: 思路: 如果需要构造一个和为定值的序列,那么考虑n-d,n-d1,.....nd-1,nd这种形式 如果要保证不能重复,那么先考虑一个排列,然后在排列上操作 如果根据小数据构造出了一些简单情形&a…...

【腾讯云 Cloud Studio 实战训练营】永不宕机的IDE,Coding Everywhere
【腾讯云 Cloud Studio 实战训练营】永不宕机的IDE,随时随地写代码! 写在最前视频讲解:Cloud Studio活动简介何为腾讯云 Cloud Studio?Cloud Studio简介免费试用,上手无忧Cloud Studio 特点及优势云端开发多种预制环境可选metawo…...
JavaScript将一层级对象数组转为children嵌套的三层级树状对象数组(多级树状分类)
有时候后端返回的数据不适合前端,我们就需要进行转换,比如我想用elementUI的级联选择器,而这个组件对数据格式有要求,本篇文章将介绍如何将一层级对象数组数据格式转为三层级嵌套children数组,JavaScript、Vue、小程序等都适用,使用情景为多级分类,嵌套数据 情况1:原数…...
Windows脚本启动Redis、Java和Nginx服务指南
文章目录 1. 完整的批处理脚本2. Redis服务3. Java服务4. Nginx服务 1. 完整的批处理脚本 echo offcd C:\path\to\redis tasklist /FI "IMAGENAME eq redis-server.exe" 2>NUL | find /I /N "redis-server.exe">NUL if "%ERRORLEVEL%"&qu…...

【宝藏系列】STM32之C语言基础知识
【宝藏系列】STM32之C语言基础知识 文章目录 【宝藏系列】STM32之C语言基础知识1️⃣位操作2️⃣define宏定义3️⃣ifdef条件编译4️⃣extern变量声明5️⃣typedef类型别名 C语言是单片机开发中的必备基础知识,本文列举了部分 STM32 学习中比较常见的一些C语言基础知…...

探索自除数:发现区间内的神奇数字
本篇博客会讲解力扣“728. 自除数”的解题思路,这是题目链接。 对于给定的正整数num,我们如何判断它是不是自除数呢?根据定义,我们只需要把num的每一位数字都取出来,判断能不能整除num,如果发现num的某一位…...
打卡力扣题目四
#左耳听风 ARST 打卡活动重启# 目录 一、题目 二、解题代码 三、解题思路 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享…...

npm yarn nrm
npm 和 yarn npm和yarn都是包管理器,yarn是在2016年发布的,那时npm还处于V3时期,那时候还没有package-lock.json文件,不稳定性、安装速度慢等缺点经常会受到广大开发者吐槽。此时,yarn 诞生了。yarn 的优点,…...

关于我对刚开始学Java的小白想分享的内容:
编程是很有魅力的,让很多人为之痴迷 如果你是初学者,俗称小白,不妨看看下述内容: 文章目录 1. Java 简介 Java 是一门编程语言,发展至今已经成为一门真正意义上的语言标准。 Java是一个完整的平台,有一个…...
Redis学习路线(5)—— Redis生成唯一ID
一、全局唯一ID (一)在用户抢购时,就会生成订单并保存到数据库中,而订单表如果使用自增ID就会存在以下几种情况: 自增ID规律性太强受单表数据量的限制 (二)全局ID生成器,是一种在…...
django后台系统Tyadmin
无意之间发现个django的后台管理框架,仔细与xadmin对比了一下,无论是功能上还是便携性上都与xadmin特别相似,但个人感觉Tyadmin略胜一筹,因为外观上要比xadmin要美观,而且相比起来速度也快,部署甚至也和简单…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...

解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

DAY 45 超大力王爱学Python
来自超大力王的友情提示:在用tensordoard的时候一定一定要用绝对位置,例如:tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾: tensorboard的发展历史和原理tens…...

轻量级Docker管理工具Docker Switchboard
简介 什么是 Docker Switchboard ? Docker Switchboard 是一个轻量级的 Web 应用程序,用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器,使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...

ubuntu中安装conda的后遗症
缘由: 在编译rk3588的sdk时,遇到编译buildroot失败,提示如下: 提示缺失expect,但是实测相关工具是在的,如下显示: 然后查找借助各个ai工具,重新安装相关的工具,依然无解。 解决&am…...