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

算法思想总结:双指针算法

一、移动零

. - 力扣(LeetCode) 移动零

该题重要信息:1、保持非0元素的相对位置。2、原地对数组进行操作

 思路:双指针算法

class Solution {
public:void moveZeroes(vector<int>& nums){int n=nums.size();for(int cur=0,des=-1;cur<n;++cur)if(nums[cur])//如为非零,就要与des后面的位置元素进行交换swap(nums[++des],nums[cur]);}
};

 二、复写零

. - 力扣(LeetCode)复写零

该题的重要信息:1、不要在超过该数组的长度的位置写入元素(就是不要越界)2、就地修改(就是不能创建新数组)。3、不返回任何东西。

 思路:双指针算法

class Solution {
public:void duplicateZeros(vector<int>& arr){int cur=0,des=-1,n=arr.size();//找最后一个被复写数的位置for(;cur<n;++cur){if(arr[cur])++des;elsedes+=2;if(des>=n-1)//要让des指向最后一个位置break;}//边界修正if(des==n){arr[--des]=0;--des;--cur;}//从后往前复写for(;cur>=0;--cur){if(arr[cur])arr[des--]=arr[cur];else{arr[des--]=0;arr[des--]=0;}}}
};

 三、快乐数

. - 力扣(LeetCode)快乐数

 该题的关键是:将正整数变成他的每位数的平方之和,有可能会一直循环始终到不了1,也有始终是1(快乐数)

思路:快慢双指针算法

以上的两个结论在博主的关于链表带环追击问题的文章里面有分析

顺序表、链表相关OJ题(2)-CSDN博客

class Solution {
public:int bitsum(int n){ int sum=0;while(n){int t=n%10;sum+=t*t;n/=10;//最后一位算完后拿掉}return sum;}bool isHappy(int n) {int slow=n,fast=bitsum(n);while(fast!=slow){slow=bitsum(slow);fast=bitsum(bitsum(fast));}return slow==1;}
};

四、盛最多水的容器

. - 力扣(LeetCode)盛最多水的容器

思路1、暴力枚举(时间复杂度太高)

class Solution {
public:int maxArea(vector<int>& height){//暴力枚举int n=height.size();int ret=0;for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)ret=max(ret,min(height[i],height[j])*(j-i));return ret;}
};

思路2、双指针对撞算法

class Solution {
public:int maxArea(vector<int>& height){int left=0,right=height.size()-1,ret=0;while(left<right){ret=max(ret,min(height[left],height[right])*(right-left));if(height[left]<height[right])++left;else--right;}return ret;}
};

五、有效三角形的个数

. - 力扣(LeetCode)有效三角形的个数

 思路1:升序+暴力枚举

思路2:升序+利用双指针算法

class Solution {
public:int triangleNumber(vector<int>& nums) {//排序一下sort(nums.begin(),nums.end());//先固定一个数,然后用双指针去找比较小的两个数int n=nums.size(),ret=0;for(int i=n-1;i>=2;--i){int left=0,right=i-1;while(left<right){int sum=nums[left]+nums[right];if(sum<=nums[i])  ++left;else  {ret+=(right-left);--right;} }}return ret;}
};

 六、查找总价格为目标值的两个商品

. - 力扣(LeetCode)查找总价格为目标值的两个商品

 

思路1:两层for循环找到所有组合去计算

思路2:利用单调性,使用双指针算法解决问题

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n=price.size();int left=0,right=n-1;while(left<right){int sum=price[left]+price[right];if(sum>target) --right;else if(sum<target) ++left;else return {price[left],price[right]};}return {1,0};}
};

七、三数之和

. - 力扣(LeetCode)三数之和

解法1:排序+暴力枚举+set去重

解法2:排序+双指针

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums){vector<vector<int>> ret;int n=nums.size();//先排序sort(nums.begin(),nums.end());//先固定一个数for(int i=0;i<n;){if(nums[i]>0) break;//小优化int target =-nums[i];//目标值//定义双指针int left=i+1,right=n-1;while(left<right){int sum=nums[left]+nums[right];if(sum<target)  ++left;else if(sum>target) --right;else  {ret.push_back({nums[left],nums[right],nums[i]});//插入进去++left;--right;//去重while(left<right&&nums[left]==nums[left-1])  ++left;//去重要注意边界while(left<right&&nums[right]==nums[right+1])  --right;}}++i;while(i<n&&nums[i]==nums[i-1])  ++i;//去重要注意边界}return ret;}
};

八、四数之和

. - 力扣(LeetCode)四数之和

解法1:排序+暴力枚举+set去重

解法2:排序+双指针(和上一题基本一样,无非就是多固定了一个数)

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;//先进行排序sort(nums.begin(),nums.end());//利用双指针解决int n=nums.size();//先固定一个数for(int i=0;i<n;){//再固定一个数for(int j=i+1;j<n;){int left=j+1,right=n-1;long long aim=(long long)target-nums[i]-nums[j];//确保不超出范围while(left<right){long long sum=nums[left]+nums[right];if(sum<aim)  ++left;else if(sum>aim) --right;else {ret.push_back({nums[i],nums[j],nums[left],nums[right]});++left;--right;//去重while(left<right&&nums[left]==nums[left-1]) ++left;while(left<right&&nums[right]==nums[right+1]) --right;}}//去重++j;while(j<n&&nums[j]==nums[j-1]) ++j;}//去重++i;while(i<n&&nums[i]==nums[i-1]) ++i;}return ret;}
};

九、总结

常见的双指针有三种形式:前后指针、对撞指针、快慢指针

1、前后指针:用于顺序结构,一般是两个指针同方向,cur指针用来遍历数组,des指针将数组进行区域划分。(如1、2题)

       注意事项:如果是从前往后遍历,要注意dst不能走得太快,否则cur还没遍历到一些数就会被覆盖掉,必要时候可以根据情况从后往前遍历。

2、快慢指针:其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。(如第3题,以及链表带环的问题)

        注意事项: 其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使⽤快慢指针的思想。最常用的就是快指针走两步,慢指针走一步。

3、对撞指针:一般用于顺序结构。从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。并且常常会用到单调性!!(如4-8题)
        注意事项:对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环)

用双指针策略一般可以比暴力枚举降低一个次方的时间复杂度

     如果后面还有关双指针的经典题目,博主会继续在这篇更新的!!

相关文章:

算法思想总结:双指针算法

一、移动零 . - 力扣&#xff08;LeetCode&#xff09; 移动零 该题重要信息&#xff1a;1、保持非0元素的相对位置。2、原地对数组进行操作 思路&#xff1a;双指针算法 class Solution { public:void moveZeroes(vector<int>& nums){int nnums.size();for(int cur…...

python中的zip函数

1.zip&#xff08;&#xff09;同时迭代多个列表、字典等 使用zip()可以同时迭代多个可迭代对象&#xff0c;如列表、字典。 注意&#xff1a;当若干个可迭代对象的长度不相等时&#xff0c;zip()函数会停止在最短的可迭代对象。 例子&#xff1a; # 定义可迭代对象 numbers …...

Element 选择季度组件

<template><el-dialogtitle"选择季度":show-close"false":close-on-click-modal"false":close-on-press-escape"false":visible"visiable"class"dialog list"append-to-body><div><div>&…...

4.MongoDB中16个常用CURD

基本的CURD 作为一个非专业的DBA&#xff0c;我们只需要会一些基本的curd就行&#xff0c;专业的内容还是需要专业的人去干的。CRUD 也就是增删改查&#xff0c;这是数据库最基本的功能&#xff0c;查询还支持全文检索&#xff0c;GEO 地理位置查询等。 01创建库 无需单独创…...

Tomcat数据源笔记

Tomcat数据源笔记 连接池的概念 连接池是一种由容器提供的机制&#xff0c;用于管理数据库连接对象的集合。连接池的主要作用是在应用程序需要与数据库进行交互时&#xff0c;提供可复用的连接对象&#xff0c;从而减少每次建立数据库连接的开销。 连接池的工作原理 连接池的…...

Spring-Kafka笔记整理

引入依赖<dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId> </dependency>配置application.propertiesspring.kafka.bootstrap-servers192.168.99.51:9092编写kafka的配置类Configuration …...

已解决org.apache.hadoop.hdfs.protocol.QuotaExceededException异常的正确解决方法,亲测有效!!!

已解决org.apache.hadoop.hdfs.protocol.QuotaExceededException异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 报错原因 解决思路 解决方法 总结 博主v&#xff1a;XiaoMing_Java 问题分析 在使用Hadoop分布式文件系统&a…...

GitHub打不开的解决方案(超简单)

在国内&#xff0c;github官网经常面临打不开或访问极慢的问题&#xff0c;不挂VPN&#xff08;梯子&#xff0c;飞机&#xff0c;魔法&#xff09;使用体验极差&#xff0c;那有什么好办法解决github官网访问不了的问题&#xff1f;今天小布教你几招轻松访问github官网。 git…...

Unity开发一个FPS游戏之二

在之前的文章中,我介绍了如何开发一个FPS游戏,添加一个第一人称的主角,并设置武器。现在我将继续完善这个游戏,打算添加敌人,实现其智能寻找玩家并进行对抗。完成的效果如下: fps_enemy_demo 下载资源 首先是设计敌人,我们可以在网上找到一些好的免费素材,例如在Unity…...

STM32F103 CubeMX 使用USB生成鼠标设备

STM32F103 CubeMX 使用USB生成鼠标设备 1 配置cubeMX1.1配置外部晶振&#xff0c;配置debug口1.2 配置USB1.3 配置芯片的时钟1.4 生成工程 2. 编写代码2.1 添加申明2.2 main函数代码 1 配置cubeMX 1.1配置外部晶振&#xff0c;配置debug口 1.2 配置USB 1.3 配置芯片的时钟 需…...

HJXH-E1/U静态信号继电器 面板安装 辅助电源220VDC 启动电压220VDC JOSEF约瑟

HJXH系列静态信号继电器 HJXH-61/U静态信号继电器&#xff1b; HJXH-61/I静态信号继电器&#xff1b; HJXH-62/U静态信号继电器&#xff1b; HJXH-62/I静态信号继电器&#xff1b; HJXH-E1/U静态信号继电器&#xff1b; HJXH-E1/I静态信号继电器&#xff1b; HJXH-E2/U静态信号…...

SpringBoot3下Kafka分组均衡消费实现

首先添加maven依赖&#xff1a; <dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId><version>2.8.11</version><exclusions><!--此处一定要排除kafka-clients&#xff0c;然…...

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:GridItem)

网格容器中单项内容容器。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。仅支持作为Grid组件的子组件使用。 子组件 可以包含单个子组件。 接口 GridItem GridItem(value?: GridItemOptions)…...

Qt 使用RAW INPUT获取HID触摸屏,笔设备,鼠标的原始数据,最低受支持的客户端:Windows XP [仅限桌面应用]

在开发绘图应用程序时&#xff0c;经常会需要读取笔设备的数据&#xff0c;通过对笔数据的解析&#xff0c;来判断笔的坐标&#xff0c;粗细。如果仅仅只是读取鼠标的坐标&#xff0c;就需要人为在应用程序端去修改笔的粗细&#xff0c;并且使用体验不好&#xff0c;如果可以实…...

easyexcel导出excel文件到s3服务器

导出excel文件是开发中常见的需求 常见的做法一般是直接通过请求接口响应对象HttpServletResponse把文件输出 我们可以使用原生的poi工具类操作.也可以使用easypoi.easyexcel等基于poi二次封装的工具处理 下面是代码 /*** 导出列表** param request* param response*/Overri…...

xss.haozi.me靶场“0x0B-0x12”通关教程

君衍. 一、0x0B 实体编码绕过二、0x0C script绕过三、0x0D 注释绕过四、0X0E ſ符号绕过五、0x0F 编码解码六、0x10 直接执行七、0x11 闭合绕过八、0x12 闭合绕过 XSS-Labs靶场“1-5”关通关教程 XSS-Labs靶场“6-10”关通关教程 Appcms存储型XSS漏洞复现 XSS-Labs靶场“11-13、…...

linux--redhat系统Yum源配置

1&#xff09;说明 redhat yum命令使用报错解决-重新配置yum源 解决--更改yum源 2&#xff09;更改yum源 &#xff08;1&#xff09;进入源目录 cd /etc/yum.repos.d/ &#xff08;2&#xff09;备份 redhat 默认源 mv redhat.repo redhat.repo-bak &#xff08;3&#xff09;…...

el-Switch 开关二次确认

前言 最近在做毕设&#xff0c;有个需求是点击按钮控制用户的状态是否禁用&#xff0c;就看到element有个switch组件可以改造一下&#xff0c;就上网看了一下&#xff0c;结果为了这个效果忙活了很久。。。所以说记录一下&#xff0c;让大家少踩坑。 前置条件 先看完我的需求再…...

(二)丶RabbitMQ的六大核心

一丶什么是MQ Message Queue(消息队列&#xff09;简称MQ&#xff0c;是一种应用程序对应用程序的消息通信机制。在MQ中&#xff0c;消息以队列形式存储&#xff0c;以便于异步传输&#xff0c;在MQ中&#xff0c;发布者&#xff08;生产者&#xff09;将消息放入队列&#xff…...

微信小程序实现上下手势滑动切换

效果图 思路 实现一个微信小程序的复合滚动页面&#xff0c;主要通过Swiper组件实现垂直方向的轮播功能&#xff0c;每个轮播项内部使用Scroll-View组件来展示可垂直滚动的长内容&#xff0c;如图片和文本。 代码 <!-- wxml --> <view class"swiper-container…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...