环形链表系列导学
问题描述
给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 null。
将链表问题转化为数学问题
状态序列与循环
我们可以将链表节点视为状态,每个节点的 next 指针代表状态转移函数 f f f。从头节点开始,我们可以得到一个状态序列:
- x 0 , x 1 = f ( x 0 ) , x 2 = f ( x 1 ) , x 3 = f ( x 2 ) , … x_0, x_1 = f(x_0), x_2 = f(x_1), x_3 = f(x_2), \ldots x0,x1=f(x0),x2=f(x1),x3=f(x2),…
如果链表中存在环,那么这个序列将出现循环。
寻找循环起点
我们的目标是找到状态序列中最小的 μ \mu μ,使得对于某个最小的 λ \lambda λ,满足:
- x μ = x μ + λ x_{\mu} = x_{\mu + \lambda} xμ=xμ+λ
其中:
- μ \mu μ 是循环的起始位置(环的入口)
- λ \lambda λ 是循环节的长度(环的长度)
Floyd 判圈算法的数学原理
阶段一:检测循环
使用两个指针:
- 慢指针(slow):每次移动一步
- 快指针(fast):每次移动两步
阶段二:找到循环的起始位置
数学推导
设:
- 非环部分长度: a a a
- 环的长度: b b b
- 从环入口到相遇点的距离: c c c
- 快指针在环内绕行的圈数: k k k ( k ≥ 1 k \geq 1 k≥1)
距离关系
-
慢指针走的总距离:
D slow = a + c D_{\text{slow}} = a + c Dslow=a+c -
快指针走的总距离:
D fast = a + c + k × b D_{\text{fast}} = a + c + k \times b Dfast=a+c+k×b -
由于快指针速度是慢指针的两倍:
D fast = 2 × D slow D_{\text{fast}} = 2 \times D_{\text{slow}} Dfast=2×Dslow
推导步骤
-
建立等式:
a + c + k × b = 2 × ( a + c ) a + c + k \times b = 2 \times (a + c) a+c+k×b=2×(a+c) -
化简:
a + c + k × b = 2 a + 2 c a + c + k \times b = 2a + 2c a+c+k×b=2a+2c
k × b = 2 a + 2 c − a − c k \times b = 2a + 2c - a - c k×b=2a+2c−a−c
k × b = a + c k \times b = a + c k×b=a+c -
得出关系式:
a + c = k × b a + c = k \times b a+c=k×b
寻找环的入口
- 快指针走了 a a a 步到达环入口
- 慢指针从相遇点再走 b − c b - c b−c 步也到达环入口
因为:
b − c = b − ( k × b − a ) = − ( k − 1 ) × b + a b - c = b - (k \times b - a) = - (k - 1) \times b + a b−c=b−(k×b−a)=−(k−1)×b+a
具体例子
假设:
- 非环部分长度: a = 3 a = 3 a=3
- 环的长度: b = 4 b = 4 b=4
- 快指针在环内绕行的圈数: k = 1 k = 1 k=1
根据推导:
a + c = k × b ⟹ c = k × b − a = 1 × 4 − 3 = 1 a + c = k \times b \implies c = k \times b - a = 1 \times 4 - 3 = 1 a+c=k×b⟹c=k×b−a=1×4−3=1
-
慢指针走的总距离:
D slow = a + c = 3 + 1 = 4 D_{\text{slow}} = a + c = 3 + 1 = 4 Dslow=a+c=3+1=4 -
快指针走的总距离:
D fast = 2 × D slow = 8 D_{\text{fast}} = 2 \times D_{\text{slow}} = 8 Dfast=2×Dslow=8
验证快指针的距离:
D fast = a + c + k × b = 3 + 1 + 1 × 4 = 8 D_{\text{fast}} = a + c + k \times b = 3 + 1 + 1 \times 4 = 8 Dfast=a+c+k×b=3+1+1×4=8
相关文章:
环形链表系列导学
问题描述 给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 null。 将链表问题转化为数学问题 状态序列与循环 我们可以将链表节点视为状态,每个节点的 next 指针代表状态转移函数 f f f。从头节点开始,我…...
IDEA2024创建一个spingboot项目
以下是创建一个基本的 Spring Boot 项目的步骤和示例: 初始化一个springboot工程其实有许多方法,笔者这里挑了一个最快捷的方式搭建一个项目。我们直接通过官方平台(start.spring.io)进行配置,然后下载压缩包就可以获取…...
Nginx:ssl
目录 部署ssl前提 nginx部署ssl证书 部署ssl部署建议 部署ssl前提 网站有域名根据域名申请到ssl证书,并下载证书部署到nginx中 部署了ssl证书后,访问的流量是加密的。 nginx部署ssl证书 #80端口跳转到443 server {listen 80;return 302 https://1…...
QT配置文件详解
TEMPLATElib TEMPLATE变量用于指定项目模板类型,其值可以是以下几种: app:建立一个应用程序的makefile,这是默认值。lib:建立一个库的makefile。vcapp:建立一个应用程序的Visual Studio项目文件。vclib&a…...
根据合约地址判断合约协议的方法
判断合约协议之前,需要了解一下什么是ERC165协议: ERC165 是以太坊中用于标准化接口检测的协议,由 Fabian Vogelsteller 在 2018 年创建 ,其核心内容主要包括以下方面: 接口定义 单一函数接口:ERC165 协议…...
联想YOGA Pro 14s至尊版电脑找不到独立显卡(N卡)问题,也无法安装驱动的问题
问题描述 电脑是联想YOGA Pro 14s至尊版,电脑上装的独立显卡是4060,一直是能够使用独立显卡的。然而有两次突然就找不到显卡了,NVIDIA CONTROL PANEL也消失了,而且也无法安装驱动。具体表现如下: 无法连接外接显示器…...
Spring Web开发注解和请求(1)
大家好我是小帅,今天我们来学习Spring Web MVC框架(入门级) 文章目录 1. 什么是 Spring Web MVC?1.1 MVC 定义1.2 什么是Spring MVC ? 2. 学习Spring MVC2.1 建⽴连接第一个spring MVC程序 3. web开发注解的解释3.1RestControlle…...
Supervisor使用教程
文章目录 [toc] Supervisor使用教程平台要求 安装supervisor本文测试的时候是使用Linux的yum安装的(其它方式未做测试)加入系统守护进行 Supervisor使用教程 在项目中,经常有脚本需要常驻运行的需求。以PHP脚本为例,最简单的方式…...
Spark基本命令详解
文章目录 Spark基本命令详解一、引言二、Spark Core 基本命令1、Transformations(转换操作)1.1、groupBy(func)1.2、filter(func) 2、Actions(动作操作)2.1、distinct([numTasks])2.2、sortBy(func, [ascending], [numTasks]) 三、…...
Three.js 相机视角的平滑过渡与点击模型切换视角
在 Three.js 中,实现相机视角的平滑过渡和点击模型切换到查看模型视角是一个常见且有用的功能。这种效果不仅能提升用户体验,还能为场景互动添加更多的动态元素。 1. 基本设置 首先,我们需要创建一个基本的 Three.js 场景,包括相…...
jenken 打包linux包遇到的问题(环境变量)
环境变量问题 我们jenkens 打包的时候 远程打包 通过ssh 去在服务器上调用脚本 环境变量没有去自动加载 代码打包的时候总是提示相关的so文件找不到 解决方案在 相关程序的make之前 把环境变量加在前面 我这里直接将变量加载代码的最前面...
使用 Go 语言中的 Context 取消协程执行
使用 Go 语言中的 Context 取消协程执行 在 Go 语言中,协程(goroutine)是一种轻量级的线程,非常适合处理并发任务。然而,如何优雅地取消正在运行的协程是一个常见的问题。本文将通过一个具体的例子来展示如何使用 con…...
python图像彩色数字化
效果展示: 目录结构: alphabets.py GENERAL {"simple": "%#*-:. ","complex": "$B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/\|()1{}[]?-_~<>i!lI;:,\"^. " } # Full list could be found here…...
cesium 3dtile ClippingPlanes 多边形挖洞ClippingPlaneCollection
原理就是3dtiles里面的属性clippingPlanes 采用ClippingPlaneCollection,构成多边形来挖洞。 其次就是xyz法向量挖洞 clippingPlanes: new this.ffCesium.Cesium.ClippingPlaneCollection({unionClippingRegions: true, // true 表示多个切割面能合并为一个有效的…...
docker 僵尸进程问题
docker僵尸进程 子进程结束后,父进程没有回收该进程资源(父进程可能没有wait),子进程残留资源存放与内核中,就变为僵尸进程(zombie) 场景分析:python脚本A中执行B应用,将A部署在docker中&#…...
微软要求 Windows Insider 用户试用备受争议的召回功能
拥有搭载 Qualcomm Snapdragon 处理器的 Copilot PC 的 Windows Insider 计划参与者现在可以试用 Recall,这是一项臭名昭著的快照拍摄 AI 功能,在今年早些时候推出时受到了很多批评。 Windows 营销高级总监 Melissa Grant 上周表示:“我们听…...
husky,commit规范,生成CHANGELOG.md,npm发版
项目git提交工程化(钩子,提交信息commit message),npm修改版本,需要涉及到的包: husky,允许在git钩子中执行不同的脚步,如commitlint,eslint,prettier&#…...
DETR:一种新颖的端到端目标检测与分割框架
DETR:一种新颖的端到端目标检测与分割框架 摘要: 随着深度学习技术的发展,目标检测和图像分割任务取得了显著的进步。然而,传统的基于区域提名的方法在处理这些问题时存在一定的局限性。为此,Facebook AI Research&am…...
前端js面试知识点思维导图(脑图)
如果看着不清晰可以去https://download.csdn.net/download/m0_73761441/90058523访问下载,无需积分 使用百度脑图制作,可以一键导入下面的文本生成自己的脑图 js相关面试题、知识点 数据类型 1. 数据类型分类?分别包含ÿ…...
【Java基础入门篇】一、变量、数据类型和运算符
Java基础入门篇 一、变量、数据类型和运算符 1.1 变量 计算机中的数据表示方式是:“二进制(0/1)”,但是同时也可以兼容其他进制,例如八进制、十进制、十六进制等。 Java变量的本质是:存储在固定空间的内容,变量名是…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
