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

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...