基础算法--双指针算法
双指针算法
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.基本介绍 严格的来说,双指针只能说是是算法中的一种技巧。 双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针&#…...

企业工程项目管理系统源码(三控:进度组织、质量安全、预算资金成本、二平台:招采、设计管理)
工程项目管理软件(工程项目管理系统)对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营,全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…...

生物的神经系统与机器的人工神经网络
生物的神经系统与机器的人工神经网络 文章目录 前言一、人工神经网络二、生物的神经系统三、关系四、相似与区别4.1. 相似:4.2. 区别: 总结 前言 因为本人是学生物的,并且深度学习的核心——人工神经网络与生物的神经系统息息相关,故想要在本…...
JNI 基础
一、JNI 涉及的名词概念 1.1、 JNI:Java Native Interface 它是Java平台的一个特性(并不是Android系统特有的)。实现Java代码调用C/C的代码,C/C的代码也可以调用Java的代码. 1.2、 二进制库分类 : 静态库,动态库. 静态库 系统…...

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

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

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

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

go初识iris框架(七) - 实战资源导入和项目框架搭建
实战项目框架搭建 如下是项目框架搭建后的说明: config::项目配置文件及读取配置文件的相关功能controller:控制器目目录,项目各个模块的控制器及业务逻辑处理的所在目录datasource:实现mysql连接和操作、封装操作mysql数据库的目录。model:数据实体目…...
甲胎蛋白AFP抗体——博迈伦
甲胎蛋白(Alpha-fetoprotein,AFP)是一种由胚胎组织产生的蛋白质,通常以胎儿肝脏和胎盘为主要来源。AFP是一种重要的生物标志物,可用于诊断和预测某些疾病的发展情况。 AFP抗体是指能够与AFP结合的抗体,通常…...

junit.Test误踩坑,识别不到@Test注解,无法运行测试方法
问题的出现源自于下面的一段代码: 在这一段代码中,只看到可以运行的main方法,无法看到test方法可以运行的标志。 只能运行main()方法。 开始排查,对junit包的导入进行检查,发现是没有问题的。 怀疑是否是IntelliJ IDE…...

一加Ace2V/Ace竞速版刷入氧OS13系统-谷歌服务套件-全球语言-国际版体验
截止目前2023年9月5日,一加除了刚上市的Ace2Pro机型未确定国际版以外,其他机型均可以支持氧OS系统刷入。今天我们刷入的就是一加Ace2V和一加Ace竞速版本,两款机型均为MTK天玑处理器,并且系统已经升级了COlorOS13系统,所…...

Java 华为真题-猴子爬山
需求: 一天一只顽猴想去从山脚爬到山顶,途中经过一个有个N个台阶的阶梯,但是这猴子有一个习惯:每一次只能跳1步或跳3步,试问猴子通过这个阶梯有多少种不同的跳跃方式? 输入描述 输入只有一个整数Nÿ…...
Axios笔记
1、Axios介绍 Axios基于promise网络请求库,作用于node.js和浏览器中(即同一套代码可以运行在node.js和浏览器中),在服务器中他使用原生node.js http,在浏览器端则使用XMLHttpRequest。 特性: (1)、支持 Pro…...

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

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

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

爬虫工作者必备:使用爬虫IP轻松获得最强辅助
目录 一、爬虫IP的作用与优势 二、选择合适的爬虫IP服务商 三、使用爬虫IP的注意事项和技巧 代码示例 四、合法合规使用爬虫IP 总结 随着互联网的发展,数据已经成为企业竞争的核心资源。而获取这些数据的有效方式,就是通过爬虫技术。但是ÿ…...
工作比读研简单多了
工作比读研简单多了,因为至少有人能解答 工作遇到的问题相比读研时遇到的问题幸福太多,简单太多。因为读研时遇到的更多是未知的问题,是科学问题,是论文中也没有答案的问题,问不着答案,搜不着结果…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

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

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...