Python面试宝典第4题:环形链表
题目
给你一个链表的头节点 head ,判断链表中是否有环。如果存在环 ,则返回 true 。 否则,返回 false 。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
示例:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
快慢指针法
快慢指针法,也叫Floyd判圈法,是解决链表中环检测问题的经典算法。其核心思想是使用两个指针,一个快指针每次移动两个节点,一个慢指针每次移动一个节点。如果链表中存在环,快慢指针最终会在环中的某一点相遇。若不存在环,快指针会先到达链表尾部。使用快慢指针法求解本题的主要步骤如下。
1、初始化指针。开始时,定义两个指针,一个快指针(fast)和一个慢指针(slow),均指向链表的头节点。
2、移动指针。每次迭代时,慢指针(slow)向前移动一步,快指针(fast)向前移动两步。如果链表中存在环,由于快指针移动速度是慢指针的两倍,最终快指针会追上慢指针。
3、终止条件。如果链表中没有环,快指针会首先到达链表的尾部(None),这时可以确定链表无环。相反,如果快慢指针相遇,则表明链表中存在环。
根据上面的算法步骤,我们可以得出下面的示例代码。
class ListNode:def __init__(self, x):self.val = xself.next = Nonedef create_linked_list(length, pos = -1):if length < 1 or (pos != -1 and (pos < 0 or pos >= length)):return Nonehead = ListNode(0)current = headcycle_node = Nonefor i in range(1, length + 1):new_node = ListNode(i)current.next = new_nodecurrent = new_nodeif i == pos + 1:cycle_node = new_node# 只有当pos有效且不为-1时,才创建环if cycle_node:current.next = cycle_node# 返回真正的头节点,忽略初始的0节点return head.nextdef has_cycle_fast_slow_pointer(head):if head is None or head.next is None:return Falseslow = headfast = head.nextwhile fast is not None and fast.next is not None:if slow == fast:return Trueslow = slow.nextfast = fast.next.nextreturn False# 创建有环链表
head_with_cycle = create_linked_list(4, 1)
# 输出: True
print(has_cycle_fast_slow_pointer(head_with_cycle))# 创建无环链表
head_no_cycle = create_linked_list(4, -1)
# 输出: False
print(has_cycle_fast_slow_pointer(head_no_cycle))
哈希表法
哈希表法利用数据结构中的哈希表来记录每个访问过的节点。由于哈希表的查找效率非常高,平均时间复杂度为O(1),故我们可以在遍历链表的同时,将每个访问过的节点添加到哈希表中。当发现某个节点已经被访问过,即该节点存在于哈希表中时,则可断定链表中存在环。使用哈希表法求解本题的主要步骤如下。
1、初始化。创建一个空的哈希表,在Python中,通常是集合set。
2、遍历链表。从链表头开始遍历,对于每一个访问到的节点,执行以下操作。
(1)检查当前节点是否已经在哈希表中。
(2)如果不在,将当前节点添加到哈希表中,并继续遍历下一个节点。
(3)如果在哈希表中发现了当前节点,说明存在环,直接返回True。
3、遍历结束。如果遍历完整个链表都没有发现重复的节点,则说明链表中没有环,返回False。
根据上面的算法步骤,我们可以得出下面的示例代码。
def has_cycle_hashset(head):visited_nodes = set()while head is not None:# 如果节点已经在集合中,说明有环if head in visited_nodes:return Truevisited_nodes.add(head)head = head.next# 遍历结束,没有发现环return False# 创建有环链表
head_with_cycle = create_linked_list(4, 1)
# 输出: True
print(has_cycle_hashset(head_with_cycle))# 创建无环链表
head_no_cycle = create_linked_list(4, -1)
# 输出: False
print(has_cycle_hashset(head_no_cycle))
总结
快慢指针法不需要额外的空间,时间复杂度为O(n),其中n是链表中的节点数量。哈希表法则提供了另一种思路,虽然它需要额外的O(n)空间,但优点是实现直观,易于理解和编码。
在实际应用中,如果对空间复杂度有严格要求,推荐使用快慢指针法。如果空间不是问题,而对代码的简洁性和直观性有更高要求,哈希表法也是一个不错的选择。
💡 如果想阅读最新的文章,或者有技术问题需要交流和沟通,可搜索并关注微信公众号“希望睿智”。
相关文章:
Python面试宝典第4题:环形链表
题目 给你一个链表的头节点 head ,判断链表中是否有环。如果存在环 ,则返回 true 。 否则,返回 false 。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环…...
Kubernetes (K8s) 底层原理
Kubernetes (K8s) 的底层原理涉及多个关键组件和概念,确保容器化应用程序的自动化部署、扩展和管理。以下是 Kubernetes 的底层原理及其关键组件的详细描述。 核心组件 Etcd 功能:分布式键值存储,用于存储集群的所有数据,包括配置…...
解析Kotlin中的委托(包括类委托,属性委托)【笔记摘要】
1.委托模式 委托模式:操作对象不会去处理某段逻辑,而是会把工作委托给另外一个辅助对象去处理。 例如我们要设计一个自定义类的来实现Set,可以将该实现委托给另一个对象: class MySet<T> (val helperSet: HashSet<T>…...
vue3+ts+uniapp+vite+pinia项目配置
开发环境: node >18,npm >8.10.2,vue < 3.2.31 安装项目 npx degit dcloudio/uni-preset-vue#vite-ts vue3-uniapp 1、引入样式规范 npm add -D eslint eslint-config-airbnb-base eslint-config-prettier eslint-import-resolv…...
大数据开发语言 Scala(四):面向对象编程
目录 1. 概述 2. 面向对象编程的基本概念 2.1 类和对象 2.2 继承和多态 2.3 封装和访问控制 3. 面向对象编程在大数据开发中的应用 3.1 Spark中的面向对象编程 3.2 面向对象编程在数据清洗和预处理中 3.3 面向对象编程在机器学习中的应用 4. 面向对象编程的高级特性 …...
C++ //练习 14.31 我们的StrBlobPtr类没有定义拷贝构造函数、赋值运算符及析构函数,为什么?
C Primer(第5版) 练习 14.31 练习 14.31 我们的StrBlobPtr类没有定义拷贝构造函数、赋值运算符及析构函数,为什么? 环境:Linux Ubuntu(云服务器) 工具:vim 解释: 因为…...
通配符和正则表达式之间的关系
通配符和正则表达式(正则)都是用于匹配字符串的工具,但它们的复杂性和用途有所不同。下面是它们之间的主要关系和区别: 通配符 通配符主要用于简单的模式匹配,常见于文件系统操作中,例如在命令行中查找文…...
GY-30光照传感器软件I2C方式驱动代码,基于STM32Cube
GY-30光照传感器的具体资料可以去淘宝搜索然后问卖家要,网上也有,所以这里我就不多嘴了。 VCC连接3到5伏电压,根据文件开头的描述在STM32CubeMX中配置好外设。 STM32Cube开发方式就是4个字“简单直接”,直接上代码。 gy30.h #…...
双相元编程:一种新语言设计方法
本文讨论了编程语言的一种趋势,即允许相同的语法表达 在两个不同阶段或环境(上下文)中执行的计算同时保持跨阶段(上下文)的一致行为。这些阶段通常在时间上(运行时间)或空间上(运行…...
基于SpringBoot校园外卖配送系统设计和实现(源码+LW+调试文档+讲解等)
💗博主介绍:✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者,博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌💗 🌟文末获取源码数据库🌟 感兴趣的可以先收藏起来,…...
茗鹤APS高级计划排程系统,在集团多工厂协同生产下的应用
随着业务规模的扩大和市场的全球化,越来越多的企业选择“总部多工厂基地”的模式,此种模式大幅提升企业的产能与产量,有效分散风险。然后,与之而来的是对企业的管理提出更高的管理要求。多个生产基地不仅面临集团下发的周期性计划…...
分享六款免费u盘数据恢复工具,U盘恢复工具集合【工具篇】
U盘里面的数据丢失了怎么找回?随着数字化时代的深入发展,U盘已成为我们日常生活中不可或缺的数据存储工具。然而,由于各种原因,如误删除、格式化、病毒攻击等,U盘中的数据可能会丢失,给用户带来极大的困扰。…...
Linux 的启动流程
第一步、加载内核 操作系统接管硬件以后,首先读入 /boot 目录下的内核文件。 以我的电脑为例,/boot 目录下面大概是这样一些文件: $ ls /bootconfig-3.2.0-3-amd64config-3.2.0-4-amd64grubinitrd.img-3.2.0-3-amd64initrd.img-3.2.0-4-amd6…...
思维导图插件--jsMind的使用
vue引入jsmind(右键菜单)_jsmind.menu.js-CSDN博客 第一版 vue-JsMind思维导图实现(包含鼠标右键自定义菜单)_jsmind 右键菜单-CSDN博客 // 新增节点addNode() {console.log(this.get_selected_nodeid());this.get_selected_…...
mac上使用finder时候,显示隐藏的文件或者文件夹
默认在finder中是不显示隐藏的文件和文件夹的,但是想创建.gitignore文件,并向里面写入内容,即便是打开xcode也是不显示这几个隐藏文件的,那有什么办法呢? 使用快捷键: 使用finder打开包含隐藏文件的文件夹…...
泰雷茲具有首个通过FIPS 140-3 三级认证的HSMs
泰雷兹LunaHsm是业界首款通过FIPS140-33级认证的解决方案,安策引进泰雷兹HSM产品可以帮助您满足您的数据安全合规性需求,阻力企业提高竞争力。 安策提供泰雷茲ThalesLunaHSMs成为首个通过FIPS140-3三级认证的硬件安全模块图 我们很高兴地宣布,…...
美术馆预约小程序的设计
管理员账户功能包括:系统首页,个人中心,展品信息管理,管理员管理,用户管理,美术馆管理,基础数据管理,论坛管理 微信端账号功能包括:系统首页,美术馆ÿ…...
序列化Serializable
一、传输对象的方式 将对象从内存传输到磁盘进行保存,或者进行网络传输,有两种方式: 实现Serializable接口,直接传输对象转成json字符串后,进行字符串传输 二、直接传输对象 implements Serializable Data Equal…...
编写静态库
一、静态库 1.制作完成整体目录结构 2.首先创建mymath.c和mymath.h 3.编写Makefile 4.创建测试的main函数 test文件夹 先把lib移到test文件夹里面 4.编译链接 gcc main.c -I ./lib/include/ -L ./lib/mymathlib/ -l mymath 5.形成可执行程序a.out 要是不想执行第四步那么麻烦…...
hive的表操作
常用的hive命令 切换数据库use test;查询表的建表信息show create table 数据库名称.表名;查看表的类型信息desc formatted 数据库名称.表名; 删除内部表 drop table 数据库名称.表名; 先启动hdfs ,mysql , hiveservice2,beeline CREATE [EX…...
基于多视点编码光场的全景三维重建方法
欢迎关注GZH《光场视觉》 摘要:在基于光场的一系列应用中,目标的三维重建是基础且关键的任务。普通光场只能重建单一视角而无法重建全景,并且在纹理特征匮乏的区域也无法生成准确的三维信息。针对以上问题,提出一种基于多视点编码…...
Spring Boot中的分布式文件系统
Spring Boot中的分布式文件系统 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天,我们将探讨如何在Spring Boot中实现分布式文件系统的搭建和应用…...
three.js地理坐标系有哪些,和屏幕坐标系的转换。
坐标系很好理解,就是点线面体的位置,一个点是一个坐标,一条线段2个坐标,一个矩形四个坐标,一个立方体8个坐标,three.js面对的是三维空间,屏幕则是二维的,这就面临着转换问题…...
聊聊C++20的三向比较运算符 `<=>`
C20标准引入了许多新特性,其中之一是三向比较运算符 <>,也被称为太空船运算符。这个新运算符为C程序员提供了一种全新的比较对象的方式,它能有效简化比较逻辑,避免编写多个比较运算符重载的情况。 为什么需要三向比较运算符…...
CVE-2024-0603 漏洞复现
CVE-2024-0603 源码:https://gitee.com/dazensun/zhicms 开题: CVE-2024-0603描述:ZhiCms up to 4.0版本的文件app/plug/controller/giftcontroller.php中存在一处未知漏洞。攻击者可以通过篡改参数mylike触发反序列化,从而远程…...
西部智慧健身小程序+华为运动健康服务
1、 应用介绍 西部智慧健身小程序为用户提供一站式全流程科学健身综合服务。用户通过登录微信小程序,可享用健康筛查、运动风险评估、体质检测评估、运动处方推送、个人运动数据监控与评估等公益服务。 2、 体验介绍西部智慧健身小程序华为运动健康服务核心体验如…...
Spring Boot中如何处理异步任务
Spring Boot中如何处理异步任务 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨在Spring Boot应用中如何处理异步任务,以提升系统的性…...
数字化精益生产系统--RD研发管理系统
R&D研发管理系统是一种用于管理和监督科学研究和技术开发的软件系统,其设计和应用旨在提高企业研发活动的效率、质量和速度。以下是对R&D研发管理系统的功能设计:...
鱼眼相机 去畸变
目录 枕形畸变和去枕形畸变 去枕形畸变失败 枕形畸变和去枕形畸变 import cv2 import numpy as np import matplotlib.pyplot as plt# 创建一个带网格的原始图像 def create_grid(image_size512, grid_size20):image np.zeros((image_size, image_size, 3), dtypenp.uint8)…...
DC/AC电源模块:为智能家居设备提供恒定的电力供应
BOSHIDA DC/AC电源模块:为智能家居设备提供恒定的电力供应 DC/AC电源模块是一种常见的电源转换器,它将直流电源(DC)转换为交流电源(AC),为智能家居设备提供恒定的电力供应。在智能家居系统中&a…...
小红书运营教程02
小红书大致会分享10篇左右。微博、抖音、以及视频剪辑等自媒体运营相关技能以及运营教程相关会陆续的进行分享。 上次分享涉及到的对比,母婴系列,或者可以说是服装类型,不需要自己过多的投入,对比知识类博主来说,自己将知识讲述出来,然后要以此账号进行变现就比较麻烦,…...
k8s自动清理节点服务
要在 Kubernetes 中实现当某个节点的 CPU 或内存使用超过 90% 时清理该节点上的服务,你可以使用以下几种方法: 自定义脚本和 cron job:编写一个脚本监控节点的资源使用情况,并在超过阈值时触发清理操作。使用 DaemonSet 运行监控…...
JS如何把年月日转为时间戳
在JavaScript中,将年月日(通常表示为一个字符串或者分别的年、月、日数字)转换为时间戳(即Unix时间戳,是自1970年1月1日(UTC/GMT的午夜)开始所经过的秒数,不考虑闰秒)可以…...
【YOLOv5进阶】——引入注意力机制-以SE为例
声明:笔记是做项目时根据B站博主视频学习时自己编写,请勿随意转载! 一、站在巨人的肩膀上 SE模块即Squeeze-and-Excitation 模块,这是一种常用于卷积神经网络中的注意力机制!! 借鉴代码的代码链接如下&a…...
【C++题解】1456. 淘淘捡西瓜
问题:1456. 淘淘捡西瓜 类型:贪心 题目描述: 地上有一排西瓜,每个西瓜都有自己的重量。淘淘有一个包,包的容量是固定的,淘淘希望尽可能在包里装更多的西瓜(当然要装整个的,不能切开…...
用Python读取Word文件并提取标题
前言 在日常工作中,我们经常需要处理Word文档,特别是从中提取关键信息,如标题、段落等。今天,我们将利用Python来实现这一功能,并为大家提供一段完整的代码示例。 准备工作 首先,你需要安装python-docx库…...
Windows编程上
Windows编程[上] 一、Windows API1.控制台大小设置1.1 GetStdHandle1.2 SetConsoleWindowInfo1.3 SetConsoleScreenBufferSize1.4 SetConsoleTitle1.5 封装为Innks 2.控制台字体设置以及光标调整2.1 GetConsoleCursorInfo2.2 SetConsoleCursorPosition2.3 GetCurrentConsoleFon…...
BiTCN-Attention一键实现回归预测+8张图+特征可视化图!注意力全家桶再更新!
声明:文章是从本人公众号中复制而来,因此,想最新最快了解各类智能优化算法及其改进的朋友,可关注我的公众号:强盛机器学习,不定期会有很多免费代码分享~ 目录 原理简介 数据介绍 结果展示 全家桶代码目…...
zoom缩放问题(关于ElementPlus、Echarts、Vue3draggable等组件偏移问题)
做了一个项目下来,由于整体界面偏大,采取了缩放90%,导致很多组件出现偏移问题,以下我会把我遇到的各种组件偏移问题依次进行描述解答: ElementPlus选择器下拉偏移 <template><el-select :teleported"f…...
【后端面试题】【中间件】【NoSQL】MongoDB的配置服务器、复制机制、写入语义和面试准备
MongoDB的配置服务器 引入了分片机制之后,MongoDB启用了配置服务器(config server) 来存储元数据,这些元数据包括分片信息、权限控制信息,用来控制分布式锁。其中分片信息还会被负责执行查询mongos使用。 MongoDB的配置服务器有一个很大的优…...
视频监控汇聚平台LntonCVS视频监控业务平台具体有哪些功能?
LntonCVS视频监控平台是一款基于H5技术开发的专业安防视频监控产品,旨在为安防视频监控行业提供全面的解决方案。以下是平台的主要功能和特点: 1. 统一接入管理: - 支持国内外各种品牌、协议和设备类型的监控产品统一接入管理。 - 提供标准的…...
我不小心把生产的数据改错了!同事帮我用MySQL的BinLog挽回了罚款
之前在生产做修改数据的时候不小心改错了一行数据,本来以为会被通报批评,但是同事利用binlog日志查看到了之前的旧数据,并且帮我回滚了,学到了,所以写了一篇binlog的文章分享给大家。 MySQL的Binary Log(简…...
Windows系统安装NVM,实现Node.js多版本管理
目录 一、前言 二、NVM简介 三、准备工作 1、卸载Node 2、创建文件夹 四、下载NVM 五、安装NVM 六、使用NVM 1、NVM常用操作命令 2、查看NVM版本信息 3、查看Node.js版本列表; 4、下载指定版本Node.js 5、使用指定版本Node.js 6、查看已安装Node.js列…...
k8s部署单节点redis
一、configmap # cat redis-configmap.yaml apiVersion: v1 kind: ConfigMap metadata:name: redis-single-confignamespace: redis data:redis.conf: |daemonize nobind 0.0.0.0port 6379tcp-backlog 511timeout 0tcp-keepalive 300pidfile /data/redis-server.pidlogfile /d…...
云微客矩阵系统:如何利用智能策略引领营销新时代?
近些年,短视频行业的风头一时无二,大量的商家和企业进驻短视频赛道,都或多或少的实现了实体门店的流量增长。虽然说现在短视频的门槛在逐步降低,但是迄今为止依旧有很多人在短视频剪辑面前望而却步。 最近在短视频营销领域&#x…...
嵌入式Linux系统编程 — 6.3 kill、raise、alarm、pause函数向进程发送信号
目录 1 kill函数 1.1 kill函数介绍 1.2 示例程序 2 raise函数 2.1 raise函数介绍 2.2 示例程序 3 alarm函数 3.1 alarm函数介绍 3.2 示例程序 4 pause函数 4.1 pause函数介绍 4.2 示例程序 与 kill 命令相类似, Linux 系统提供了 kill()系统调用&#…...
Swoole实践:如何使用协程构建高性能爬虫
随着互联网的普及,web爬虫已经成为了一个非常重要的工具,它可以帮助我们快速地抓取所需要的数据,从而降低数据获取成本。在爬虫的实现中,性能一直是一个重要的考虑因素。swoole是一款基于php的协程框架,它可以帮助我们…...
基于人脸68特征点识别的美颜算法(一) 大眼算法 C++
1、加载一张原图,并识别人脸的68个特征点 cv::Mat img cv::imread("5.jpg");// 人脸68特征点的识别函数vector<Point2f> points_vec dectectFace68(img);// 大眼效果函数Mat dst0 on_BigEye(800, img, points_vec);2、函数 vector<Point2f&g…...
算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice
大侠幸会,在下全网同名「算法金」 0 基础转 AI 上岸,多个算法赛 Top 「日更万日,让更多人享受智能乐趣」 抱个拳,送个礼 在算法模型构建中,我们经常需要计算样本之间的相似度,通常的做法是计算样本之间的距…...
项目实战--Spring Boot大数据量报表Excel优化
一、项目场景 项目中要实现交易报表,处理大规模数据导出时,出现单个Excel文件过大导致性能下降的问题,需求是导出大概四千万条数据到Excel文件,不影响正式环境的其他查询。 二、方案 1.使用读写分离,查询操作由从库…...