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

双指针的详细教程

双指针算法是一种常用的算法技巧,它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。

双指针并非真的用指针实现,一般用两个变量来表示下标(在后面都用指针来表示)

双指针算法使用两个指针在数据结构上进行迭代,并根据问题的要求移动这些指针。

双指针往往也和单调性、排序联系在一起,在数组的区间问题上,暴力法的时间复杂度往往都是O(n^2)的,但双指针利用“单调性”可以优化到O(n)

常见的双指针模型有

(1)对撞指针

指的是两个指针left、right分别指向序列的第一个元素和最后一个元素

然后I指针不断递增,r不断递减,直到两个指针的值相撞后错开(即l>=r),或者满足其他的特殊条件为止

对撞指针一般是用来解决有序数组或者字符串问题(区间问题)

查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。

字符串反转问题:反转字符串,回文数等问题。

1 使用两个指针left,right.left指向序列第一个元素,即:left=1,right指向序列最后一个元素,即:right:n。

2 在循环体中将左右指针相向移动,当满足一定条件时,将左指针右移,left++.当满足另外一定条件时,右指针左移right--

直到两指针相撞(即left==right),或者满足其他要求的特殊条件时,跳出循环体

例题实战

题目描述

给定一个长度为n的字符串S,请你判断字符串S是否时回文

输入描述

输入仅一行包含一个字符串S

1<=|S|<=10^6,保证S只包含大小写字母

输出描述

若字符串S为会问串,则输出Y,否则输出N

输入输出样例

示例 1

abcba

输出Y

回文判定

对撞指针,每次判断s[l]和s[r]是否相等。如果相等,进一步移动,否则直接判断“不是回文串”

(2)快慢指针

快慢指针一般比对撞指针更难想,更难写。

指的是两个指针,从同一侧开始遍历序列,且移动的步长一个块,一个慢

移动快的指针被称为快指针,一动漫的指针被称为慢指针

为了方便理解,我们称快指针为r,慢指针为l,这样慢指针和快指针构成的区间为[l,r]

两个指针以不同的速度,不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或者满足其他特殊条件为止。

1.使用两个指针l,r.一般l指向序列的第一个元素,即:l=1,r一般指向序列第零个元素,即:r=0。即初始时区间[l,r]=[1,0]表示为空区间。

2.在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即l++。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即r++,保持[l,r]为合法区间

3.到指针移动到数组尾端(即l==n且r==n),或者两指针相交,或者满足其他特殊条件时,跳出循环 

例题

给定一个长度为n的序列a1,a2,...an和一个常数S

对于一个连续区间如果它的区间和大于或等于S,则称它为美丽区间

对于一个美丽区间,如果区间长度越短,它越美丽

请你从序列中找出最美丽的区间

输入描述

第一含包含两个整数n,S,其含义如题所述

接下来一行包含n个整数,分别表示a1,a2,...an

输出描述

输出共遗憾,包含一个整数,表示最美丽的区间长度

若不存在任何美丽区间,则输出0

相关文章:

双指针的详细教程

双指针算法是一种常用的算法技巧&#xff0c;它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。 双指针并非真的用指针实现&#xff0c;一般用两个变量来表示下标&#xff08;在后面都用指针来表示&#xff09; 双指针算法使用两个指针在数据结构上进行迭代&a…...

【Review+预测】测试架构演进的曲折之路

文章目录 前言 一、“原始”阶段 二、“小打小闹”阶段 三、“小米加步枪”阶段 四、“摩托化部队”阶段 五、“骑兵连”阶段 六、“海军陆战队”阶段 七、“社区型组织”阶段 前言 近期公司的测试团队需要重新组织安排&#xff0c;本着谦虚谨慎的态度&#xff0c;我从…...

2015年认证杯SPSSPRO杯数学建模D题(第二阶段)城市公共自行车全过程文档及程序

2015年认证杯SPSSPRO杯数学建模 D题 城市公共自行车 原题再现&#xff1a; 城市交通问题直接影响市民的生活和工作。在地形平坦的城市&#xff0c;公共自行车出行系统是一种很好的辅助手段。一般来说&#xff0c;公共自行车出行系统由数据中心、驻车站点、驻车桩、自行车&…...

视频汇聚平台EasyCVR启用图形验证码之后调用login接口的操作方法

视频综合管理平台EasyCVR视频监控系统支持多协议接入、兼容多类型设备&#xff0c;平台可以将区域内所有部署的监控设备进行统一接入与集中汇聚管理&#xff0c;实现对监控区域的实时高清视频监控、录像与存储、设备管理、云台控制、语音对讲、级联共享等&#xff0c;在监控中心…...

【数据结构】非线性结构——二叉树

文章目录 前言1.树型结构1.1树的概念1.2树的特性1.3树的一些性质1.4树的一些表示形式1.5树的应用2.二叉树 2.1 概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储2.5 二叉树的基本操作 前言 前面我们都是学的线性结构的数据结构&#xff0c;接下来我们就需要来学习非…...

数据分析POWER BI之power query

1.导入数据 ctrla全选--数据--获取数据--其他来源--来自表格/区域 导入数据&#xff0c;进入编辑模式 2.整理与清除 清除&#xff1a;删除所选列的非打印字符 转换--格式--清除 修整&#xff1a;删除前面和后面的空格 转换---格式---修整&#xff08;修整后前面后面的空格没有了…...

【c语言】详解操作符(上)

1. 操作符的分类 2. 原码、反码、补码 整数的2进制表示方法有三种&#xff0c;即原码、反码、补码 有符号整数的三种表示方法均有符号位和数值位两部分&#xff0c;2进制序列中&#xff0c;最高位的1位是被当做符号位其余都是数值位。 符号位都是用0表示“正”&#xff0c;用…...

VR全景展示:传统制造业如何保持竞争优势?

在结束不久的两会上&#xff0c;数字化经济和创新技术再度成为了热门话题。我国制造产业链完备&#xff0c;但是目前依旧面临着市场需求不足、成本传导压力加大等因素影响&#xff0c;那么传统制造业该如何保持竞争优势呢&#xff1f; 在制造行业中&#xff0c;VR全景展示的应用…...

2.7、创建列表(List)

概述 列表是一种复杂的容器&#xff0c;当列表项达到一定数量&#xff0c;内容超过屏幕大小时&#xff0c;可以自动提供滚动功能。它适合用于呈现同类数据类型或数据类型集&#xff0c;例如图片和文本。在列表中显示数据集合是许多应用程序中的常见要求&#xff08;如通讯录、…...

solr functionquery函数查询自定义函数实现

Solr是一个开源的搜索平台&#xff0c;基于Apache Lucene库构建&#xff0c;主要用于提供全文搜索的功能。它被设计为一个高度可靠、可扩展的搜索应用服务器。以下是Solr的一些主要使用场景&#xff1a; 全文搜索&#xff1a;Solr最核心的功能是提供全文搜索&#xff0c;它可以…...

如何将 Parallels虚拟机 安装或者迁移到 移动硬盘 or U盘?

本文讨论主题 如何安装 Parallels 虚拟机到移动硬盘和U盘? 已经安装到了mac上的虚拟机如何迁移到移动硬盘活着U盘上? 关于Parallels Deskshop 19 虚拟机 安装激活,文末关注公众号AIshape,回复:PD 进行获取通过将虚拟机安装在外置的移动硬盘U盘上,可以节省mac本身SSD的容…...

大型网站集群管理负载均衡

课程介绍 结合企业大规模应用&#xff0c;解决应用高并发问题&#xff0c;解决单节点故障问题&#xff0c;缓存数据库的应用。学完掌握知识点&#xff1a;企业应用实现四七层负载均衡&#xff0c;以及Nginx等应用的高可用性&#xff0c;Redis缓存数据库的部署应用以及高可用方…...

JAVA使用POI实现Excel单元格合并-02

JAVA使用POI实现Excel单元格合并 实现效果 解释&#xff1a;只要是遇见与前一行相同的数据就合并 引入jar <dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxml</artifactId><version>5.2.2</version></depe…...

深入了解 Linux 中的 MTD 设备:/dev/mtd* 与 /dev/mtdblock*

目录 前言一、什么是MTD子系统&#xff1f;二、 /dev/mtd* 设备文件用途注意事项 三、/dev/mtdblock* 设备文件用途注意事项 三、这两种设备文件的关系四、关norflash的一些小知识 前言 在嵌入式Linux系统的世界里&#xff0c;非易失性存储技术扮演着至关重要的角色。MTD&#…...

2、Spring CLI安装

安装 Spring CLI 提供了多种格式,让您选择自己喜欢的安装方法。可下载的制品可从发布页面获取。 二进制发行版 WindowsLinuxMac手动安装(Windows,其他自己看) spring-cli-standalone-<version>-windows.x86_64.zip - 打包了 x86 JDKspring-cli-installer-<versi…...

数据库备份工具(实现数据定时覆盖)

数据库备份工具&#xff08;实现数据定时覆盖&#xff09; 永远热爱&#xff0c;永远执着&#xff01; 工具介绍 自动化测试数据库更新调度程序 这段 Python 脚本自动化了每天定时从生产数据库更新测试数据库的过程。它利用了 schedule 库来安排并执行每天指定时间的更新任务…...

测试环境搭建整套大数据系统(十二:挂载磁盘到hadoop环境)

一&#xff1a;链接硬盘 将硬盘连接到计算机的 SATA 接口或 USB 接口&#xff0c;并确保硬盘通电并处于可用状态。 二&#xff1a;查看硬盘信息 sudo fdisk -l三&#xff1a;创建分区 gdisk /dev/vbd重新扫描磁盘 partprobe /dev/vdb格式化磁盘 mkfs.ext4 /dev/vdb2查看磁…...

Spring事务核心:声明式事务注解式事务

全解&#xff1a;声明式事务和注解事务 在Spring中&#xff0c;事务管理是一个非常重要的特性&#xff0c;它可以帮助开发者在应用程序中实现事务控制。Spring提供了两种事务管理方式&#xff1a;声明式事务和注解事务。 1. 声明式事务 声明式事务是指通过配置文件或注解的方…...

AcWing 1015. 摘花生

Problem: AcWing 1015. 摘花生 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们需要在一个二维网格中&#xff0c;从左上角走到右下角&#xff0c;每次只能向右或向下移动&#xff0c;目标是使得经过的路径上的数字之和最大。 我们可以定义dp[i][j]为从…...

Dalle-3、Sora、Stable Diffusion 3 掀起AIGC新浪潮

随着科技的飞速发展&#xff0c;我们迎来了视觉AIGC高光时刻&#xff0c;一个充满无限可能与机遇的新时代。在这个时代里&#xff0c;三大里程碑Dalle-3、Sora和Stable Diffusion 3以其炸裂式的技术发展&#xff0c;引领着AIGC领域的新浪潮。文章首先做相应简要介绍&#xff0c…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...