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

网站开发公司 优帮云今日nba比赛直播

网站开发公司 优帮云,今日nba比赛直播,平面图在线设计,商品网站怎么做的问题描述 给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 null。 将链表问题转化为数学问题 状态序列与循环 我们可以将链表节点视为状态,每个节点的 next 指针代表状态转移函数 f f f。从头节点开始,我…

问题描述

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

http://www.ritt.cn/news/9865.html

相关文章:

  • 济南网站免费制作新闻网最新消息
  • 漂亮的个人网站搜狗搜索网页版
  • 谁会在西安做网站的吗网络营销方法有哪些举例
  • 合肥市住房和城乡建设局seo定义
  • 网站建设常用视频格式郑州seo顾问热狗hotdoger
  • 做网站怎么移动图片杭州优化关键词
  • 网站建设公司net2006引擎搜索技巧
  • 完美建设工程有限公司网站seo排名
  • 用easyui皮肤做漂亮的网站雅虎搜索引擎
  • 手机网站建设比较好的公司互联网营销策划案
  • 做网站怎样安全采集营销策划方案模板范文
  • 海南网站建设中心公司网站模板设计
  • wordpress的后台链接seo优化推广多少钱
  • 网站后台密码存在哪域名备案查询站长工具
  • 福田网站建设哪家好怎么推广网页
  • 做网站分pc端和移动端的吗seo关键词推广
  • 搭建钓鱼网站教程网络推广的调整和优化
  • 门户网站建设公司案例新闻营销发稿平台
  • h5网站模板开发app推广策略
  • 类似淘宝网站建设费用seo推广有哪些
  • 建设公司网站的会计分录广告网
  • 织梦装修网站模板2345网址导航官方网站
  • 263企业邮箱登陆入囗广东网站seo营销
  • 北京 公司网站制作一份完整的营销策划方案
  • 长治一般建一个网站需要多少钱学生班级优化大师
  • 平台网站怎么做的网站建设对企业品牌价值提升的影响
  • 四川省建设招标网站首页查域名备案信息查询
  • 树莓派网站建设google代理
  • 在门户网站做产品单页多少钱一天seo排名优化软件免费
  • 做云购网站网络营销有哪些例子