弗洛伊德龟兔赛跑算法(弗洛伊德判圈算法)

news/2024/3/29 19:41:49/文章来源:https://blog.csdn.net/weixin_41896770/article/details/129681143

弗洛伊德( 罗伯特・弗洛伊德)判圈算法(Floyd Cycle Detection Algorithm),又称龟兔赛跑算法(Tortoise and Hare Algorithm),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,以及判断环的起点与长度的算法。

昨晚刷到一个视频,来自油管的Joma Tech,视频本身挺有意思的,当然这哥们也很有意思,经常在油管发视频然后在FB就被辞职了,现就职于谷歌。

里面介绍了如何实现下面这个的算法,主要是视频内容很有意思,当然这里还是介绍里面出现的几个算法。

题目:找出数组中的重复数字,数组里只有一个重复的数字,可以重复多次。其中算法的要求是时间复杂度小于O(n²),空间复杂度是O(1)

题目是很简单,求解的办法也很多,有直接循环查找,为了提高效率还可以使用二分查找,视频中的前两个方法如下:

排序之后,相邻元素如果是相等即为重复数字。但运行的时间复杂度高,比较耗时。不能通过!

def findDuplicate1(nums):nums.sort()for i in range(1,len(nums)):if nums[i]==nums[i-1]:return nums[i]arr1=[1,3,4,2,2]
arr2=[8,1,3,4,2,4,5,4]print(findDuplicate1(arr1))#2
print(findDuplicate1(arr2))#4

使用字典或set来保存遍历数组里的值,然后判断是否已添加,如果有添加就说明是重复数值了。

这个虽然相较于上面的方法,时间缩短了,但是空间复杂度上来了,比较耗内存。不能通过!

def findDuplicate2(nums):seen={}for num in nums:if num in seen:return numseen[num]=Trueprint(findDuplicate2(arr1))#2
print(findDuplicate2(arr2))#4#或者set()也可以
def findDuplicate2_(nums):seen=set()for num in nums:if num in seen:return numseen.add(num)
print(findDuplicate2_(arr1))#2
print(findDuplicate2_(arr2))#4

接下来看下符合要求的算法,也就是下面介绍的龟兔算法。

当然这个题目还有一个限定条件,给定一个包含n + 1个整数的数组nums,其中每个整数都在1到n之间(包括),不然我给出的示例就会出现索引越界了,这样就可以使用这个龟兔赛跑的算法,也有人管叫快慢指针,有重复就形成闭环:

def findDuplicate_ok(nums):tortoise=nums[0]hare=nums[0]while True:tortoise=nums[tortoise]#龟hare=nums[nums[hare]]#兔if tortoise==hare:breakptr1=nums[0]ptr2=tortoisewhile ptr1!=ptr2:ptr1=nums[ptr1]ptr2=nums[ptr2]return ptr1arr1=[1,3,4,2,2]
arr3=[1,4,6,8,2,3,8,5,7]
print(findDuplicate_ok(arr1))#2
print(findDuplicate_ok(arr3))#8

时间复杂度:O(n),空间复杂度:O(1)

当然如果是初学者,会感觉到有点复杂,没关系,我们可以在龟(或兔或两者)的位置设置断点,然后步进,一步一步的看整个算法的执行流程就明白了,这个也是大家在需要进行调试或者了解一些变量的变化的最常见有效的方法。

不便调试的,我也将整个执行过程贴出来,方便观察:

数组:nums=[1,4,6,8,2,3,8,5,7]

第1次

第2次

第3次

第4次

第5次

nums[0]=1

nums[1]=4

nums[4]=2

nums[2]=6

nums[6]=8

nums[0]=1

nums[nums[1]]=2

nums[nums[2]]=8

nums[7]=5

nums[3]=8

当迭代到第5次的时候,两者相等了,于是就跳出循环,然后就通过指针找出重复的值

ptr1=1

nums[1]=4

nums[4]=2

nums[2]=6

nums[6]=8

ptr2=8

nums[8]=7

nums[7]=5

nums[5]=3

nums[3]=8

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

根据平均分来划分等级-课后程序(JavaScript前端开发案例教程-黑马程序员编著-第2章-课后作业)

【案例2-1】 根据平均分来划分等级 一、案例描述 考核知识点 switch语句 练习目标 掌握switch语句的使用。 需求分析 switch语句也是多分支语句,针对某个表达式的值做出判断,来决定执行哪一段代码,本案例用于实现根据输入的小明同学的5门课…

百度CTO王海峰:全栈AI技术加持,打造新一代大语言模型文心一言

3月16日,百度在北京总部召开新闻发布会,百度创始人、董事长兼首席执行官李彦宏和百度首席技术官王海峰出席,李彦宏展示了新一代知识增强大语言模型文心一言在文学创作、商业文案创作、数理逻辑推算、中文理解、多模态生成五个使用场景中的综合…

【linux】管道pipe(),dup()系统调用

int pipe(int p[2]) 函数作用:生成一个管道,将管道读端的文件标识符存到p[0]中,将管道写端的文件标识符存到p[1]中。返回值:若成功返回0,失败返回-1 管道的理解 如图,当创建完管道以后的父进程fork出两个子…

Python中模块是个啥

昨天有粉丝问我说,啥是模块?经常听别人口中提这个词,但就是不懂。 模块可以认为是一盒主题积木,通过它可以拼出某一主题的东西。这与之前介绍的函数不同,一个函数相当于一块积木,而一个模块中可以包括很多函…

【C++进阶】unordered_set和unordered_map的介绍及使用

文章目录unordered系列容器介绍unordered_setunordered_set的模板参数unordered_set的函数接口介绍unordered_set的重要接口的使用构造函数增删查迭代器的使用unordered_mapunordered_map的模板参数unordered_map的函数接口介绍unordered_map的重要接口的使用增删查改迭代器的使…

EMQ 南洋万邦云边一体化方案:激活数据潜力,打造智慧工业园区

在工业 4.0 的浪潮之中,全球制造业再度振兴和崛起,并经历着前所未有从流程驱动转向数据驱动的变革。 近年来,数智化绿色工厂正在成为制造业竞争力的主要驱动力,依托物联网、工业互联网,人工智能等先进制造技术的深度融合,智能工厂变得更高效、更灵活,拥有更高的交付韧性和成本…

解忧杂货铺(四):Hightec生成HEX方法+小功能开启

目录 1、概述 2、 4.6.6的生成方法 3 、HighTEC4.9.3的生成.hex方法 4、MAP文件生成方法 5、elf生成 6、编译优化 7、输出编译过程中的详细信息 8、快速定位内存 1、概述 本文章纯属整合,大部分属于外链,补充一下,后面是自己记录的了…

由浅入深之字符串的算法题(vs: chatGPT做算法)

背景俗话说,温故而知新。chatGPT效果太惊艳了!简直就是碾压的效果。但是还要有希望,先拾取,再创新。先了解,再超越吧。ps: 再刷最后一遍算法题思路。顺便基于chatGPT3.5感受一下大模型的魔力。字符串基础C/C每个字符串…

编程题]组队竞赛(Java实现)

🎉🎉🎉点进来你就是我的人了 博主主页:🙈🙈🙈戳一戳,欢迎大佬指点!人生格言:当你的才华撑不起你的野心的时候,你就应该静下心来学习! 欢迎志同道合的朋友一起加油喔🦾&am…

十七、队列

文章目录1、基本概念(队列实际上就是一个结构体,可以理解为就是一个数组)2、使用场景:任务间或任务与中断间传递数据3、使用队列的好处(1)休眠唤醒(2)提高CPU利用率4、队列的核心5、…

WebService简单入门

1. JAX-WS发布WebService 创建web工程 创建simple包,和server、client两个子包。正常情况下server和client应该是两个项目,这里我们只是演示效果,所以简化写到一个项目中: 1.1 创建服务类Server package simple.server;import ja…

JavaScript正则表达式知识拓展总结

JavaScript的正则表达式是前端中比较重要的部分,正则表达式主要用于字符串处理,表单验证等场合,实用高效。JavaScript中的正则表达式比起C#中的正则表达式要弱很多,但基本够用了。在js中定义正则表达式很简单,有两种方…

搭建SFTP服务安全共享文件,实现在外远程访问「内网穿透」

文章目录1.前言2.本地SFTP服务器搭建2.1.SFTP软件的下载和安装2.2.配置SFTP站点2.3.Cpolar下载和安装3.SFTP服务器的发布3.1.Cpolar云端设置3.2.Cpolar本地设置4.公网访问测试5.结语1.前言 现在的网络发达,个人电脑容量快速上升,想要保存的数据资料也越…

DRBG_InstantiateSeeded调试-1

public 参数解析: standardEKPolicy: 837197674484b3f81a90cc8d46a5d724fd52d76e06520b64f2a1da1b331469aa(32bytes) rawCmdBuf 命令数据: 800200000063000001314000000100000009400000090000010000000400000000003a0001000b000300720020837197674484b3f81a90cc8d46a5d724fd5…

Baumer工业相机堡盟相机如何使用PixelTransformation像素转换功能(像素转换功能的使用和优点以及行业应用)(C++)

项目场景 Baumer工业相机堡盟相机是一种高性能、高质量的工业相机,可用于各种应用场景,如物体检测、计数和识别、运动分析和图像处理。 Baumer的万兆网相机拥有出色的图像处理性能,可以实时传输高分辨率图像。此外,该相机还具…

银河麒麟v10系统硬盘挂载并配置yum软件源

一、查看磁盘 近期由于centos系统停止更新用户服务器要更换银河麒麟v10,拿到服务器后使用lsblk -f或fdisk -l命令查看磁盘名称 可以看到sdb200G就是要挂载的硬盘,还没有uuid需要初始化才可以挂载。 二、分区 分区命令: fdisk /dev/【你的…

QML- QML视觉元素类型

QML视觉元素类型一、概述一、图像类型三、共享视觉属性1. 不透明度和可见性2. 转换(转置)一、概述 对于最基本的视觉效果,Qt Quick提供了一个 Rectangle 类型来绘制矩形。这些矩形可以用颜色或垂直渐变来着色。 Rectangle 还可以在矩形上绘制…

QuestDb 基础使用

一、安装 Download QuestDB | QuestDB 可去官网直接下载对应版本,我这里是Windows版本 二、运行 找到Bin目录运行 管理员Cmd,输入 questDb.exe,即可运行,默认webConsole端口 9000,可在bin下 server.config去修改。 效果如下 …

Mac安装Nacos

参考链接: https://nacos.io/zh-cn/docs/quick-start.html 文章目录Nacos安装下载和解压启动和关闭Nacos什么是nacos?Nacos架构基本架构及概念逻辑架构及其组件介绍领域模型数据模型服务领域模型配置领域模型类视图Nacos安装 下载和解压 从链接中下载最新的版本 …

Vue基础25之路由第四节

Vue基础25路由编程式路由导航Home.vue(去掉两个router-line的replace)HomeMessage.vueBanner.vue总结缓存路由组件Home.vueHomeNews.vueHomeMessage.vue总结两个新的生命周期钩子HomeNews.vueHomeMessage.vueHome.vue总结全局路由守卫路由前置守卫src/router/index.js路由后置守…