【算法笔记】双指针算法深度剖析
【算法笔记】双指针算法深度剖析

🔥个人主页:大白的编程日记
🔥专栏:算法笔记

文章目录
- 【算法笔记】双指针算法深度剖析
- 前言
- 一.移动零
- 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) …...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...

