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

环形链表系列导学

问题描述

给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 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 k1)
距离关系
  • 慢指针走的总距离
    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

推导步骤
  1. 建立等式
    a + c + k × b = 2 × ( a + c ) a + c + k \times b = 2 \times (a + c) a+c+k×b=2×(a+c)

  2. 化简
    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+2cac
    k × b = a + c k \times b = a + c k×b=a+c

  3. 得出关系式
    a + c = k × b a + c = k \times b a+c=k×b

寻找环的入口
  • 快指针走了 a a a 步到达环入口
  • 慢指针从相遇点再走 b − c b - c bc 步也到达环入口

因为:
b − c = b − ( k × b − a ) = − ( k − 1 ) × b + a b - c = b - (k \times b - a) = - (k - 1) \times b + a bc=b(k×ba)=(k1)×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×bc=k×ba=1×43=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图像彩色数字化

效果展示&#xff1a; 目录结构&#xff1a; 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&#xff0c;构成多边形来挖洞。 其次就是xyz法向量挖洞 clippingPlanes: new this.ffCesium.Cesium.ClippingPlaneCollection({unionClippingRegions: true, // true 表示多个切割面能合并为一个有效的…...

docker 僵尸进程问题

docker僵尸进程 子进程结束后&#xff0c;父进程没有回收该进程资源&#xff08;父进程可能没有wait&#xff09;&#xff0c;子进程残留资源存放与内核中&#xff0c;就变为僵尸进程(zombie) 场景分析&#xff1a;python脚本A中执行B应用&#xff0c;将A部署在docker中&#…...

微软要求 Windows Insider 用户试用备受争议的召回功能

拥有搭载 Qualcomm Snapdragon 处理器的 Copilot PC 的 Windows Insider 计划参与者现在可以试用 Recall&#xff0c;这是一项臭名昭著的快照拍摄 AI 功能&#xff0c;在今年早些时候推出时受到了很多批评。 Windows 营销高级总监 Melissa Grant 上周表示&#xff1a;“我们听…...

husky,commit规范,生成CHANGELOG.md,npm发版

项目git提交工程化&#xff08;钩子&#xff0c;提交信息commit message&#xff09;&#xff0c;npm修改版本&#xff0c;需要涉及到的包&#xff1a; husky&#xff0c;允许在git钩子中执行不同的脚步&#xff0c;如commitlint&#xff0c;eslint&#xff0c;prettier&#…...

DETR:一种新颖的端到端目标检测与分割框架

DETR&#xff1a;一种新颖的端到端目标检测与分割框架 摘要&#xff1a; 随着深度学习技术的发展&#xff0c;目标检测和图像分割任务取得了显著的进步。然而&#xff0c;传统的基于区域提名的方法在处理这些问题时存在一定的局限性。为此&#xff0c;Facebook AI Research&am…...

前端js面试知识点思维导图(脑图)

如果看着不清晰可以去https://download.csdn.net/download/m0_73761441/90058523访问下载&#xff0c;无需积分 使用百度脑图制作&#xff0c;可以一键导入下面的文本生成自己的脑图 js相关面试题、知识点 数据类型 1. 数据类型分类&#xff1f;分别包含&#xff…...

【Java基础入门篇】一、变量、数据类型和运算符

Java基础入门篇 一、变量、数据类型和运算符 1.1 变量 计算机中的数据表示方式是&#xff1a;“二进制(0/1)”&#xff0c;但是同时也可以兼容其他进制&#xff0c;例如八进制、十进制、十六进制等。 Java变量的本质是&#xff1a;存储在固定空间的内容&#xff0c;变量名是…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...