算法——双指针

目录

  • 前言
  • 一、什么是双指针
  • 二、算法特点
  • 三、算法实现步骤
  • 四、常见形式
  • 五、应用场景与示例
  • 六、优势与注意事项
  • 七、双指针算法动态图解
  • 八、经典例题
    • [1. 回文判定](https://www.lanqiao.cn/problems/1371/learning/?page=1&first_category_id=1&name=%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A)
      • 代码题解
    • [2. 反转字符串中的字符](https://www.lanqiao.cn/problems/250/learning/?page=1&first_category_id=1&name=%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E5%AD%97%E7%AC%A6)
      • 代码题解
    • 3.等腰三角
      • 代码题解
  • 结语

前言

双指针算法是必须掌握的一种基础算法,在一些比较出名的竞赛acm、蓝桥杯,并且在一些公司面试题中都可能会出现,而且作为简单题我们必须要拿下,所以我们要引起重视,下面让我们来深入了解递推。
在这里插入图片描述

一、什么是双指针

双指针算法涉及使用两个指针(索引或引用),通常分别称为“快指针”和“慢指针”或“左指针”和“右指针”,以协同进行遍历或搜索。该算法的核心思想是通过移动这两个指针来实现特定的目标,例如寻找一对元素的和、判断是否存在某种关系或在特定条件下移动其中一个指针。

二、算法特点

时间复杂度低:
双指针算法通常能够在O(n)的时间复杂度内解决问题,相较于暴力搜索的O(n^2)时间复杂度,具有显著的优势。
这是因为双指针算法通过同时操作两个指针,减少了重复计算和遍历次数。

空间复杂度低:
双指针算法通常只需要常数级别的额外空间,即O(1)的空间复杂度。这使得双指针算法在处理大规模数据时更加高效,因为它不需要额外的存储空间来存储中间结果。

适用性强:
双指针算法可以应用于多种数据结构,如数组、链表等。
它还可以用于解决多种类型的问题,如查找和排序、判断链表是否有环、计算最大子数组和等。

三、算法实现步骤

1.初始化指针:根据问题的具体需求,选择合适的初始位置来初始化指针。

2.遍历数据结构:使用循环遍历数据结构,同时操作两个指针。

3.判断条件:在遍历过程中,根据当前指针位置和目标条件来判断是否满足要求。

4.移动指针:根据判断结果,移动指针以继续搜索或缩小搜索范围。

5.记录结果:当找到满足条件的解时,记录结果并继续搜索,直到遍历完整个数据结构。

四、常见形式

对撞指针:两个指针分别从线性数据结构的两端向中间移动,常用于查找和排序问题。例如,在有序数组中查找和为特定值的两个数,可以使用一个头指针和一个尾指针,分别指向数组的最左边和最右边,通过比较两个指针指向的值与目标值的大小关系,移动指针来缩小搜索范围。

快慢指针:一个指针移动速度较快,另一个移动速度较慢。这常用于解决链表中的问题,如判断链表是否有环、找到链表的中间节点等。快慢指针相遇时,可以判断链表是否有环,并通过调整指针位置找到环的起点。

滑动窗口:使用两个指针维护一个窗口,通过移动窗口的左右边界解决问题。这类问题常见于字符串和数组处理,例如找到最短的包含所有字符的子串或计算数组中的最大子数组和等。

同向双指针:两个指针方向相同,通过控制其中一个指针的位置来处理问题。例如,在一个有序数组中查找两个数,使它们的和等于给定值。

五、应用场景与示例

移动零:使用双指针将数组中的零移动到末尾,同时保持非零元素的相对顺序。

复写零:在原数组上复写零,即每遇到一个零,就在其后面再添加一个零,同时保证不覆盖后面的数字。

快乐数:判断一个数是否为快乐数。快乐数定义为:一个正整数,每一次将该数替换为其每个位置上的数字的平方和,然后重复这个过程,直到这个数变为1,也可能是无限循环但始终变不到1。可以使用快慢指针的思想来判断是否存在循环。

盛最多水的容器:给定一个整数数组,其中每个元素代表一个垂直线条的高度,找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。可以使用双指针从两端向中间遍历,通过比较高度移动指针来找到最大面积。

有效三角形的个数:给定一个包含非负整数的数组,判断其中可以组成三角形的三个数的个数。可以先对数组进行排序,然后使用双指针来判断任意三个数是否能组成三角形。

三数之和:给定一个包含n个整数的数组,判断该数组中是否存在三个元素a,b,c,使得a+b+c=0?找出所有满足条件且不重复的三元组。可以使用双指针在排序后的数组中遍历并查找满足条件的三元组。

六、优势与注意事项

双指针算法通常能够在O(n)的时间复杂度内解决问题,具有较好的效率。然而,在使用双指针算法时需要注意以下几点:

初始化指针位置:根据问题的具体需求,选择合适的初始位置来初始化指针。

控制指针移动:根据当前指针位置和目标条件来决定如何移动指针。

避免重复计算:在移动指针时,要注意避免重复计算已经处理过的元素。

处理边界情况:对于数组为空或仅有一个元素等边界情况,需要进行特殊处理。

七、双指针算法动态图解

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

八、经典例题

1. 回文判定

(帅哥这个蓝色字体可以点进去看原题)

代码题解

#include <iostream>
#include<string>
using namespace std;
string s;
int main()
{cin>>s;int l=0,r=s.size()-1;while(l<r){if(s[l]==s[r])l++,r--;else {cout<<"N"<<endl;break;}}if(l>=r)cout<<"Y"<<endl;return 0;
}

2. 反转字符串中的字符

(帅哥这个蓝色字体可以点进去看原题)

代码题解

#include <iostream>
#include<cstring>
using namespace std;
int main()
{char s[1000];cin.getline(s,101,'\n');int l=0;int r=strlen(s)-1;while(l<r){swap(s[l],s[r]);l++,r--;}cout<<s<<endl;return 0;
}

3.等腰三角

(帅哥这个蓝色字体可以点进去看原题)

代码题解

#include <iostream>
#include<algorithm>
using namespace std;#define maxn 200001
int A[maxn],B[maxn],C[maxn];
//  1 2 3 4     A
//  2 4 6 8     C
//  2 2 3 4     B
//  i
//  j
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>A[i];C[i]=2*A[i];}for(int i=0;i<n;i++){cin>>B[i];}sort(C,C+n);//对c数组进行递增排序sort(B,B+n);//与c数组同理int i=0,j=0,ans=0;while(i<n&&j<n){if(C[i]>B[j])j++,ans++;//两个数组排好序之后,如b[j]>=c[i],那么也就是说j以后的b数组所有数都比c[i]大,i++i++;}cout<<ans<<endl;return 0;
}

结语

学习算法是一个很艰难,漫长的过程,我们要克服一切困难,学习算法本就是由易到难,不会的地方就问,我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节,加油,我相信你一定能行。

在这里插入图片描述

关注我让我们一起学习编程,希望大家能点赞关注支持一下,让我有持续更新的动力,谢谢大家。
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465858.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【简信CRM-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

burpsuite安装详细教程(非常详细)零基础入门到精通,收藏这篇就够了

BurpSuite是一款功能强大的集成化安全测试工具&#xff0c;专门用于攻击和测试Web应用程序的安全性。适合安全测试、渗透测试和开发人员使用。本篇文章基于BurpSuite安装及常用实操做详解&#xff0c;如果你是一名安全测试初学者&#xff0c;会大有收获&#xff01; 前****言 …

使用亚马逊 S3 连接器为 PyTorch 和 MinIO 创建地图式数据集

在深入研究 Amazon 的 PyTorch S3 连接器之前&#xff0c;有必要介绍一下它要解决的问题。许多 AI 模型需要使用无法放入内存的数据进行训练。此外&#xff0c;许多为计算机视觉和生成式 AI 构建的真正有趣的模型使用的数据甚至无法容纳在单个服务器附带的磁盘驱动器上。解决存…

【Python】怎么创建一个新的conda环境,并在其中安装所需的软件包

最近在运行前同事留下的包的时候&#xff0c;遇到了numpy包和pandas包不匹配的问题&#xff0c;具体见前一篇&#xff1a;【Python】遇到pandas 和numpy版本不兼容怎么办&#xff1f;sharetypeblogdetail&sharerId143412274&sharereferPC&sharesourceMeggie35&…

优衣库在淘宝平台的全方位竞品分析与店铺表现研究:市场定位与竞争策略透视

优衣库品牌在淘宝平台的全方位竞品与店铺表现分析 一、品牌商品分析 1.商品列表与分类分析&#xff08;数据来源&#xff1a;关键词商品搜索接口&#xff1b;获取时间&#xff1a;2024.08.30&#xff09; 商品类别分布柱状图&#xff1a; 根据关键词商品搜索接口获取到的优衣…

[HCTF 2018]WarmUp 1--详细解析

打开靶机&#xff0c;进入界面&#xff1a; 信息搜集 当前界面没有任何有用信息。 想到查看页面源代码。右键–查看页面源代码 看到hint&#xff1a;<!--source.php--> 进入/source.php页面&#xff0c;看到页面源代码&#xff1a; <?phphighlight_file(__FILE_…

安利一款超6K+ star的可拖放响应式灵活的网格布局Gridstack.js

Gridstack.js是一个现代JavaScript&#xff08;或Typescript&#xff09;库&#xff0c;旨在帮助开发人员快速构建交互式和响应式的布局。以下是对Gridstack.js的详细介绍&#xff1a; 一、主要特点 灵活的网格布局&#xff1a;Gridstack.js允许开发者轻松地创建和管理网格布局…

嵌入式学习-网络高级-Day01

嵌入式学习-网络高级-Day01 【1】Modbus协议 起源 分类 优势 应用场景 【2】Modbus TCP 特点 组成 报文头&#xff1a;7个字节 寄存器&#xff08;存储数据&#xff09; 功能码 总结 练习 【3】工具安装 Modbus Slave、Poll安装 网络调试助手 wireshark 练习 【1】Modbus协议 起…

细说STM32单片机USART中断收发RTC实时时间并改善其鲁棒性的另一种方法

目录 一、工程目的 1、目标 2、通讯协议及应对错误指令的处理目标 二、工程设置 三、程序改进 四、下载与调试 1、合规的指令 2、不以#开头&#xff0c;但以&#xff1b;结束&#xff0c;长度不限 3、以#开头&#xff0c;不以;结束&#xff0c;也不包含;&#xff0c;长…

路见不平 ! 基于tensorlfow快速迭代的户型图分类功能

前言 在工作之余&#xff0c;发现合作的同事需要手动筛选户型图&#xff0c;存在一些老旧或无家具的户型图。这启发我们通过机器学习的模型预测来辅助校验&#xff0c;进而优化筛选流程。当前本期目标为6万个,后续也会有数据需要筛选,已经筛选出一部分数据 可以进行模型训练&am…

字符串接龙 /单词接龙 (BFs C#

卡码网 110和 力扣127 和LCq 108题都是一个解法 这两道题乍一看在结果处可能不一样 力扣要求 字符串里边必须包含对应的最后一个字符 而110不需要最后一个字符 但是在实验逻辑上是一致的 只是110需要把如果在set中找不到最后一个字符就直接返回0的逻辑删去 就可以了 这就是…

STM32之看门狗

STM32有独立看门狗&#xff08;IWDG&#xff09;和窗口看门狗(WWDG)。 采用窗口看门狗&#xff08;WWDG&#xff09;&#xff0c;有一个死前中断&#xff0c;可以用来作一个报警的功能。 独立看门狗超时时间计算公式 假设LSI是32KHz,超时时间等于 预分频系数&#xff08;4&…

平安科技(外包)面试分享

前言&#xff1a; 这是成都这边的平安科技面试分享&#xff0c;上家公司是做海外的&#xff0c;好不容易逮到公司离职赔偿的机会&#xff0c;我就离职了&#xff0c;没想到过了国庆节之后&#xff0c;工作是那么的难找&#xff0c;大概投了1-2周简历&#xff08;外包和短期项目…

Python 在PDF中绘制形状(线条、矩形、椭圆形等)

在PDF中绘制图形可以增强文档的视觉效果。通过添加不同类型的形状&#xff0c;如实线、虚线、矩形、圆形等&#xff0c;可以使文档更加生动有趣&#xff0c;提高读者的阅读兴趣。这对于制作报告、演示文稿或是教材特别有用。本文将通过以下几个示例介绍如何使用Python 在PDF中绘…

2-2.STM32之定时器TIM---输入捕获--实验2( PWMI模式测频率占空比)

输入捕获模式测频率、PWMI模式测频率占空比-CSDN博客 参考这篇文章&#xff01; 来利用一个GPIO的定时器的两个通道进行捕获占空比和频率&#xff0c;看出可以看出。TI1FP1和TI2FP2&#xff0c;计数值分别在CCR1和CCR2中取&#xff0c; 测周法 IC.c #include "stm32f1…

2024年转行指南:大学生进军就业前景广阔的领域——人工智能大模型

据教育部数据统计&#xff0c;2024高校毕业生规模预计达1179万人&#xff0c;将再创历史新高&#xff0c;“就业难”仍是当前大学毕业生需要直面的问题。在此背景下&#xff0c;选择一个就业前景好的专业尤为重要。 究竟学什么样的专业好就业呢&#xff1f;给毕业生们推荐3个当…

suanfabiji

1 差分练习 1 模板题 代码实现&#xff1a; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int num sc.nextInt();long[][] arr new long[n 2][m 2…

WPS单元格重复值提示设置

选中要检查的所有的单元格 设置提示效果 当出现单元格值重复时&#xff0c;重复的单元格就会自动变化 要修改或删除&#xff0c;点击

一.Linux文件基本属性

前言&#xff1a;Linux系统是一个多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;也就是说具有不同的权限。为了安全&#xff0c;对于不同用户访问同一个文件&#xff0c;设置不同权限是很有必要的。 一.文件的基本属性理解 在Linux中&#xff0c;通常是这两个命…

【学习记录】使用CARLA录制双目摄像头SLAM数据

一、数据录制 数据录制的部分参考了网上的部分代码&#xff0c;代码本身并不复杂&#xff0c;基本都是简单的CARLA语法&#xff0c;关键的一点在于&#xff0c;CARLA内部本身并没有预设的双目摄像头&#xff0c;需要我们添加两个朝向相同的摄像头来组成双目系统&#xff0c;这…