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

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

弗洛伊德( 罗伯特・弗洛伊德)判圈算法(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

相关文章:

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

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

nodejs篇 express(1)

文章目录前言express介绍安装RESTful接口规范express的简单使用一个最简单的服务器,仅仅只需要几行代码便可以实现。restful规范的五种接口类型请求信息req的获取响应信息res的设置中间件的使用自定义中间件解决跨域nodejs相关其它内容前言 express作为nodejs必学的…...

Java实习生------Redis常见面试题汇总(AOF持久化、RDB快照、分布式锁、缓存一致性)⭐⭐⭐

“年轻人,就要勇敢追梦”🌹 参考资料:图解redis 目录 谈谈你对AOF持久化的理解? redis的三种写回策略是什么? 谈谈你对AOF重写机制的理解?AOF重写机制的具体过程? 谈谈你对RDB快照的理解&a…...

seata服务搭建

它支持两种存储模式,一个是文件,一个是数据库,下面我们分别介绍一下这两种配置nacos存储配置,注意如果registry.conf中注册和配置使用的是file,就会去读取file.config的配置,如果是nacos则通过nacos动态读取…...

Kafka和RabbitMQ有哪些区别,各自适合什么场景?

目录标题1. 消息的顺序2. 消息的匹配3. 消息的超时4. 消息的保持5. 消息的错误处理6. 消息的吞吐量总结1. 消息的顺序 有这样一个需求:当订单状态变化的时候,把订单状态变化的消息发送给所有关心订单变化的系统。 订单会有创建成功、待付款、已支付、已…...

用Pytorch构建一个喵咪识别模型

本文参加新星计划人工智能(Pytorch)赛道:https://bbs.csdn.net/topics/613989052 目录 一、前言 二、问题阐述及理论流程 2.1问题阐述 2.2猫咪图片识别原理 三、用PyTorch 实现 3.1PyTorch介绍 3.2PyTorch 构建模型的五要素 3.3PyTorch 实现的步骤 3.3.…...

QT搭建MQTT开发环境

QT搭建MQTT开发环境 第一步、明确安装的QT版本 注意: 从QT5.15.0版本开始,官方不再提供离线版安装包,除非你充钱买商业版。 而在这里我使用的QT版本为5.15.2,在线安装了好久才弄好,还是建议使用离线安装的版本 在这里…...

Python3,5行代码,生成自动排序动图,这操作不比Excel香?

5行代码生成自动排序动图1、引言2、代码实战2.1 pynimate介绍2.2 pynimate安装2.3 代码示例3、总结1、引言 小屌丝:鱼哥,听说你的excel段位又提升了? 小鱼:你这是疑问的语气? 小屌丝:没有~ 吧… 小鱼&…...

【Java SE】变量的本质

目录一. 前言二. 变量(variable)2.1 性质2.2 变量类型2.2.1 核心区别2.3 变量的使用三. 总结一. 前言 一天一个Java小知识点,助力小伙伴更好地入门Java,掌握更深层次的语法。 二. 变量(variable) 2.1 性质 变量本质上就是代表一个”可操作的存储空间”…...

【Android笔记85】Android之使用Camera和MediaRecorder录制视频

这篇文章,主要介绍Android之使用Camera和MediaRecorder录制视频。 目录 一、录制视频 1.1、案例运行效果 1.2、创建Camera对象 1.3、创建MediaRecorder对象...

MySQL集群搭建与高可用性实现:掌握主从复制、多主复制、负载均衡和故障切换技术,让你的MySQL数据库永不宕机!

MySQL集群和高可用性MySQL是一款广泛使用的关系型数据库管理系统,常用于Web应用和企业级应用中。为了提高MySQL的可用性,我们可以通过搭建MySQL集群和实现高可用性来保障数据的稳定性和可靠性。本文将介绍如何搭建MySQL集群和实现高可用性,包…...

收到6家大厂offer,我把问烂了的《Java八股文》打造成3个文档。共1700页!!

前言大家好,最近有不少小伙伴在后台留言,近期的面试越来越难了,要背的八股文越来越多了,考察得越来越细,越来越底层,明摆着就是想让我们徒手造航母嘛!实在是太为难我们这些程序员了。这不&#…...

多线程 (六) 单例模式

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

Docker入门到放弃笔记之容器

1、启动容器1.1容器hello world1.2 容器bash终端1.3 后台运行容器是 Docker 三大核心概念之一,其余两个是镜像与仓库。本文主讲容器。简单的说,容器是独立运行的一个或一组应用,以及它们的运行态环境。对应的,虚拟机可以理解为模拟…...

项目二 任务三 训练5 交换机的HSRP技术

在“项目二 任务三 训练4 交换机的DHCP技术”基础上继续完成下列操作: 1、二层交换机50-2的配置 50-2>en 50-2#conf t Enter configuration commands, one per line. End with CNTL/Z. 50-2(config)#int 50-2(config)#interface g 50-2(config)#interface gigab…...

计算机网络复习重点

文章目录计算机网络复习重点第一章 计算机网络和因特网概念与应用1、什么是因特网2、协议protocol3、入网方式4、物理媒介5、数据交换模式6、延时与丢包什么时候发生延时?延时的类型丢包何时发生7、协议层次与模型因特网协议栈TCP / IP模型ISO/OSI参考模型协议数据单…...

算法基础---基础算法

文章目录 快速排序归并排序二分 整数二分浮点数二分高精度 高精度加法高精度减法高精度乘法高精度除法前缀和 一维前缀和二维前缀和差分 一维差分二维差分双指针位运算离散化区间合并一、快速排序 思想:1.首先确定一个分界点(随机取任意一点为…...

linux中写定时任务

场景:我们生产环境中有大量的日志记录,但是我们的磁盘没有太大,需要定时清理磁盘 文章目录crond 定时任务详解安装定时任务crontab服务启动与关闭crontab操作crontab 命令test.sh查看日志丢弃linux中的执行日志Linux进入nano模式方式一方式二…...

2023.3.21

6&#xff1a;有序数组中找到num // arr保证有序&#xff0c;在arr数组中寻找num&#xff0c;二分查找public static boolean find(int[] arr, int num) {if(arr null || arr.length 0) {return false;}int L 0;int R arr.length - 1;while (L < R) {int mid (L R) /…...

制作数据库框架

一 利用前端条件组装sql与查询条件的集合public void handle() throws Exception{Map<String,String> requestMap new HashMap();String fromdate requestMap.get("fromdate");String todate requestMap.get("todate");String resultcode reque…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...