当前位置: 首页 > news >正文

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

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

🔥个人主页大白的编程日记

🔥专栏算法笔记


文章目录

  • 【算法笔记】双指针算法深度剖析
    • 前言
    • 一.移动零
      • 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;}
};

八.算法总结

双指针算法总体来说就是利用两个指针,根据题目要求灵活结合单调性,区间思想,以及题目场景用指针的移动访问解决问题。总而言之,双指针需要根据题目灵活使用解决问题

后言

这就是双指针算法原理的深度剖析,这些题目基本包含了双指针的所有解题方法。大家自己好好消化。感谢大家的耐心垂阅!今天就分享到这,咱们下期见!拜拜~

相关文章:

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

【算法笔记】双指针算法深度剖析 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;算法笔记 文章目录 【算法笔记】双指针算法深度剖析前言一.移动零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. 电话号码的字母组合 回溯法的一个重点理解&#xff1a;细细理解这句话&#xff01;…...

关闭IDM自动更新

关闭IDM自动更新 1 打开注册表2 找到IDM注册表路径 1 打开注册表 winR regedit 2 找到IDM注册表路径 计算机\HKEY_CURRENT_USER\Software\DownloadManager 双击LstCheck&#xff0c;把数值数据改为0 完成 感谢阅读...

Go 性能剖析工具 pprof 与 Graphviz 教程

在 Golang 开发中&#xff0c;性能分析是确保应用高效运行的重要环节。本文介绍如何使用 gin-contrib/pprof 在 Gin 应用中集成性能剖析工具&#xff0c;并结合 Graphviz 生成图形化的性能分析结果&#xff0c;如火焰图。这套流程帮助开发者更好地理解和优化 Go 应用的性能。 目…...

【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

【题目解析】蓝桥杯23国赛C中高级组 - 斗鱼养殖场 题目链接跳转&#xff1a;点击跳转 前置知识&#xff1a; 了解过基本的动态规划。熟练掌握二进制的位运算。 题解思路 这是一道典型的状压动态规划问题。设 d p i , j dp_{i, j} dpi,j​ 表示遍历到第 i i i 行的时候&a…...

JavaScript可视化:探索顶尖的图表库

JavaScript可视化&#xff1a;探索顶尖的图表库 在这个被数据驱动的时代&#xff0c;你有没有想过&#xff0c;数据本身是如何变得有意义的&#xff1f;答案就是数据可视化。通过图表和图形&#xff0c;我们不仅可以看到数据&#xff0c;还可以感受到它&#xff0c;从而做出明…...

谷歌AI大模型Gemini API快速入门及LangChain调用视频教程

1. 谷歌Gemini API KEY获取及AI Studio使用 要使用谷歌Gemini API&#xff0c;首先需要获取API密钥。以下是获取API密钥的步骤&#xff1a; 访问Google AI Studio&#xff1a; 打开浏览器&#xff0c;访问Google AI Studio。使用Google账号登录&#xff0c;若没有账号&#xf…...

进入容器:掌控Docker的世界

进入容器:掌控Docker的世界 在这个快速发展的技术时代,你是否曾被Docker的庞大生态所吸引?那么,有没有想过在这个容器化的世界里,如何快速高效地“进入”这些隐藏在虚拟墙后的容器呢?容器就如同魔法箱,装载着应用与服务,而你,通过探索这些容器,能够更好地管理、排除…...

初始Linux(二)基础命令

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

STM32 OLED

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

伦敦金实时行情决策辅助!

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

​Leetcode 746. 使用最小花费爬楼梯​ 入门dp C++实现

问题&#xff1a;Leetcode 746. 使用最小花费爬楼梯 给你一个整数数组 cost &#xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用&#xff0c;即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你…...

路由协议常见知识点

路由协议是网络通信的基础&#xff0c;主要负责在网络中传递数据包&#xff0c;并确保它们从源节点传递到目标节点。本文将介绍一些常见的路由协议知识点&#xff0c;包括路由协议的分类、特性、配置与管理以及常见问题。 一、路由协议的分类 距离矢量路由协议&#xff1a; R…...

多模态大语言模型(MLLM)-InstructBlip深度解读

前言 InstructBlip可以理解为Blip2的升级版&#xff0c;重点加强了图文对话的能力。 模型结构和Blip2没差别&#xff0c;主要在数据集收集、数据集配比、指令微调等方面下文章。 创新点 数据集收集&#xff1a; 将26个公开数据集转换为指令微调格式&#xff0c;并将它们归类…...

网页前端开发之Javascript入门篇(7/9):字符串

Javascript字符串 什么是字符串&#xff1f; 答&#xff1a;其概念跟 Python教程 介绍的一样&#xff0c;只是语法上有所变化。 在 Javascript 中&#xff0c;一个字符串变量可以看做是其内置类String的一个实例&#xff08;Javascript会自动包装&#xff09;。 因此它拥有一…...

双登股份再战IPO:数据打架,实控人杨善基千万元股权激励儿子

撰稿|行星 来源|贝多财经 近日&#xff0c;双登集团股份有限公司&#xff08;下称“双登股份”&#xff09;递交招股书&#xff0c;准备在港交所主板上市&#xff0c;中金公司、建银国际、华泰国际为其联席保荐人。 贝多财经了解到&#xff0c;这并非双登股份首次向资本市场…...

4.Python 函数(函数的定义、函数的传入参数、函数的返回值、None 类型、函数说明文档、变量的作用域)

一、函数快速入门 1、函数概述 函数是组织好的&#xff0c;可重复使用的&#xff0c;用来实现特定功能的代码段 name "Hello World" name_length len(name)print(f"{name} 的长度为 {name_length}") # Hello World 的长度为 11len() 是Python 内置的函…...

【JavaEE】——文件IO

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;认识文件 1&#xff1a;文件的概念 2&#xff1a;文件的结构 3&#xff1a;文件路径…...

Python的pandas库基本操作(数据分析)

一、安装&#xff0c;导入 1、安装 使用包管理器安装&#xff1a; pip3 install pandas 2、导入 import pandas as pd as是为了方便引用起的别名 二、DateFrame 在Pandas库中&#xff0c;DataFrame 是一种非常重要的数据结构&#xff0c;它提供了一种灵活的方式来存储和…...

软件测试(平铺版本)

目录 黑盒测试&#xff1a; 定义: 示例&#xff1a;登录功能的黑盒测试 适合使用黑盒测试的情况 几种常见的黑盒测试方法&#xff1a; 1. 等价类划分&#xff08;Equivalence Partitioning&#xff09; 2. 边界值分析&#xff08;Boundary Value Analysis&#xff09; …...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&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语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

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

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