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

【力扣每日一题】2023.7.30 环形链表2

题目:

示例:

分析:

这道题属于是那种知道解法就很简单,不知道解法就很难独立想出来的那种,我们只需要稍微记住这类题的固定解法就可以。

所以接下来我先说解法,再解释为什么解法可以解出来。

那么我们都知道使用快慢指针可以找出一个链表是否有环(不知道的去看看我昨天的每日一题题解),我们需要找出这个环的路口,我们在快慢指针相遇的时候就可以判断出链表有环,并且开始寻找。

我们将快指针移动回链表的开头,并且将快指针的速度调整为每次移动一格,然后再让快慢指针再次移动,直到它们相遇,相遇的位置就是环的入口。

这看起来有些不可思议是吗,怎么会这么简单,而且怎么就可以知道它们再次相遇的点就是环入口了,小朋友你是否有很多问号???

那么这涉及到了数学,因此这类题我的建议就是记住对应的模板,不要深究怎么样才可以在下次遇到类似的题目时自己可以从零开始推导出来,这不是普通人能干的

首先我们把链表开头到环入口的这段距离称为A,把环入口到快慢指针第一次相遇的地方的这段距离称为B,把快慢指针第一次相遇的地方直走走回环的入口的这段距离称为C,接下来可以开始推导了。

我们知道,快指针走过的的路程等于A+B+C+B,而慢指针走过的路程等于A+B。

我们又知道,每次快指针移动两格,慢指针移动一格,因此快指针走过的路程是慢指针的两倍。

我们就可以得到这样的式子:

A+B+C+B = 2*(A+B) = A+A+B+B

 化简一下就变成了:

C=A

 神奇吗同志们,从链表到环入口的距离(A)就等于在快慢指针第一次相遇的地方再次走到环入口,因此我们之前的操作就可以得到解释了,让慢指针接着走,然后让快指针调整速度以后从头开始走,走到它们第二次相遇,那就是环的入口了。

代码:

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head==nullptr) return nullptr;//快慢指针ListNode* fast=head;ListNode* slow=head;while(fast!=nullptr && fast->next!=nullptr){//快指针每次移动两次,慢指针每次移动一次slow=slow->next;fast=fast->next->next;//如果相遇则是有环,开始寻找入口if(fast==slow){fast=head;while(fast!=slow){fast=fast->next;slow=slow->next;}return fast;}}return nullptr;}
};

相关文章:

【力扣每日一题】2023.7.30 环形链表2

题目: 示例: 分析: 这道题属于是那种知道解法就很简单,不知道解法就很难独立想出来的那种,我们只需要稍微记住这类题的固定解法就可以。 所以接下来我先说解法,再解释为什么解法可以解出来。 那么我们都…...

Flink状态的理解

Flink是一个带状态的数据处理系统;系统在处理数据的过程中,各算子所记录的状态会随着数据的处理而不断变化; 1. 状态 所谓状态State,一般指一个具体的 Task 的状态,即线程处理过程中需要保存的历史数据或历史累计数据…...

6.3.tensorRT高级(1)-yolov5模型导出、编译到推理(无封装)

目录 前言1. YOLOv5导出2. YOLOv5推理3. 补充知识总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程,之前有看过一遍,但是没有做笔记,很多东西也忘了。这次重新撸一遍,顺便记记笔记。 本次课程学习 tensorRT 高级-yolov5模…...

如何利用设备数字化平台推动精益制造?

人工智能驱动技术的不断发展,尤其是基于机器学习的预测分析工具的使用,为制造业带来了全新的效率和价值水平。一直以来,精益生产(也叫精益制造)在制造业中扮演着重要角色,而现在通过与工业 4.0的融合&#…...

使用Wps减小PDF文件的大小

第一步、打开左上角的文件 第二步、点击打印选项 第三步、点击打印按钮...

【深度学习】GPT-3

2020年5月,OpenAI在长达72页的论文《https://arxiv.org/pdf/2005.14165Language Models are Few-Shot Learners》中发布了GPT-3,共有1750亿参数量,需要700G的硬盘存储,(GPT-2有15亿个参数),它比GPT-2有了极大的改进。根…...

在登录界面中设置登录框、多选项和按钮(HTML和CSS)

登录框(Input框)的样式: /* 设置输入框的宽度和高度 */ input[type"text"], input[type"password"] {width: 200px;height: 30px; }/* 设置输入框的边框样式、颜色和圆角 */ input[type"text"], input[type&q…...

【语音识别】- 声学,词汇和语言模型

一、说明 语音识别是指计算机通过处理人类语言的音频信号,将其转换为可理解的文本形式的技术。也就是说,它可以将人类的口语语音转换为文本,以便计算机能够进一步处理和理解。它是自然语言处理技术的一部分,被广泛应用于语音识别助…...

【考研英语语法及长难句】小结

【 考场攻略汇总 】 考点汇总 考场攻略 #1 断开长难句只看谓语动词,不考虑非谓语动词先找从句,先看主句 考场攻略 #2 抓住谓语动词,抓住句子最核心的表述动作或内容通过定位谓语动词,找到复杂多变的主语通过谓语动词的数量&…...

C# 反射

反射的概念:C#通过类型(Type)来创建对象,调用对象中的方法,属性等信息;B超就是利用了反射原理将超声波打在人的肚子上,然后通过反射波进行体内器官的成员; 反射提供的类:…...

Pytorch(二)

一、分类任务 构建分类网络模型 必须继承nn.Module且在其构造函数中需调用nn.Module的构造函数无需写反向传播函数,nn.Module能够利用autograd自动实现反向传播Module中的可学习参数可以通过named_parameters()返回迭代器 from torch import nn import torch.nn.f…...

Python 使用http时间同步设置系统时间源码

Python方式实现使用http时间同步设置系统时间源码,系统环境是ubuntu 12.04、Python2.7版本。需要使用到time、os及httplib方法。 Python使用http时间同步设置系统时间,源码如下: #-*-coding:utf8 -*- import httplib as client import time…...

golang sync.singleflight 解决热点缓存穿透问题

在 go 的 sync 包中,有一个 singleflight 包,里面有一个 singleflight.go 文件,代码加注释,一共 200 行出头。内容包括以下几块儿: Group 结构体管理一组相关的函数调用工作,它包含一个互斥锁和一个 map,map 的 key 是…...

4、Linux驱动开发:设备-设备号设备号注册

目录 🍅点击这里查看所有博文 随着自己工作的进行,接触到的技术栈也越来越多。给我一个很直观的感受就是,某一项技术/经验在刚开始接触的时候都记得很清楚。往往过了几个月都会忘记的差不多了,只有经常会用到的东西才有可能真正记…...

C++(MFC)调用Python

环境: phyton版本:3.10 VS版本:VS2017 包含文件头:Python\Python310\include 包含库文件:Python\Python310\libs 程序运行期间,以下函数只需要调用一次即可,重复调用会导致崩溃 void Initial…...

深度学习实践——循环神经网络实践

系列实验 深度学习实践——卷积神经网络实践:裂缝识别 深度学习实践——循环神经网络实践 深度学习实践——模型部署优化实践 深度学习实践——模型推理优化练习 代码可见于: 深度学习实践——循环神经网络实践 0 概况1 架构实现1.1 RNN架构1.1.1 RNN架…...

docker简单web管理docker.io/uifd/ui-for-docker

要先pull这个镜像docker.io/uifd/ui-for-docker 这个软件默认只能使用9000端口,别的不行,因为作者在镜像制作时已加入这一层 刚下下来镜像可以通过docker history docker.io/uifd/ui-for-docker 查看到这个端口已被 设置 如果在没有设置br0网关时&…...

SpringBoot内嵌的Tomcat:

SpringBoot内嵌Tomcat源码: 1、调用启动类SpringbootdemoApplication中的SpringApplication.run()方法。 SpringBootApplication public class SpringbootdemoApplication {public static void main(String[] args) {SpringApplication.run(SpringbootdemoApplicat…...

企业级docker应用注意事项

现在很多企业使用容器化技术部署应用,绕不开的docker技术,在生产环境docker常用操作总结。参考:https://juejin.cn/post/7259275893796651069 1. 尽可能使用官方镜像 在docker hub 官方 使用后面带有 DOCKER OFFICIAL IMAGE 标签的镜像&…...

腾讯云高性能计算集群CPU服务器处理器说明

腾讯云高性能计算集群以裸金属云服务器为节点,通过RDMA互联,提供了高带宽和极低延迟的网络服务,能满足大规模高性能计算、人工智能、大数据推荐等应用的并行计算需求,腾讯云服务器网分享腾讯云服务器高性能计算集群CPU处理器说明&…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...