vector快慢指针+例题详解
1.快慢指针
例题
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:

提示:
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle
2.思路
设置一快一慢指针,如果快指针追上慢指针,则有环。如果快指针到达链表尾,说明无环。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head==nullptr||head->next==nullptr)return false;ListNode * slow = head;ListNode * fast = slow->next;while(fast!=slow){if(fast==nullptr||fast->next==nullptr)return false;slow = slow->next;fast = fast->next->next;}return true;}
};
3.相似例题
以下本质为快慢指针
26. 删除有序数组中的重复项 - 力扣(LeetCode)

class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() < 2)return nums.size();int slow = 1;int fast = 1;for (fast = 1; fast < nums.size(); fast++){if (nums[fast] != nums[slow-1]){nums[slow] = nums[fast];slow++;}}return slow;}
};
class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& nums) {auto slow = nums.begin();auto fast = nums.end();int flag = 0;for (slow = nums.begin(); slow < nums.end(); slow++){flag = 0;for (fast = nums.begin(); fast < nums.end(); fast++){if (*fast == *slow){flag++;}}if(flag > nums.size()/2){return *slow;}}return 0;}
};
优质文章推荐:双指针算法详解(快慢指针、对撞指针、滑动窗口)_滑动窗口和双指针算法-CSDN博客
相关文章:
vector快慢指针+例题详解
1.快慢指针 例题 给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从…...
重温设计模式--1、组合模式
文章目录 1 、组合模式(Composite Pattern)概述2. 组合模式的结构3. C 代码示例4. C示例代码25 .应用场景 1 、组合模式(Composite Pattern)概述 定义:组合模式是一种结构型设计模式,它允许你将对象组合成…...
单片机:实现SYN6288语音播报(附带源码)
单片机实现SYN6288语音播报 SYN6288是一款广泛应用于语音合成的IC,可以通过串口与单片机(如51系列、STM32等)进行通信,实现场景化的语音播报。通过连接外部存储设备(如SD卡)存储语音文件或直接通过内部语音…...
cookie,session,token 的区别
解决什么问题?Cookie(客户端存储)问题来了 Session(会话)解决的问题问题来了 token(令牌)解决的问题问题:token是无状态的如何解决? 解决什么问题? 解决http无状态的问题,说简单点就是用户身份的验证 举个例子: 张三在银行里…...
基于OpenAI Whisper AI模型自动生成视频字幕:全面解析与实战指南
在数字化时代,视频内容已成为信息传播的重要载体。然而,为视频添加字幕却是一项繁琐且耗时的工作。幸运的是,随着人工智能技术的飞速发展,特别是OpenAI Whisper模型的推出,我们有了更加高效、智能的解决方案。 一、Op…...
物理学天空的两朵乌云——量子论与相对论
物理学天空的两朵乌云——量子论与相对论 爱因斯坦的青春与科学的辉煌起点 提到爱因斯坦,我们往往会联想到一个经典的形象——乱糟糟的头发,叼着烟斗,脸上满是岁月的皱纹。然而,这张深入人心的照片并不是他科学创造力的象征。实…...
聚类之轮廓系数
Silhouette Score(轮廓系数)是用于评估聚类质量的指标之一。它衡量了数据点与同簇内其他点的相似度以及与最近簇的相似度之间的对比。 公式 对于一个数据点 i: a(i): 数据点 i 到同簇内其他点的平均距离(簇内不相似度ÿ…...
Jenkins 构建流水线
在 Linux 系统上安装 Jenkins 服务,以及配置自动化构建项目 前置准备环境:docker、docker-compose、jdk、maven 一、环境搭建 1. Jenkins 安装 (1)拉取镜像 # 安装镜像包,默认安装最新版本 docker pull jenkins/jen…...
RTK部分模糊度固定测量流程图
部分模糊度剔除常用测量: 周跳或失锁时间优先剔除;按俯仰角剔除;按浮点模糊度协方差大小剔除模糊度;按信号强度剔除卫星;...
力扣-数据结构-2【算法学习day.73】
前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?建议灵神的题单和代码随想录)和记录自己的学习过程,我的解析也不会做的非常详细,只会提供思路和一些关…...
操作系统导论读书笔记
目录 虚拟化抽象:进程抽象:进程概念 虚拟化 抽象:进程 本章讨论操作系统提供的基本的抽象—— 进程。进程的非正式定义非常简单:进程就是运行中的程序。程序本身是没有生命周期的,它只是存在磁盘上面的一些指令&…...
基于3D-Speaker进行区分说话人项目搭建过程报错记录 | 通话录音说话人区分以及语音识别 | 声纹识别以及语音识别 | pyannote-audio
0. 研究背景 在外呼系统中,我们的后台管理系统通常要对电话录音的内容进行提取和分析。那么说到分析,我们就要对录音中的两个人的对话进行分离,然后分别分析,比如分析客户是否有合作的意愿,分析客服讲的话术是否合理&…...
如何使用流式渲染技术提升用户体验
提示:记录工作中遇到的需求及解决办法 文章目录 什么是流式渲染?Node.js 实现简单流式渲染声明式 Shadow DOM,不依赖 javascript 实现react 实现流式渲染总结提示:以下是本篇文章正文内容,下面案例可供参考 什么是流式渲染? 流式渲染主要思想是将HTML文档分块(chunk)…...
【接口自动化连载】使用yaml配置文件自动生成接口case
直接上干货撸代码,有一些是通用的工具类代码,一次性封装永久使用,期待大家的关注,一起加油!!! 配置文件 根据不同的业务需求进行配置,例如Goods服务、Order服务分开配置࿰…...
前端安全 常见的攻击类型及防御措施
1. 跨站脚本攻击(XSS) 描述:跨站脚本(XSS:Cross-Site Scripting)是一种安全漏洞,允许攻击者向网站注入恶意客户端代码。该代码由受害者执行从而让攻击者绕过访问控制并冒充用户。XSS攻击可以分…...
来道面试题——CopyOnWriteArrayList
原理 初始化时候,CopyOnWriteArrayList内部维护了一个可变数组,用于存储元素当执行数据变更操作的时候,会先创建一个原数组的副本,在副本上进行写操作,修改副本中的元素。写操作完成之后,把原数组的引用指…...
【Rust自学】5.1. 定义并实例化struct
喜欢的话别忘了点赞、收藏加关注哦,对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 5.1.1. 什么是struct struct的中文意思为结构体,它是一种自定义的数据类型,它允许程序为相关联的值命名和打包&am…...
React 生命周期完整指南
React 生命周期完整指南 1. 生命周期概述 1.1 React 16.3 之前的生命周期 初始化阶段 constructorcomponentWillMountrendercomponentDidMount 更新阶段 componentWillReceivePropsshouldComponentUpdatecomponentWillUpdaterendercomponentDidUpdate 卸载阶段 componentWil…...
python中os._exit(0) 强制关闭进程后来杀死线程
在 Python 中调用 os._exit(0) 会强制终止整个进程,包括所有正在运行的线程。以下是详细解释: os._exit(0) 的行为 立即终止进程:os._exit() 函数会立即终止当前进程,不会执行任何清理操作,如调用清理处理程序&#…...
LeetCode:257. 二叉树的所有路径
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:257. 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
