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

基础算法--双指针算法

双指针算法

1.基本介绍

严格的来说,双指针只能说是是算法中的一种技巧。

双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。最常见的双指针算法有两种:一种是,在一个序列里边,用两个指针维护一段区间;另一种是,在两个序列里边,一个指针指向其中一个序列,另外一个指针指向另外一个序列,来维护某种次序。

在这里插入图片描述在这里插入图片描述

2.模板

for (int i = 0, j = 0; i < n; i ++ )  // j从某一位置开始,不一定是0
{while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}
常见问题分类:(1) 对于一个序列,用两个指针维护一段区间,比如快排的划分过程(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

双指针算法的核心思想(作用):优化
在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.

当我们采用朴素的方法即暴力枚举每一种可能的情况,时间复杂度为O(n*n)

    for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){//具体逻辑}}

而当我们使用双指针算法时通过某种性质就可以将上述O(n*n)的操作优化到O(n)
在这里插入图片描述

暴力算法和它优化后的双指针算法有什么区别:

由于具有某种单调性,朴素算法往往能优化为双指针算法。
区别:

  • 朴素算法每次在第二层遍历的时候,是会从新开始(j会回溯到初始位置),然后再遍历下去。(假设i是终点,j是起点)
  • 双指针算法:由于具有某种单调性,每次在第二层遍历的时候,不需要回溯到初始位置(单调性),而是在满足要求的位置继续走下去或者更新掉。

3.例题01

先看这样一个例子:输入一个字符每个子串之间有一个空格,让你输出每一个空格后的子串。

输入

abc def hij

输出

abc
def
hij

【参考代码】

#include<iostream>
#include<string>using namespace std;int main()
{string str;getline(cin, str);int n = str.size();for(int i = 0; i < n; i++){int j = i;while(str[j] != ' ') j++;// cout<<j;for(int k = i; k < j; k++) cout<<str[k];cout<<endl;i = j; //循环体执行完后for()中的i才 i++即,下一次开始时 i就到了上一次空格(位置j)的下一位 }return 0;
}

在这里插入图片描述

例题02

【AcWing 799. 最长连续不重复子序列 】

给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例:

5
1 2 2 3 5

输出样例:

3

思路:

使用双指针算法,根据观察发现,当使用i,j两个快慢指针表示当前的指针移动到i的最长不重复序列时候,具有单调性,即i向后移动,j必然向右或者不动,不可能向左移动,这一单调性质导致可以使用双指针算法。(当出现重复时若j还向左移动,那序列必然还有重复,这就矛盾了!)
在双指针算法中,一个指针扫描整个数组而移动,关键如何找到对应的另一个指针移动的位置,在本题中,我们定义i为快指针,j为慢指针,j的位置定义为i对应的最长不重复序列的j的位置,因为不重复,i和j元素都不重复,出现次数都为一,因此我们使用一个数组s来记录各个元素出现的次数,i,j不断移动,数组及时更新,每次i更新,便更新j确保(j,i)区间元素都只出现一次,代码如下

【参考代码】

#include<iostream>using namespace std;
const int N = 100000+10;
int a[N],s[N];// s[N]用来记录数据出现的次数
int main()
{int n;cin>>n;int res = 0;for(int i = 0; i < n; i++) cin>>a[i];for(int i = 0, j = 0; i < n; i++){// 注意:j = 0不能拿下来,不然每次又是从0开始了!s[a[i]]++; // 记录数值a[i]出现的次数// i快指针,j 慢指针while(j <= i && s[a[i]] > 1) // 若出现重复的数值。j <= i不要也行{s[a[j]]--; j++;}//更新的不包含重复的数的连续区间的最大长度res = max(res, i - j +1);}cout<<res;return 0;
}

图解辅助理解:
在这里插入图片描述

相关文章:

基础算法--双指针算法

双指针算法 1.基本介绍 严格的来说&#xff0c;双指针只能说是是算法中的一种技巧。 双指针指的是在遍历对象的过程中&#xff0c;不是普通的使用单个指针进行访问&#xff0c;而是使用两个相同方向&#xff08;快慢指针&#xff09;或者相反方向&#xff08;对撞指针&#…...

企业工程项目管理系统源码(三控:进度组织、质量安全、预算资金成本、二平台:招采、设计管理)

工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…...

生物的神经系统与机器的人工神经网络

生物的神经系统与机器的人工神经网络 文章目录 前言一、人工神经网络二、生物的神经系统三、关系四、相似与区别4.1. 相似&#xff1a;4.2. 区别: 总结 前言 因为本人是学生物的&#xff0c;并且深度学习的核心——人工神经网络与生物的神经系统息息相关&#xff0c;故想要在本…...

JNI 基础

一、JNI 涉及的名词概念 1.1、 JNI&#xff1a;Java Native Interface 它是Java平台的一个特性(并不是Android系统特有的)。实现Java代码调用C/C的代码&#xff0c;C/C的代码也可以调用Java的代码. 1.2、 二进制库分类 &#xff1a; 静态库&#xff0c;动态库. 静态库 系统…...

用户参数(zabbix-agent)

-s 指向被监控端地址 -p 指向被监控端端口 -k 指向key的名字 监控内存使用率 agent vi a.conf server web界面 对数据库的avg进行监控 systemctl 创建监控项 另一台 重启 agent 监控请求数 运行时间 对自定义key的理解 写下想要监控的任何参数命令&#xff0c;利用zabbix…...

期权策略篇: 实现买方狂欢,让卖方稳赚不赔的策略

欢迎来到期权策略篇: 实现买方狂欢&#xff0c;让卖方稳赚不赔的策略&#xff0c;今天给大家带来的期权策略比较简单&#xff0c;是我们比较常见的四种单腿期权策略&#xff0c;这四种策略分别是买入看涨期权、买入看跌期权、卖出看涨期权、卖出看跌期权策略。本文来自&#xf…...

关于包,类名,方法名的命名规范

保持与数据库同名的一个命名规范的规则 方法名采用驼峰命名法&#xff0c;保持与数据库同名的一个命名规范的规则 类名采用首字母大写&#xff0c;驼峰命名法&#xff0c;保持与数据库同名的一个命名规范的规则 包名全部使用小写&#xff0c;保持与数据库同名的一个命名规范的规…...

1.1 安装配置CentOS

文章目录 零、学习目标一、导入新课二、新课讲解&#xff08;一&#xff09;安装VMWare Workstation1、获取安装程序2、进入安装向导3、按提示完成安装 &#xff08;二&#xff09;虚拟网络编辑器1、启动虚拟网络编辑器2、选择VMnet8虚拟网3、更改网络配置4、查看DHCP设置5、查…...

go初识iris框架(七) - 实战资源导入和项目框架搭建

实战项目框架搭建 如下是项目框架搭建后的说明&#xff1a; config:&#xff1a;项目配置文件及读取配置文件的相关功能controller:控制器目目录,项目各个模块的控制器及业务逻辑处理的所在目录datasource:实现mysql连接和操作、封装操作mysql数据库的目录。model:数据实体目…...

甲胎蛋白AFP抗体——博迈伦

甲胎蛋白&#xff08;Alpha-fetoprotein&#xff0c;AFP&#xff09;是一种由胚胎组织产生的蛋白质&#xff0c;通常以胎儿肝脏和胎盘为主要来源。AFP是一种重要的生物标志物&#xff0c;可用于诊断和预测某些疾病的发展情况。 AFP抗体是指能够与AFP结合的抗体&#xff0c;通常…...

junit.Test误踩坑,识别不到@Test注解,无法运行测试方法

问题的出现源自于下面的一段代码&#xff1a; 在这一段代码中&#xff0c;只看到可以运行的main方法&#xff0c;无法看到test方法可以运行的标志。 只能运行main()方法。 开始排查&#xff0c;对junit包的导入进行检查&#xff0c;发现是没有问题的。 怀疑是否是IntelliJ IDE…...

一加Ace2V/Ace竞速版刷入氧OS13系统-谷歌服务套件-全球语言-国际版体验

截止目前2023年9月5日&#xff0c;一加除了刚上市的Ace2Pro机型未确定国际版以外&#xff0c;其他机型均可以支持氧OS系统刷入。今天我们刷入的就是一加Ace2V和一加Ace竞速版本&#xff0c;两款机型均为MTK天玑处理器&#xff0c;并且系统已经升级了COlorOS13系统&#xff0c;所…...

Java 华为真题-猴子爬山

需求&#xff1a; 一天一只顽猴想去从山脚爬到山顶&#xff0c;途中经过一个有个N个台阶的阶梯&#xff0c;但是这猴子有一个习惯&#xff1a;每一次只能跳1步或跳3步&#xff0c;试问猴子通过这个阶梯有多少种不同的跳跃方式&#xff1f; 输入描述 输入只有一个整数N&#xff…...

Axios笔记

1、Axios介绍 Axios基于promise网络请求库&#xff0c;作用于node.js和浏览器中&#xff08;即同一套代码可以运行在node.js和浏览器中)&#xff0c;在服务器中他使用原生node.js http,在浏览器端则使用XMLHttpRequest。 特性&#xff1a; &#xff08;1&#xff09;、支持 Pro…...

如何使用try-except语句处理Python中的异常

在python爬虫行业里面&#xff0c;异常处理能力已经成为了一项非常重要的技能。随着软件规模的不断扩大和复杂性的增加&#xff0c;异常处理能力已经成为了评判一个示波器水平的重要指标。 &#xff0c;学会使用try-except语句来捕获和处理Python异常&#xff0c;对于我们做爬虫…...

学Python的漫画漫步进阶 -- 第十一步.常用的内置模块

学Python的漫画漫步进阶 -- 第十一步.常用的内置模块 十一、常用的内置模块11.1 数学计算模块——math11.2 日期时间模块——datetime11.2.1 datetime类11.2.2 date类11.2.3 time类11.2.4 计算时间跨度类——timedelta11.2.5 将日期时间与字符串相互转换 11.3 正则表达式模块—…...

发现无尽的创意可能性——Photo Image Editor Pixelstyle for Mac

无论您是一名专业摄影师还是一个爱好者&#xff0c;您都需要一款强大而多功能的图像编辑软件来实现您的创意。Photo Image Editor Pixelstyle for Mac将成为您的创作利器&#xff0c;帮助您探索图像编辑的无限可能性。 Photo Image Editor Pixelstyle for Mac是一款专业级的图…...

Smart Community(1)之设计规范

通过前面大数据开发相关知识的学习&#xff0c;准备做一个项目进行练习---我给他起了一个响亮的名字&#xff1a;基于HadoopHA的智慧社区服务平台 设计规范&#xff1a; 做一个项目之前肯定要先规定一些开发过程中的设计规范 &#xff08;一&#xff09;数据埋点规范&#xf…...

爬虫工作者必备:使用爬虫IP轻松获得最强辅助

目录 一、爬虫IP的作用与优势 二、选择合适的爬虫IP服务商 三、使用爬虫IP的注意事项和技巧 代码示例 四、合法合规使用爬虫IP 总结 随着互联网的发展&#xff0c;数据已经成为企业竞争的核心资源。而获取这些数据的有效方式&#xff0c;就是通过爬虫技术。但是&#xff…...

工作比读研简单多了

工作比读研简单多了&#xff0c;因为至少有人能解答 工作遇到的问题相比读研时遇到的问题幸福太多&#xff0c;简单太多。因为读研时遇到的更多是未知的问题&#xff0c;是科学问题&#xff0c;是论文中也没有答案的问题&#xff0c;问不着答案&#xff0c;搜不着结果&#xf…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

反射获取方法和属性

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

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...