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

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.快慢指针 例题 给定一个链表&#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&#xff08;索引从…...

重温设计模式--1、组合模式

文章目录 1 、组合模式&#xff08;Composite Pattern&#xff09;概述2. 组合模式的结构3. C 代码示例4. C示例代码25 .应用场景 1 、组合模式&#xff08;Composite Pattern&#xff09;概述 定义&#xff1a;组合模式是一种结构型设计模式&#xff0c;它允许你将对象组合成…...

单片机:实现SYN6288语音播报(附带源码)

单片机实现SYN6288语音播报 SYN6288是一款广泛应用于语音合成的IC&#xff0c;可以通过串口与单片机&#xff08;如51系列、STM32等&#xff09;进行通信&#xff0c;实现场景化的语音播报。通过连接外部存储设备&#xff08;如SD卡&#xff09;存储语音文件或直接通过内部语音…...

cookie,session,token 的区别

解决什么问题?Cookie&#xff08;客户端存储&#xff09;问题来了 Session&#xff08;会话&#xff09;解决的问题问题来了 token(令牌)解决的问题问题:token是无状态的如何解决? 解决什么问题? 解决http无状态的问题,说简单点就是用户身份的验证 举个例子: 张三在银行里…...

基于OpenAI Whisper AI模型自动生成视频字幕:全面解析与实战指南

在数字化时代&#xff0c;视频内容已成为信息传播的重要载体。然而&#xff0c;为视频添加字幕却是一项繁琐且耗时的工作。幸运的是&#xff0c;随着人工智能技术的飞速发展&#xff0c;特别是OpenAI Whisper模型的推出&#xff0c;我们有了更加高效、智能的解决方案。 一、Op…...

物理学天空的两朵乌云——量子论与相对论

物理学天空的两朵乌云——量子论与相对论 爱因斯坦的青春与科学的辉煌起点 提到爱因斯坦&#xff0c;我们往往会联想到一个经典的形象——乱糟糟的头发&#xff0c;叼着烟斗&#xff0c;脸上满是岁月的皱纹。然而&#xff0c;这张深入人心的照片并不是他科学创造力的象征。实…...

聚类之轮廓系数

Silhouette Score&#xff08;轮廓系数&#xff09;是用于评估聚类质量的指标之一。它衡量了数据点与同簇内其他点的相似度以及与最近簇的相似度之间的对比。 公式 对于一个数据点 i&#xff1a; a(i): 数据点 i 到同簇内其他点的平均距离&#xff08;簇内不相似度&#xff…...

Jenkins 构建流水线

在 Linux 系统上安装 Jenkins 服务&#xff0c;以及配置自动化构建项目 前置准备环境&#xff1a;docker、docker-compose、jdk、maven 一、环境搭建 1. Jenkins 安装 &#xff08;1&#xff09;拉取镜像 # 安装镜像包&#xff0c;默认安装最新版本 docker pull jenkins/jen…...

RTK部分模糊度固定测量流程图

部分模糊度剔除常用测量&#xff1a; 周跳或失锁时间优先剔除&#xff1b;按俯仰角剔除&#xff1b;按浮点模糊度协方差大小剔除模糊度&#xff1b;按信号强度剔除卫星&#xff1b;...

力扣-数据结构-2【算法学习day.73】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;建议灵神的题单和代码随想录&#xff09;和记录自己的学习过程&#xff0c;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关…...

操作系统导论读书笔记

目录 虚拟化抽象&#xff1a;进程抽象&#xff1a;进程概念 虚拟化 抽象&#xff1a;进程 本章讨论操作系统提供的基本的抽象—— 进程。进程的非正式定义非常简单&#xff1a;进程就是运行中的程序。程序本身是没有生命周期的&#xff0c;它只是存在磁盘上面的一些指令&…...

基于3D-Speaker进行区分说话人项目搭建过程报错记录 | 通话录音说话人区分以及语音识别 | 声纹识别以及语音识别 | pyannote-audio

0. 研究背景 在外呼系统中&#xff0c;我们的后台管理系统通常要对电话录音的内容进行提取和分析。那么说到分析&#xff0c;我们就要对录音中的两个人的对话进行分离&#xff0c;然后分别分析&#xff0c;比如分析客户是否有合作的意愿&#xff0c;分析客服讲的话术是否合理&…...

如何使用流式渲染技术提升用户体验

提示:记录工作中遇到的需求及解决办法 文章目录 什么是流式渲染?Node.js 实现简单流式渲染声明式 Shadow DOM,不依赖 javascript 实现react 实现流式渲染总结提示:以下是本篇文章正文内容,下面案例可供参考 什么是流式渲染? 流式渲染主要思想是将HTML文档分块(chunk)…...

【接口自动化连载】使用yaml配置文件自动生成接口case

直接上干货撸代码&#xff0c;有一些是通用的工具类代码&#xff0c;一次性封装永久使用&#xff0c;期待大家的关注&#xff0c;一起加油&#xff01;&#xff01;&#xff01; 配置文件 根据不同的业务需求进行配置&#xff0c;例如Goods服务、Order服务分开配置&#xff0…...

前端安全 常见的攻击类型及防御措施

1. 跨站脚本攻击&#xff08;XSS&#xff09; 描述&#xff1a;跨站脚本&#xff08;XSS&#xff1a;Cross-Site Scripting&#xff09;是一种安全漏洞&#xff0c;允许攻击者向网站注入恶意客户端代码。该代码由受害者执行从而让攻击者绕过访问控制并冒充用户。XSS攻击可以分…...

来道面试题——CopyOnWriteArrayList

原理 初始化时候&#xff0c;CopyOnWriteArrayList内部维护了一个可变数组&#xff0c;用于存储元素当执行数据变更操作的时候&#xff0c;会先创建一个原数组的副本&#xff0c;在副本上进行写操作&#xff0c;修改副本中的元素。写操作完成之后&#xff0c;把原数组的引用指…...

【Rust自学】5.1. 定义并实例化struct

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 5.1.1. 什么是struct struct的中文意思为结构体&#xff0c;它是一种自定义的数据类型&#xff0c;它允许程序为相关联的值命名和打包&am…...

React 生命周期完整指南

React 生命周期完整指南 1. 生命周期概述 1.1 React 16.3 之前的生命周期 初始化阶段 constructorcomponentWillMountrendercomponentDidMount 更新阶段 componentWillReceivePropsshouldComponentUpdatecomponentWillUpdaterendercomponentDidUpdate 卸载阶段 componentWil…...

python中os._exit(0) 强制关闭进程后来杀死线程

在 Python 中调用 os._exit(0) 会强制终止整个进程&#xff0c;包括所有正在运行的线程。以下是详细解释&#xff1a; os._exit(0) 的行为 立即终止进程&#xff1a;os._exit() 函数会立即终止当前进程&#xff0c;不会执行任何清理操作&#xff0c;如调用清理处理程序&#…...

LeetCode:257. 二叉树的所有路径

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;257. 二叉树的所有路径 给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...