当前位置: 首页 > 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;返回所有从根…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...