当前位置: 首页 > 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…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

高频面试之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…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...