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

算法思想之双指针(一)

news 来源：原创 2025/9/3 8:48:38

欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之双指针(一)
发布时间：2025.4.4
隶属专栏：算法

在这里插入图片描述

双指针算法介绍
- 对撞指针：
- 快慢指针：
例题
- 移动零
- - 题目链接
  - 题目描述
  - 算法思路
  - 代码实现
- 复写零
- - 题目链接
  - 题目描述
  - 算法思路
  - 代码实现
- 快乐数
- - 题目链接
  - 题目描述
  - 算法思路
  - 代码实现
- 盛最多水的容器
- - 题目链接
  - 题目描述
  - 算法思路
  - 代码实现

双指针算法介绍

常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。

对撞指针：

⼀般⽤于顺序结构中，也称左右指针。

对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
- left == right （两个指针指向同一个位置）
- left > right （两个指针错开）

快慢指针：

又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的⼀种就是：

在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

例题

移动零

题目链接

283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

算法思路

在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零数序列的最后一个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在 cur 遍历期间，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。

代码实现

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();for(int dest = -1, cur = 0; cur < n; cur++){if(nums[cur] != 0){swap(nums[dest+1], nums[cur]);dest++;}}}
};

在这里插入图片描述

复写零

题目链接

1089.复写零

题目描述

给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。
示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 9

算法思路

如果从前向后进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。但是从后向前复写的时候，我们需要找到最后一个复写的数，因此我们的大体流程分两步：

i. 先找到最后一个复写的数；
ii. 然后从后向前进行复写操作。

代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int cur = 0, dest = -1;// 找到最后覆写的数while(dest < n){if(arr[cur] == 0)dest+=2;elsedest++;if(dest >= n-1)break;cur++;}// 特殊情况处理if(dest == n){arr[n-1] = 0;dest-=2;cur--;            }// 进行复写操作while(cur >= 0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur --;}else{arr[dest--] = arr[cur--];}}}
};

在这里插入图片描述

快乐数

题目链接

202.快乐数

题目描述

编写一个算法来判断一个数n是不是快乐数。
快乐数 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

如果n是快乐数就返回 true ；不是，则返回 false 。
示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：
1 <= n <= 231 - 1

算法思路

根据上述的题目分析，我们可以知道，当重复执行 x的时候，数据会陷入到一个循环之中。而快慢指针有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是1 ，那么这个数一定是快乐数；如果相遇位置不是1的话，那么就不是快乐数。

代码实现

class Solution {
public:int BitSum(int n){int num = 0;while(n>0){int x = n %10;n /= 10;num+=x*x;}return num;}bool isHappy(int n) {int slow = n, fast = BitSum(n);while(slow != fast){slow = BitSum(slow);fast = BitSum(BitSum(fast));} return slow == 1;}
};

在这里插入图片描述

盛最多水的容器

题目链接

11. 盛最多水的容器

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

算法思路

设两个指针 left ，right分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left])
容器的左边界为 height[left] ，右边界为 height[right] 。
为了方便叙述，我们假设左边边界小于右边边界。
如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：

容器的宽度⼀定变小。
由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是⼀定不会超过右边的柱子高度，因此容器的容积可能会增大。
如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会
超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小的。

由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。

当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案。

代码实现

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

在这里插入图片描述

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

算法思想之双指针(一)

欢迎拜访：雾里看山-CSDN博客本篇主题：算法思想之双指针(一) 发布时间：2025.4.4 隶属专栏：算法目录双指针算法介绍对撞指针：快慢指针： 例题移动零题目链接题目描述算法思路代码实现复写零题目链接题目描…...

编程日记 2025/9/3 8:48:38

Pascal语言的设备管理

Pascal语言的设备管理引言在计算机科学中，设备管理是操作系统的重要组成部分之一。设备管理指的是操作系统对外部设备的控制和协调，实现对各种设备的有效利用。Pascal语言作为一种教育性编程语言，虽然最初并不是为了直接进行设备管理而设…...

编程日记 2025/9/3 8:47:34

【MySQL】DML：添加-修改-删除数据 (数据操作语言) 学习笔记

DML (数据操作语言) 学习笔记 1. 数据表结构首先创建员工表 employee： CREATE TABLE employee (id int unsigned NOT NULL AUTO_INCREMENT COMMENT ID,username varchar(20) NOT NULL COMMENT 用户名,password varchar(32) DEFAULT 123456 COMMENT 密码,name va…...

编程日记 2025/8/29 11:07:24

React编程高级主题：背压（Backpressure）处理

文章目录 **5.1 背压（Backpressure）概述****5.1.1 缓冲（Buffer）****1. 基本概念****2. 缓冲的实现方式****3. 适用场景****4. 潜在问题** **5.1.2 丢弃（Drop）****1. 基本概念****2. 丢弃的实现方式****3. 适…...

编程日记 2025/8/30 18:47:07

Spring IoCDI

IoC容器前⾯我们提到IoC控制反转， 就是将对象的控制权交给Spring的IOC容器 ，由IOC容器创建及管理对象。也就是bean的存储. 在类上⾯添加 RestController 和 Controller 注解, 就是把这个对象交给Spring管理 , Spring 框架启动时就会加载该类. 把对象…...

编程日记 2025/8/30 3:21:14

COBOL语言的数据库交互

COBOL语言的数据库交互引言随着信息技术的不断发展，数据库管理系统（DBMS）已经成为现代应用程序中不可或缺的组成部分。在众多编程语言中，COBOL（Common Business-Oriented Language）以其在商业应用中的稳…...

编程日记 2025/9/2 16:44:04

【C++11（中）】—— 我与C++的不解之缘（三十一）

一、可变参数模版基本语法： C11支持可变参数模版，简单来说就是支持可变数量参数的函数模版或者类模版； 可变数目的参数被称为参数包，存在两种参数包：模版参数包(表示0个或者多个模版参数)，函数参数包(表示…...

编程日记 2025/9/2 16:53:14

JavaScript学习19-事件类型之鼠标事件

1. 2. 3....

编程日记 2025/8/30 12:22:42

文件或目录损坏且无法读取：数据恢复的实战指南

在数字化时代，数据的重要性不言而喻。然而，在日常使用电脑、移动硬盘、U盘等存储设备时，我们难免会遇到“文件或目录损坏且无法读取”的提示。这一提示如同晴天霹雳，让无数用户心急如焚，尤其是当这些文件中存储着重要的…...

编程日记 2025/8/26 4:27:14

python爬虫：小程序逆向实战教程

根据我之前发表的文章，我们进行延伸实战https://blog.csdn.net/weixin_64809364/article/details/146981598?spm1001.2014.3001.5501 1. 想要爬取什么小程序，我们进行搜索 2. 找到我们vx小程序的文件地址，我们就可以进行破解破解步骤强看…...

编程日记 2025/9/3 1:32:40

第二十节课：python实例五：身体质量指数BMI计算

python实例五：身体质量指数BMI计算一、问题分析 BMI计算公式： BMI 体重(kg) / 身高(m)^2国际与国内标准对比分类国际标准国内标准偏瘦<18.5<18.5正常18.5-2518.5-24偏胖25-3024-28肥胖≥30≥28 二、实现要点输入处理 # 同时接收身高体重…...

编程日记 2025/9/1 16:04:18

八、重学C++—动态多态（运行期）

上一章节： 七、重学C—静态多态（编译期）-CSDN博客https://blog.csdn.net/weixin_36323170/article/details/146999362?spm1001.2014.3001.5502 本章节代码： cpp/dynamicPolymorphic.cpp CuiQingCheng/cppstudy - 码云 - 开源中…...

编程日记 2025/8/31 1:55:03

思维链 Chain-of-Thought（COT）

思维链 Chain-of-Thought（COT）：思维链的启蒙 3. 思维链 Chain-of-Thought（COT）存在问题？2. 思维链 Chain-of-Thought（COT）是思路是什么？1. 什么是思维链 Chain-of-Thoug…...

编程日记 2025/8/28 9:55:45

React框架的Fiber架构

以下是关于 Fiber 架构的系统梳理：一、Fiber 架构的出现背景 React 15 及之前的问题同步递归渲染：虚拟DOM的diff过程不可中断，导致主线程长时间阻塞。掉帧问题：复杂组件树渲染时，用户交互无法及时响应。无法实现增量渲染：无法拆分任务优先级，无法利用浏览器空闲时间。…...

编程日记 2025/8/30 0:58:39

PCI与PCIe接口的通信架构是主从模式吗？

PCI（Peripheral Component Interconnect）总线在通信架构上本质是主从模式，但其具体实现和角色分配在不同版本（如传统PCI与PCI Express）中存在差异。以下是详细分析： 传统PCI总线的主从模式 (1) 基本架构主…...

编程日记 2025/8/29 13:18:23

【2011】【论文笔记】THz保护文化遗产——

前言类型太赫兹 + 文化保护太赫兹 + 文化保护太赫兹+文化保护期刊 I E E E T R A N S A C T I O N S O N T E R A H E R...

编程日记 2025/8/26 6:03:36

状态机思想编程练习

状态机实现LED流水灯本次实验，我们将利用状态机的思想来进行Verilog编程实现一个LED流水灯，并通过Modelsim来进行模拟仿真，再到DE2-115开发板上进行验证。首先进行主要代码的编写。 module led (input sys_clk,input sys_…...

编程日记 2025/8/31 12:56:51

三部门新政力推智能家居居然智家数智化转型迎利好东风

2025年3月，工业和信息化部、教育部、市场监管总局联合印发《轻工业数字化转型实施方案》，明确提出重点培育智能家居、智能穿戴、智能骑行、智慧养老等消费端场景，深化人工智能技术在家电、家具等领域的应用，推动产业链供应链智能化…...

编程日记 2025/8/26 6:03:33

CCF GESP C++编程七级认证真题 2025年3月

C 七级 2025 年 03 月题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B A B C B B B A D D A C B B D 一、单选题第 1 题下列哪个选项是C中的关键字？ A. function B. class C. method D. object 第 2 题下面代码输出的是（） int main()…...

编程日记 2025/8/29 7:08:59

【MySQL】navicat16 result字段识别不了

在mysql里面使用result字段打印出来为空之后换了个字段命名使用outcome 成功能打印出来了。。不知道是不是版本的问题...

编程日记 2025/8/26 6:03:29

【教学类-102-02】自制剪纸图案（留白边、沿线剪）02——Python+PS自动化添加虚线边框

背景需求： 01版本实现了对透明背景png图案边界线的扩展，黑线实线描边【教学类-102-01】自制剪纸图案（留白边、沿线剪）01-CSDN博客文章浏览阅读974次，点赞15次，收藏7次。【教学类-102-01】自制剪纸图案（留白边、沿线剪）01https://blog.csdn.net/reasonsummer/article…...

编程日记 2025/8/28 11:41:03

CExercise_05_1函数_1.1素数(要对键盘录入的数据做参数校验)

题目： 编写函数实现以下功能： 键盘录入一个正整数，请判断它是否是一个素数，然后控制台输出对应的结果。要对键盘录入的数据做参数校验，素数是一个大于1的自然数，它仅能被1和自身整除。关键点分析&#xf…...

编程日记 2025/8/30 0:58:41

运算放大器（五）电压比较器

比较器在最常用的简单集成电路中排名第二，仅次于排名第一的运算放大器。电压比较器是一种用来比较输入信号电压与参考电压大小，并将比较结果以高电平或低电平形式输出的一种信号处理电路，广泛应用于各种非正弦波的产生和变换电路中&#xf…...

编程日记 2025/8/31 15:29:03

蓝桥杯_PCF8591

目录一前言二引言三 PCF8591介绍 （1）I2C通信 （2）原理图中的8591 四代码层面 （1）根据题目所给的示范代码，实现ADC 1 为什么需要返回值，同时返回值是unsigned char&#x…...

编程日记 2025/9/1 8:57:46

Windows修改hosts文件让向日癸软件联网

Windows修改hosts文件让向日癸软件联网前言一、查看向日葵软件使用的网址及IP1.清除dns记录2.打开向日葵软件并将dns记录导出txt 二、修改Windows服务器的hosts文件1.winx选择Windows PowerShell(管理员)2.在Windows PowerShell中输入如下内容：3.在hosts文件最后添…...

编程日记 2025/8/30 12:07:14

[MySQL初阶]MySQL数据类型

MySQL数据类型 1. 数据类型分类2. 数值类型2.1 tinyint类型2.2 bit类型2.3 float类型2.4 decimal类型3. 字符串类型3.1 char3.2 varchar3.3 日期和时间类型3.4 enum和set1. 数据类型分类数据库中的类型决定了在存储位置中，占据的空间大小以及如何识别的问题。 2. 数值类型 2…...

编程日记 2025/8/31 22:53:10

JS用ES6和ES5分别实现：8字节长整数和字节数组的互转

🧑 博主简介：CSDN博客专家，历代文学网（PC端可以访问：https://literature.sinhy.com/#/?__c1000，移动端可微信小程序搜索“历代文学”）总架构师，15年工作经验，精通Java编…...

编程日记 2025/8/27 13:26:18

【学Rust写CAD】29 Alpha256结构体（alpha256.rs）

源码 #[derive(Clone, Copy)] pub struct Alpha256(u32);impl Alpha256{#[inline]pub fn from(alpha:u32)->Alpha256{Alpha256(alpha1)}// Calculates 256 - (value * alpha256) / 255 in range [0,256],// for [0,255] value and [0,256] alpha256.#[inline]fn alpha_mul_…...

编程日记 2025/9/1 3:18:38

目录

双指针算法介绍

对撞指针：

快慢指针：

例题

移动零

题目链接

题目描述

算法思路

代码实现

复写零

题目链接

题目描述

算法思路

代码实现

快乐数

题目链接

题目描述

算法思路

代码实现

盛最多水的容器

题目链接

题目描述

算法思路

代码实现

相关文章：