【算法笔记】双指针算法深度剖析
【算法笔记】双指针算法深度剖析
🔥个人主页:大白的编程日记
🔥专栏:算法笔记
文章目录
- 【算法笔记】双指针算法深度剖析
- 前言
- 一.移动零
- 1.1题目
- 1.2思路分析
- 1.3代码实现
- 二.复写零
- 2.1题目
- 2.2思路分析
- 2.3代码实现
- 三.快乐数
- 3.1题目
- 3.2思路分析
- 3.3代码实现
- 四.盛水最多的容器
- 4.1题目
- 4.2思路分析
- 4.3正确性证明
- 4.4代码实现
- 五.有效三角形个数
- 5.1题目
- 5.2思路分析
- 5.3代码实现
- 六.两数之和
- 6.1题目
- 6.2思路分析
- 6.3代码实现
- 七.三数之和
- 7.1题目
- 7.2思路分析
- 7.3代码实现
- 八.算法总结
- 后言
前言
哈喽,各位小伙伴大家好!今天给大家分享的是入门算法双指针。算法我们程序员必备的技能。话不多说,咱们进入正题!向大厂冲锋!
一.移动零
1.1题目
- 题目:移动零
1.2思路分析
这里我们无非就是想让数组维持非0元素在前,0元素在后的区间状态。同时不改变非0元素的相对顺序。那我们可以用区间思想,借助双指针维护我们的区间状态。
1.3代码实现
class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur=0,dest=-1;cur<nums.size();cur++)//初始化同时扫描数组{if(nums[cur])//判断是否非0{swap(nums[++dest],nums[cur]);//dest移动后交换}}}
};
//分成三个区间未处理区
//处理区分区为非0元素区和0元素区
二.复写零
2.1题目
- 题目:复写零
2.2思路分析
我们从左往右无法复写,因为会覆盖后面的数据。但是从右往左复写可以。所以我们找到最后一个复写的数,处理一下特殊情况从右往左复写即可。
2.3代码实现
class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest=-1,cur=0,n=arr.size();while(dest<n-1)//找到最后一个复写数{if(arr[cur]==0){dest++;}dest++;if(dest>=n-1){break;}cur++;}if(dest==n)//防止越界{arr[--dest]=0;dest--;cur--;}while(cur>=0)//从后往前复写{if(arr[cur]==0){arr[dest--]=0;arr[dest--]=0;cur--;}else{arr[dest--]=arr[cur--];}}}
};
三.快乐数
3.1题目
- 题目:
快乐数
3.2思路分析
这里我们根据鸽巢原理就可以把题目转化为判断入环点是否为1。
具体快慢指针相遇的问题可以看这篇 快慢指针相遇证明
3.3代码实现
这里我们用两个变量代替指针的作用。
class Solution {
public:int bitSum(int n)//计算每个数的平方和{int sum=0;while(n){sum+=pow(n%10,2);n/=10;}return sum;}bool isHappy(int n) {int slow=bitSum(n);int fast=bitSum(slow);while(slow!=fast){slow=bitSum(slow);fast=bitSum(fast);fast=bitSum(fast);}return slow==1;//判断入环点是否为1}
};
四.盛水最多的容器
4.1题目
- 题目:盛水最多的容器
4.2思路分析
这里我们需要观察规律解题。
4.3正确性证明
4.4代码实现
class Solution {
public:int maxArea(vector<int>& height){int max=0;int left=0,right=height.size()-1;while(left<right)//双指针法{int v=fmin(height[left],height[right])*(right-left);//保存枚举的最大值max=fmax(v,max);//更新最大值height[left]<height[right]?left++:right--;}return max;}
};
五.有效三角形个数
5.1题目
- 题目:有效三角形的个数
5.2思路分析
这里我们用排序的单调性做优化.
正确性证明上一个题解有,这里就不过多赘述了。
5.3代码实现
class Solution {
public:int triangleNumber(vector<int>& nums) {int ret=0;sort(nums.begin(),nums.end());for(int i=nums.size()-1;i>=2;i--)//固定最大的数{int left=0,right=i-1;while(left<right){int t=nums[left]+nums[right];if(t>nums[i])//大于{ret+=(right-left);right--;}else//小于{left++;}}}return ret;}
};
六.两数之和
6.1题目
- 题目:两数之和
这里题目改了但是题意是一样的
6.2思路分析
这里依旧是按照单调性优化。
需要注意的是如果我们找到存在多个结果,我们找到结果后让left和right指针继续移动查找即可。
6.3代码实现
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());//排序int left=0,right=nums.size()-1;while(left<right){int tmp=nums[left]+nums[right];if(tmp<target){left++;}else if(tmp>target){right--;}else //找到结果{return {nums[left],nums[right]};}}return {};}
};
七.三数之和
7.1题目
- 题目:三数之和
7.2思路分析
这里我们可以转化为两数之和来解决问题。但是要注意去重的问题。
7.3代码实现
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());for(int i=0;i<nums.size()-2;)//固定最左边的指针{if(nums[i]>0)//大于没结果{break;}int left=i+1,right=nums.size()-1;int target=-nums[i];//找两数之和while(left<right)//左右指针两数之和,先移动再比较{int tmp=nums[left]+nums[right];if(tmp<target)//小于{left++;while(left<right&&nums[left]==nums[left-1])//跳过重复元素去重{left++;}}else if(tmp>target)//大于{right--;while(left<right&&nums[right]==nums[right+1])//跳过重复元素去重{right--;}}else//相等{ret.push_back({nums[i],nums[left],nums[right]});//记录结果left++;right--;while(left<right&&nums[left]==nums[left-1])//跳过重复元素去重{left++;}while(left<right&&nums[right]==nums[right+1])//跳过重复元素去重{right--;}}}i++;while(i<nums.size()&&nums[i]==nums[i-1])//跳过重复元素去重{i++;}//去重}return ret;}
};
八.算法总结
双指针算法总体来说就是利用两个指针,根据题目要求灵活结合单调性,区间思想,以及题目场景用指针的移动访问解决问题。总而言之,双指针需要根据题目灵活使用解决问题
后言
这就是双指针算法原理的深度剖析,这些题目基本包含了双指针的所有解题方法。大家自己好好消化。感谢大家的耐心垂阅!今天就分享到这,咱们下期见!拜拜~
相关文章:

【算法笔记】双指针算法深度剖析
【算法笔记】双指针算法深度剖析 🔥个人主页:大白的编程日记 🔥专栏:算法笔记 文章目录 【算法笔记】双指针算法深度剖析前言一.移动零1.1题目1.2思路分析1.3代码实现 二.复写零2.1题目2.2思路分析2.3代码实现 三.快乐数3.1题目…...

第二十二天|回溯算法| 理论基础,77. 组合(剪枝),216. 组合总和III,17. 电话号码的字母组合
目录 回溯算法理论基础 1.题目分类 2.理论基础 3.回溯法模板 补充一个JAVA基础知识 什么时候用ArrayList什么时候用LinkedList 77. 组合 未剪枝优化 剪枝优化 216. 组合总和III 17. 电话号码的字母组合 回溯法的一个重点理解:细细理解这句话!…...

关闭IDM自动更新
关闭IDM自动更新 1 打开注册表2 找到IDM注册表路径 1 打开注册表 winR regedit 2 找到IDM注册表路径 计算机\HKEY_CURRENT_USER\Software\DownloadManager 双击LstCheck,把数值数据改为0 完成 感谢阅读...
Go 性能剖析工具 pprof 与 Graphviz 教程
在 Golang 开发中,性能分析是确保应用高效运行的重要环节。本文介绍如何使用 gin-contrib/pprof 在 Gin 应用中集成性能剖析工具,并结合 Graphviz 生成图形化的性能分析结果,如火焰图。这套流程帮助开发者更好地理解和优化 Go 应用的性能。 目…...
【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场
【题目解析】蓝桥杯23国赛C中高级组 - 斗鱼养殖场 题目链接跳转:点击跳转 前置知识: 了解过基本的动态规划。熟练掌握二进制的位运算。 题解思路 这是一道典型的状压动态规划问题。设 d p i , j dp_{i, j} dpi,j 表示遍历到第 i i i 行的时候&a…...
JavaScript可视化:探索顶尖的图表库
JavaScript可视化:探索顶尖的图表库 在这个被数据驱动的时代,你有没有想过,数据本身是如何变得有意义的?答案就是数据可视化。通过图表和图形,我们不仅可以看到数据,还可以感受到它,从而做出明…...

谷歌AI大模型Gemini API快速入门及LangChain调用视频教程
1. 谷歌Gemini API KEY获取及AI Studio使用 要使用谷歌Gemini API,首先需要获取API密钥。以下是获取API密钥的步骤: 访问Google AI Studio: 打开浏览器,访问Google AI Studio。使用Google账号登录,若没有账号…...
进入容器:掌控Docker的世界
进入容器:掌控Docker的世界 在这个快速发展的技术时代,你是否曾被Docker的庞大生态所吸引?那么,有没有想过在这个容器化的世界里,如何快速高效地“进入”这些隐藏在虚拟墙后的容器呢?容器就如同魔法箱,装载着应用与服务,而你,通过探索这些容器,能够更好地管理、排除…...

初始Linux(二)基础命令
前言: 之前那一篇我们已经介绍了一部分的基础命令,当然那只不过是九牛一毛,本篇我们继续介绍一些比较重要且需要掌握的基础命令。 mv命令: 其实这个命令有两个功能,一个是移动(剪切)文件&#…...

STM32 OLED
文章目录 前言一、OLED是什么?二、使用步骤1.复制 OLED.C .H文件1.1 遇到问题 2.统一风格3.主函数引用头文件3.1 oled.h 提供了什么函数 4.介绍显示一个字符的函数5. 显示十进制函数的讲解 三、使用注意事项3.1 配置符合自己的引脚3.2 花屏总结 前言 提示ÿ…...

伦敦金实时行情决策辅助!
在伦敦金实时交易的过程中,投资者主要依赖技术分析来辅助自己的投资决策。与基本面分析不同,技术分析侧重于研究金价的走势和市场行为,通过图表和技术指标来预测未来的市场走势。常用的技术分析方法包括: 趋势线和支撑阻力位&…...

Leetcode 746. 使用最小花费爬楼梯 入门dp C++实现
问题:Leetcode 746. 使用最小花费爬楼梯 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你…...
路由协议常见知识点
路由协议是网络通信的基础,主要负责在网络中传递数据包,并确保它们从源节点传递到目标节点。本文将介绍一些常见的路由协议知识点,包括路由协议的分类、特性、配置与管理以及常见问题。 一、路由协议的分类 距离矢量路由协议: R…...

多模态大语言模型(MLLM)-InstructBlip深度解读
前言 InstructBlip可以理解为Blip2的升级版,重点加强了图文对话的能力。 模型结构和Blip2没差别,主要在数据集收集、数据集配比、指令微调等方面下文章。 创新点 数据集收集: 将26个公开数据集转换为指令微调格式,并将它们归类…...
网页前端开发之Javascript入门篇(7/9):字符串
Javascript字符串 什么是字符串? 答:其概念跟 Python教程 介绍的一样,只是语法上有所变化。 在 Javascript 中,一个字符串变量可以看做是其内置类String的一个实例(Javascript会自动包装)。 因此它拥有一…...

双登股份再战IPO:数据打架,实控人杨善基千万元股权激励儿子
撰稿|行星 来源|贝多财经 近日,双登集团股份有限公司(下称“双登股份”)递交招股书,准备在港交所主板上市,中金公司、建银国际、华泰国际为其联席保荐人。 贝多财经了解到,这并非双登股份首次向资本市场…...
4.Python 函数(函数的定义、函数的传入参数、函数的返回值、None 类型、函数说明文档、变量的作用域)
一、函数快速入门 1、函数概述 函数是组织好的,可重复使用的,用来实现特定功能的代码段 name "Hello World" name_length len(name)print(f"{name} 的长度为 {name_length}") # Hello World 的长度为 11len() 是Python 内置的函…...

【JavaEE】——文件IO
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 一:认识文件 1:文件的概念 2:文件的结构 3:文件路径…...

Python的pandas库基本操作(数据分析)
一、安装,导入 1、安装 使用包管理器安装: pip3 install pandas 2、导入 import pandas as pd as是为了方便引用起的别名 二、DateFrame 在Pandas库中,DataFrame 是一种非常重要的数据结构,它提供了一种灵活的方式来存储和…...
软件测试(平铺版本)
目录 黑盒测试: 定义: 示例:登录功能的黑盒测试 适合使用黑盒测试的情况 几种常见的黑盒测试方法: 1. 等价类划分(Equivalence Partitioning) 2. 边界值分析(Boundary Value Analysis) …...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...