算法:双指针

算法:双指针

    • 双指针
    • 快慢指针
    • 对撞指针
    • 总结


双指针

LeetCode 283.移动零

在这里插入图片描述

以上题目要求我们把所有0移动到数组的末尾,也就是说,我们要把数组转化为以下状态:

[ 非0区域 ] [ 0区域 ]

像这种把一个数组划分为多个区域的题型,就是数组划分。而数组划分非常适合使用双指针算法

对于这道题,我们可以用两个指针,对数组进行动态的区域划分。

在这里插入图片描述

其中dest指针维护一段区域,表示非0区域cur指针与dest之间的区域是0区域。而cur后面的区域是待处理区域

也就是我们的数组被划分为了以下情况:

[ 非0区域 ] [ 0区域 ] [ 待处理区域 ]

当我们的cur移动后,对于一个新的数据,就要根据条件来决定把它放到哪一个区域去。当cur指针走到末尾,数组就被处理为了:

[ 非0区域 ] [ 0区域 ]

也就是题目要求的样子了。

对于本题而言,如果新插入的数据是0,那就放到cur维护的区域里面,此时直接cur++即可;如果新插入的数据是非0,那么就放到dest的末尾,为了保证dest不会覆盖掉cur原本维护的0,因此要进行一个交换操作。

在这里插入图片描述

代码如下:

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

LeetCode 75.颜色分类

在这里插入图片描述

这一题也是一个区域划分问题,根据上一题的思路,我们可以把数组划分为以下状态:

[ 0区域 ] [ 1区域 ] [ 2区域 ]

相比于上一题,这次我们要划分出三个区域来,毫无疑问就需要更多的指针来维护区域,大致可以划分为:

[ 0区域 ] [ 1区域 ] [ 待处理 ] [ 2区域 ]

我们让维护0区域的指针left向右拓展,维护2区域的指针right向左拓展,以及利用cur指针向右遍历数组:

在这里插入图片描述

上图中,left指针左侧维护了一段0区域leftcur之间维护了一段1区域curright之间是待处理区域,right右侧是2区域。当cur往后遍历,如果遇到一个新的数据,就要决定把它放到哪一个区域去:

  1. 遇到0,就交换++leftcur的值,把0放到left后面一位,拓展left指针维护的区域
  2. 遇到1,就直接++cur,把1放到curleft之间
  3. 遇到2,就交换--rightcur的值,把2放到right的前面一位,拓展right维护的区域

要注意的是,当把0交给left后,cur++;但是当把2交给right后,cur不能移动。因为left后面的一位数一定是符合cur范围要求的,也就是区间(left, cur]之间的数据被交换到了cur的位置,此时不用判断被交换过来的数据。而right的前面一位数据是不确定的,也就是把区间(cur, right)之间的数据,交换给了cur。而(cur, right)之间的数据是待处理的不确定数据,因此还需要额外判断一次。比如上图中,right的前一位数据就是0,交换后状态如下:

在这里插入图片描述

可以看到,cur得到的数据是0,应该被放到left维护的区域去。

总代码如下:

class Solution
{
public:void sortColors(vector<int>& nums){int left = -1;int right = nums.size();int cur = 0;while (cur < right){if (nums[cur] == 0)swap(nums[++left], nums[cur++]);else if (nums[cur] == 2)swap(nums[--right], nums[cur]);//交换后不能cur++,进入下一轮循环在判断一次cur的值elsecur++;}}
};

快慢指针

LeetCode 202.快乐数

在这里插入图片描述

该题的意思是,每个数字的下一个数字是该数字所有位的平方和,比如 19 的下一位数字就是 1 2 + 9 2 = 82 1^{2} + 9^{2} = 82 12+92=82。一直以这个规则操作下去,会出现两种情况:

  1. 最后该数字变为1,那么该数字是快乐数
  2. 该数字陷入死循环,那么该数字不是快乐数
  • 比如19 -> 82 -> 68 -> 100 -> 1 ,最后19变成了1,所以19是一个快乐数
  • 比如2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4,可以发现其陷入了一个死循环,从4开始又以4结束,那么2就不是一个快乐数

这题的难点不在于如何计算下一位快乐数字,而在于如何判断一个数字陷入了死循环

对于这种循环问题,就可以使用快慢指针

快慢指针规则如下:

  1. 定义两个变量fastslow
  2. fast2步,slow走一步
  3. 如果fast走到终点,说明没有循环
  4. 如果fastslow相遇,说明陷入了循环

一开始fastslow都在起点:

在这里插入图片描述

fast走两步,slow走一步:

在这里插入图片描述

由于这是一个循环结构,当fast进入第二圈循环,slow还没有走完第一圈:

在这里插入图片描述

这个时候,由于slow的速度为1fast的速度为2,那么每次行动fastslow的距离就会缩短1,最后fast一定可以遇到slow

在这里插入图片描述

此时两者相遇,说明这是一个循环结构

因此代码逻辑如下:

  1. 定义两个变量,fastslowfast走两步,slow走一步
  2. 如果fast变成1,那么该数字是快乐数,返回true
  3. 如果fastslow相遇,那么有循环结构,该数字不是快乐数,返回false

代码如下:

class Solution 
{
public:int getNextNum(int n) //到下一个数字的函数{int num = 0;while (n){int tmp = n % 10;num += tmp * tmp;n /= 10;}return num;}bool isHappy(int n) {int fast = n;int slow = n;while (fast != 1){fast = getNextNum(getNextNum(fast));//fast走两步slow = getNextNum(slow);//slow走一步if (fast == slow && fast != 1)//两者相遇,有循环return false;} return true;//到这里说明fast = 1,是快乐数}
};

其中有一个注意点,就是条件fast == slow && fast != 1,这里一种情况就是fast虽然和slow相等,但是两者都为1,此时是快乐数。

比如数字1010 -> 1 -> 1slow走第一步就是1了,fast走两步也是1,此时两者相等。


LeetCode 141.环形链表

在这里插入图片描述

本题要求判断一个链表中有没有环结构,那就是一个循环问题,要使用快慢指针

我们刚刚已经讲解过快慢指针了,现在我们直接说明代码逻辑:

  1. 定义两个指针fastslowfast走两步,slow走一步
  2. 如果fastnullptr,说明链表无环,返回true
  3. 如果fastslow相遇,说明有环,返回false

代码如下:

class Solution {
public:bool hasCycle(ListNode* head){ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow)return true;}return false;}
};

注意事项:

  1. 进入循环时,因为fast要走两步,因此要判断fast->next是不是空指针,否则fast->next-->next就是访问空指针行为

LeetCode 142.环形链表II

在这里插入图片描述

这道题要求我们求出环形链表的环入口,这就麻烦了,通过之前的fastslow的快慢指针追击问题,我们已经可以判断是否存在环结构了,那么我们要如何求环入口呢?

看到以下示意图:

在这里插入图片描述

现在slowfast刚好相遇,参数含义如下:

L:从起点到环入口的距离
C:环周长
X:相遇点和环入口的距离

由于fast的速度是slow的两倍,当slow走的距离是L + X,因此此时fast走了2(L + X)的距离。

又由于fast一定经过了起点到入口的L距离,因此此时fast在环中走了2(L + X) - L = L + 2X的距离。

假设fast已经在环中转了n圈,因此此时fast在环中走了nC + X的距离

那么可以列出公式:

n C + X = L + 2 X nC + X = L + 2X nC+X=L+2X

变形得到:

n C − X = L \mathbf{{\color{Red} nC - X = L} } nCX=L

这个公式具有重大意义,L代表起点到入口的距离,nC代表n个环周长,X代表当前相遇点与入口的距离。

nC -X整体可以看成(n - 1)C + (C - X)C - X就代表相遇点开始与环入口的优弧的长度

此时如果让一个指针A从起点开始走L的距离所用的时间,和让一个指针B从相遇点开始走n - 1圈外加一个C - X的距离所用的时间是一致的。由于相遇点与环入口距离已经是X了,那么指针B最后刚好会走到环入口。而指针A从入口开始走L到达的地方也是环入口,因此两者相遇!

通过这个公式可知:让一个指针从起点开始走,一个指针从相遇点开始走,两者会在环入口相遇

因此我们的代码逻辑如下:

  1. 定义两个指针fastslowfast走两步,slow走一步
  2. 如果fastnullptr,说明链表无环,返回nullptr
  3. 如果fastslow相遇,说明有环,开始找环入口
  • 在相遇点定义一个指针B,也就是B = slow;在起点定义一个指针A,也就是A = head
  • 两个指针各自行动,速度一致,最后AB相遇的地方就是环入口
  • 返回AB

代码如下:

class Solution
{
public:ListNode* detectCycle(ListNode* head){ListNode* fast = head;ListNode* slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (slow == fast)  // 有环,开始找入口{ListNode* A = head;ListNode* B = slow;while (A != B)//A与B相遇点,就是环入口{A = A->next;B = B->next;}return A;}}return nullptr; //没有环,返回空指针}
};


对撞指针

LCR 179.查找总价格为目标值的两个商品

在这里插入图片描述

这道题给了一个升序数组,要求我们求出数组中任意两个值的和刚好为target

该数组有一个特点:有序数组。像这种在一个有序区间中查找两个元素,计算得到固定值的题型,就可以使用对撞指针

如果我们直接暴力解法的话,那就是枚举所有两两一对的元素组,直到某一对刚好和为target,时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)

假设现在的数组为[8, 21, 27, 34, 52]target = 61

因为数组具有单调性,我们可以一开始就枚举最左侧和左右侧的两个元素

在这里插入图片描述

当前8 + 52 = 6061小,说明我们需要一个更大的值来增大当前总和。那么由于数组升序,我们只需要left++即可:

在这里插入图片描述

当前21 + 52 = 7361大,说明我们需要一个更小的值来缩小当前总和。那么由于数组升序,我们只需要right--即可:

在这里插入图片描述

当前21 + 34 = 5561小,说明我们需要一个更大的值来增大当前总和。那么由于数组升序,我们只需要left++即可:

在这里插入图片描述

当前27 + 34 = 61,我们就找到了目标值,返回leftright下标即可。

正是由于数组单调性,我们可以通过比大小来进行指针的调整,来决定当前总值要变大还是变小,如果最后leftright相遇了,说明不存在这样的和。

为什么可以这样优化呢?看到这个例子:

在这里插入图片描述
对于34而言,其要去枚举除了自己以外的所有值,但是当前21 + 34 = 5561小,如果把21改为8,那只总和只会更小,因此我们只需要再枚举比21大的值即可。也就是通过单调性,免去了很多不必要的枚举行为

代码如下:

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

LeetCode 11.盛水最多的容器

在这里插入图片描述

本题要求存储的最大水量,其实也就是两个下标之间的距离right - leftmin(height[left], height[right])的乘积。

如果暴力枚举,那么就是枚举出每一对下标,然后求出最大面积,时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)

本题也可以使用双指针的算法,水量的值与right - leftmin(height[left], height[right])两个变量正相关,如果我们利用两个指针向内枚举,那么right - left这个值是一直在减小的,也就是有一项有单调性

对于这种,如果利用对撞指针下标向内枚举,对组成结果的某一项变量的影响是单调的,就可以考虑对撞指针

假设我们已经在边界上定义好了leftright指针:

在这里插入图片描述

第一个问题就是,应该以什么规则进行向内移动指针?

移动的过程中,水的宽度的一直递减的,那么我们就要尽可能找到height高的元素,来拔高水量。

比如说当前的两个高度为37,由于水的高度取决于较低的那个元素,因此高度为7的指针无论怎么向内移动,水高度都不会超过3,而这个过程中宽度又是单调递减的,因此right指针向内移动,所有的结果都小于当前的水量。

比如这个情况:

在这里插入图片描述

虽然right向内移动,找到了比7更大的元素,但是由于此时水高度取决于3,而且宽度还变小了,最后总水量没有变大。

因此每次都把比元素值较小的那个指针向内移动

代码如下:

class Solution
{
public:int maxArea(vector<int>& height){int left = 0;int right = height.size() - 1;int ret = -1;while (left <= right){int w = right - left;//宽度int h = min(height[left], height[right]);//高度ret = max(ret, w * h);//更新最大水量//每次都让较小的元素向内枚举if (height[left] > height[right])right--;elseleft++;}return ret;}
};

总结

双指针

  • 数组划分使用双指针算法。

一般处理为[A区域][B区域]...[待处理]这样的格式,当新元素符合哪一个区域特性,就放到哪一个区域中。

快慢指针

  • 循环问题,利用快慢指针来判断是否有循环。

相遇就是有环,如果fast走到结尾就是无环。

如果要找循环开始节点,一个指针从头开始走,一个指针从相遇点开始走,最后会在环入口相遇。

对撞指针

  • 在一个有序区间中查找两个元素,计算得到固定值的题型,使用对撞指针。

  • 如果利用对撞指针下标向内枚举,对组成结果的影响是单调的,就可以考虑对撞指针。

对撞指针的特点在于利用单调性减小搜索范围。


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/310149.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

顺序表(C语言版)

前言&#xff1a;本篇文章我们来详细的讲解一下顺序的有关知识&#xff0c;这篇文章中博主会以C语言的方式实现顺序表。以及用顺序表去实现通讯录的代码操作。 目录 一.顺序表的概念 二.顺序表的分类 1.静态顺序表 三.动态顺序表的实现 1.顺序表的初始化 2.顺序表的尾插…

【Entity Framework】聊一聊EF中继承关系

【Entity Framework】聊一聊EF中继承关系 文章目录 【Entity Framework】聊一聊EF中继承关系一、概述二、实体类型层次结构映射三、每个层次结构一张表和鉴别器配置四、共享列五、每个类型一张表配置六、每个具体类型一张表配置七、TPC数据库架构八、总结 一、概述 Entity Fra…

【linux】set ff=unix、linux设置文件格式

文章目录 一、文件格式二、如何查看文件格式三、设置文件格式、set ffunix四、查看unix与dos的区别 一、文件格式 当我们打开sh脚本时发现有时候格式是unix(LF) ,有时候是windows(CR LF) 。如下图&#xff1a; 文件格式影响了文件中的换行符 linux中sh类型的文件一般要设置为…

【网络编程】Linux网络内核结构以及分布剖析

hello &#xff01;大家好呀&#xff01; 欢迎大家来到我的网络编程系列之Linux网络内核结构以及分布剖析&#xff0c;在这篇文章中&#xff0c;你将会学习到在Linux内核中如何实现网络数据的输入和输出的&#xff0c;并且我会给出源码进行剖析&#xff0c;以及手绘UML图来帮助…

Office 365卡顿怎么办?SD-WAN可以解决

随着数字化浪潮的推进&#xff0c;Office 365等云办公应用已成为企业日常运营不可或缺的工具。然而&#xff0c;许多企业在使用Office 365时遭遇了网络卡顿的难题&#xff0c;给工作人员带来诸多不便。随着SD-WAN技术的成熟和普及&#xff0c;这一难题得到了有效的解决。 Offic…

机器人方向控制中应用的磁阻角度传感芯片

磁阻传感器提供的输出信号几乎不受磁场变动、磁温度系数、磁传感器距离与位置变动影响&#xff0c;可以达到高准确度与高效能&#xff0c;因此相当适合各种要求严格的车用电子与工业控制的应用。所以它远比采用其它传感方法的器件更具有优势。 机器人的应用日渐广泛&#xff0…

鸿蒙开发学习笔记第一篇--TypeScript基础语法

目录 前言 一、ArkTS 二、基础语法 1.基础类型 1.布尔值 2.数字 3.字符串 4.数组 5.元组 6.枚举 7.unkown 8.void 9.null和undefined 10.联合类型 2.条件语句 1.if语句 1.最简单的if语句 2.if...else语句 3.if...else if....else 语句 2.switch语句 5.函数…

OpenResty,Nginx实现接口验签与黑名单控制

介绍 nginx与openresty是两种优秀知名的7层负载均衡软件&#xff0c;nginx以其出色的性能和稳定性成为首选&#xff0c;而openresty则是在Nginx基础上构建的&#xff0c;支持嵌入Lua语言&#xff0c;大幅提升了开发效率。 安装OpenResty 版本 openresty-1.25.3.1-win64下载地…

机器学习和深度学习--李宏毅(笔记与个人理解)Day11-12

Day11 when gradient is small…… 怎么知道是局部小 还是鞍点&#xff1f; using Math 这里巧妙的说明了hessan矩阵可以决定一个二次函数的凹凸性 也就是 θ \theta θ 是min 还是max&#xff0c;最后那个有些有些 哈 是一个saddle&#xff1b; 然后这里只要看hessan矩阵是不…

STM32学习和实践笔记(5):时钟树

STM32一共有4个时钟源。外部时钟高低速各一个&#xff0c;内部时钟高低速各一个。 外部高速时钟是&#xff1a;4-16MHZ的HSE OSC。HS表示高速high speed. E表示外部的external。开发板该处安装的8M晶振。 外部低速时钟是&#xff1a;32.768KHz的LSI OSC。LS表示高速low speed…

Go——面向对象

一. 匿名字段 go支持只提供类型而不写字段名的方式&#xff0c;也就是匿名字段&#xff0c;也称为嵌入字段。 同名字段的情况 所以自定义类型和内置类型都可以作为匿名字段使用 指针类型匿名字段 二.接口 接口定义了一个对象的行为规范&#xff0c;但是定义规范不实现&#xff…

强大的压缩和解压缩工具 Keka for Mac

Keka for Mac是一款功能强大的压缩和解压缩工具&#xff0c;专为Mac用户设计。它支持多种压缩格式&#xff0c;包括7z、Zip、Tar、Gzip和Bzip2等&#xff0c;无论是发送电子邮件、备份文件还是节省磁盘空间&#xff0c;Keka都能轻松满足用户需求。 这款软件的操作简单直观&…

用c++实现串匹配问题、选择排序

5.2.2 串匹配问题 【问题】 给定两个字符串S和T&#xff0c;在主串S中查找子串T的过程称为串匹配(string matching,也称模式匹配&#xff09;&#xff0c;T称为模式。在文本处理系统、操作系统、编译系统、数据库系统以及 Internet 信息检索系统中&#xff0c;串匹配是使用最频…

分布式系统:缓存与数据库一致性问题

前言 缓存设计是应用系统设计中重要的一环&#xff0c;是通过空间换取时间的一种策略&#xff0c;达到高性能访问数据的目的&#xff1b;但是缓存的数据并不是时刻存在内存中&#xff0c;当数据发生变化时&#xff0c;如何与数据库中的数据保持一致&#xff0c;以满足业务系统…

Linux shell编程学习笔记46:awk命令的由来、功能、格式、选项说明、版权、版本

0 前言 在编写Linux Shell脚本的过程中&#xff0c;我们经常要对Linux命令执行的结果进行分析和提取&#xff0c;Linux也在文本分析和提取这方面提供了不少的命令。比如我们之前研究过的cut命令。 Linux shell编程学习笔记43&#xff1a;cut命令https://blog.csdn.net/Purple…

史上最全excel导入功能测试用例设计(以项目为例)

web系统关于excel的导入导出功能是很常见的&#xff0c;通常为了提高用户的工作效率&#xff0c;在维护系统中的一些数据的时候&#xff0c;批量导入往往比一个一个添加或者修改快很多。针对导入功能的测试&#xff0c;往往会有很多种情况&#xff0c;现在针对平时项目中遇到的…

Excel·VBA二维数组S形排列

与之前的文章《ExcelVBA螺旋数组函数》将一维数组转为二维螺旋数组 本文将数组转为S形排列的二维数组&#xff0c;类似考场座位S形顺序 Function S形排列(ByVal arr, ByVal num_rows&, ByVal num_cols&, Optional ByVal mode$ "row")将数组arr转为num_rows…

Home Assistant OS转 Hassio Supervisor(docker 版本)

这是一个失败案例&#xff0c;请忽略。 原因 HAOS缺点&#xff1a;系统不是很好用&#xff0c;无法满足我在上面使用python开发插件的小需求&#xff08;或许有方法满足&#xff0c;但是我没找到&#xff09;。 HAOS优点&#xff1a;方便安装&#xff0c;配置非常方便。 数据…

UE5学习日记——实现自定义输入及监听输入,组合出不同的按键输入~

UE5的自定义按键和UE4有所不同&#xff0c;在这里记录一下。 本文主要是记录如何设置UE5的自定义按键&#xff0c;重点是学会原理&#xff0c;实际开发时结合实际情况操作。 输入映射 1. 创建输入操作 输入操作并不是具体的按键映射&#xff0c;而是按键的激活方式&#xff0…

面试官:说一说CyclicBarrier的妙用!我:这个没用过...

写在开头 面试官&#xff1a;同学&#xff0c;AQS的原理知道吗&#xff1f; 我&#xff1a;学过一点&#xff0c;抽象队列同步器&#xff0c;Java中很多同步工具都是基于它的… 面试官&#xff1a;好的&#xff0c;那其中CyclicBarrier学过吗&#xff1f;讲一讲它的妙用吧 我&…