【算法详解】双指针

双指针

常见的双指针有两种形式,一种是对撞指针,一种是左右指针。

1. 双指针简介

双指针(Two Pointers):指的是在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针进行访问,从而达到相应的目的。如果两个指针方向相反,则称为「对撞指针」。如果两个指针方向相同,则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表,则称为「分离双指针」。

在数组的区间问题上,暴力算法的时间复杂度往往是 O ( n 2 ) O(n^2) O(n2)。而双指针利用了区间「单调性」的性质,可以将时间复杂度降到 O ( n ) O(n) O(n)

2. 对撞指针

对撞指针:指的是两个指针 leftright 分别指向序列第一个元素和最后一个元素,然后 left 指针不断递增,right 不断递减,直到两个指针的值相撞(即 left == right),或者满足其他要求的特殊条件为止。

对撞指针一般用于顺序结构中,也称为左右指针。

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

2.2 对撞指针伪代码模板

left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值

2.3 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题:

  • 查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。
  • 字符串反转问题:反转字符串、回文数、颠倒二进制等问题。

下面我们根据具体例子来讲解如何使用对撞指针来解决问题。

盛最多水的容器

题目链接

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

题目大意

给定 n 个非负整数 a1, a2, ..., an,每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0)

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

解题思路

思路 1:对撞指针

设两个指针 leftright 分别指向容器的左右两个端点,此时容器的容积为:

v = (right - left) * min( height[right], height[left])

容器的左边界为 height[left],右边界为 height[right]

为了方便叙述,我们假设「左边边界」小于「右边边界」。

如果此时我们固定一个边界,改变另一个边界,水的容积会有如下变化形式:

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

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

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

解题代码

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

3.快慢指针

快慢指针:指的是两个指针从同一侧开始遍历序列,且移动的步长一个快一个慢。移动快的指针被称为 「快指针(fast)」,移动慢的指针被称为「慢指针(slow)」。两个指针以不同速度、不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或者满足其他特殊条件时为止。

快慢指针,又称为乌龟赛跑算法,其基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

快慢指针是指两个指针在链表上移动的速度不同,常用于解决环形链表相关的问题。快指针每次移动两步,慢指针每次移动一步,因此快指针会比慢指针快一倍。快慢指针的经典应用包括:

  • 判断一个链表是否存在环。
  • 找到链表的中间节点。
  • 判断链表是否为回文结构。

3.1 快慢指针求解步骤

  1. 使用两个指针 slowfastslow 一般指向序列第一个元素,即:slow = 0fast 一般指向序列第二个元素,即:fast = 1
  2. 在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即 slow += 1。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即 fast += 1
  3. 到快指针移动到数组尾端(即 fast == len(nums) - 1),或者两指针相交,或者满足其他特殊条件时跳出循环体。

3.2 快慢指针伪代码模板

slow = 0
fast = 1
while 没有遍历完:
    if 满足要求的特殊条件:
        slow += 1
    fast += 1
return 合适的值

3.3 快慢指针适用范围

快慢指针一般用于处理数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。

下面我们根据具体例子来讲解如何使用快慢指针来解决问题。

删除有序数组中的重复项

题目链接

26. 删除有序数组中的重复项 - 力扣(LeetCode)

题目大意

描述:给定一个有序数组 nums

要求:删除数组 nums 中的重复元素,使每个元素只出现一次。并输出去除重复元素之后数组的长度。

说明

  • 不能使用额外的数组空间,在原地修改数组,并在使用 O ( 1 ) O(1) O(1) 额外空间的条件下完成。

示例

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。


输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
解题思路
思路 1:快慢指针

因为数组是有序的,那么重复的元素一定会相邻。

删除重复元素,实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下:

  • 定义两个快慢指针 slowfast。其中 slow 指向去除重复元素后的数组的末尾位置。fast 指向当前元素。
  • slow 在后, fast 在前。令 slow = 0fast = 1
  • 比较 slow 位置上元素值和 fast 位置上元素值是否相等。
    • 如果不相等,则将 slow 后移一位,将 fast 指向位置的元素复制到 slow 位置上。
  • fast 右移 1 位。
  • 重复上述步骤,直到 fast 等于数组长度。
  • 返回 slow + 1 即为新数组长度。

1.png

解题代码

int removeDuplicates(vector<int>& nums) {
    if(nums.empty()) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.size()){
        if(nums[p] != nums[q]){
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【uniapp】个推H5号码认证一键登录(附代码)

前言 最近在做APP、h5产品&#xff0c;登陆注册成了难题。邮箱验证多数人不会使用&#xff0c;还是短信方便点&#xff0c;短信可以采用号码认证和验证码的方式&#xff0c;前者稍微便宜的&#xff0c;关于性价比和上手程度我推荐个推&#xff0c; 于是有了今天这篇案例记录&a…

谷歌浏览器插件开发速成指南:弹窗

诸神缄默不语-个人CSDN博文目录 本文介绍谷歌浏览器插件开发的入门教程&#xff0c;阅读完本文后应该就能开发一个简单的“hello world”插件&#xff0c;效果是出现写有“Hello Extensions”的弹窗。 作为系列文章的第一篇&#xff0c;本文还希望读者阅读后能够简要了解在此基…

爬取日本常用汉字秘籍

前言 昨天投简历时遇到了这样的一个笔试。本以为会是数据结构算法之类的没想到直接发了一个word直接提需求&#xff0c;感觉挺有意思就写了这篇文章&#xff0c;感兴趣的朋友可以看看。 1. 网页内容解析 首先&#xff0c;我们通过请求网页获取到日本常用汉字的链接列表。然后…

计算机网络——38报文完整性

报文完整性 数字签名 数字签名类比于手写签名 发送方数字签署了文件&#xff0c;前提是他是文件的拥有者/创建者可验证性&#xff0c;不可伪造性&#xff0c;不可抵赖性 谁签署&#xff0c;接收方可以向他人证明是他&#xff0c;而不是其他人签署了这个文件签署了什么&#…

Web攻击越发复杂,企业如何保护云上业务

如今&#xff0c;电子政务、电子商务、网上银行、网上营业厅等依托Web应用&#xff0c;为广大用户提供灵活多样的服务。在这之中&#xff0c;流量攻击堪称是Web应用的最大敌人&#xff0c;黑客通过流量攻击获取利益、竞争对手雇佣黑客发起恶意攻击、不法分子通过流量攻击瘫痪目…

ShardingSphere-JDBC使用时出现雪花算法id无法生成

出现报错&#xff1a; 这是sql 尝试1&#xff1a; 这里改成Long 还是报错 尝试2&#xff1a;将配置重写 删除 props: # 主键生成器属性配置worker-id: 1 # Snowflake算法中的workerId配置解决&#xff01;

基于Difussion图像、视频生成综述

2024年大年初七&#xff08;02.16&#xff09;OpenAI 发布视频生成模型 Sora 在各大平台转疯了&#xff0c;和2022年发布ChatGPT3.5时一样的疯狂。在开工第一天&#xff0c;我就去官网上看了 Sora 的技术报告&#xff0c;遗憾的是&#xff0c;在这份技术报告中只披露了一些模型…

苹果证书分类及作用详解,助力开发者高效管理应用程序

转载&#xff1a;苹果证书的作用及分类详解 摘要&#xff1a;本文将详细介绍苹果证书的作用及分类&#xff0c;包括企业证书、开发者证书、 推送证书、分发证书和MDM证书&#xff0c;帮助开发者了解如何正确使用和管理这些证书&#xff0c; 提升应用程序的开发和发布效率。 引…

基于SSM的校园二手物品交易平台论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本校园二手物品交易平台就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据…

基于单片机分舱式电开水炉位控制系统

**单片机设计介绍&#xff0c;基于单片机分舱式电开水炉位控制系统 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机分舱式电开水炉位控制系统概要主要涉及通过单片机对电开水炉的各个舱位进行精确控制&#xff0c;实现水位、温度…

C++中的指针:其重要性与应用深度解析

在C编程语言的世界中&#xff0c;指针无疑是一个至关重要的概念。它不仅是C语言的核心特性之一&#xff0c;更是实现高效、灵活编程的关键工具。理解并熟练掌握指针的使用&#xff0c;对于提升程序设计能力、优化代码性能以及深入理解计算机内存模型具有不可估量的价值。 为了帮…

HarmonyOS 应用开发-ArkUI(ets)仿“腾讯新闻”APP

一、效果演示 1、新闻列表页 2、新闻详情页、图片展示页 3、视频页 4、动态页 二、 流程图 –本来自定义了视频的控制栏的&#xff0c;但是发现VideoController()控制器的bug会导致控制器失效&#xff0c;所以没继续做。视频页先不搞了。 三、文件组织&#xff08;“我的页面…

mac上搭建鸿蒙开发环境(2024)

开发环境 设备 MacBook Pro 芯片 Apple M1 系统 11.4 内存 16 GB 一、下载公开版本的DevEco Studio 华为官方目前对外提供的版本是DevEco Studio 3.1&#xff0c;可在官网下载https://developer.huawei.com/consumer/cn/deveco-studio/ 因为目前还在学习阶段&#xff0c;…

OpenHarmony实战:轻量系统STM32F407芯片移植案例

介绍基于STM32F407IGT6芯片在拓维信息Niobe407开发板上移植OpenHarmony LiteOS-M轻量系统&#xff0c;提供交通、工业领域开发板解决方案。 移植架构采用Board与SoC分离方案&#xff0c;使用arm gcc工具链Newlib C库&#xff0c;实现了lwip、littlefs、hdf等子系统及组件的适配…

循序表实战——基于循序表的通讯录

前言&#xff1a;本篇文章主要是利用顺序表作为底层&#xff0c; 实现一个通讯录。偏向于应用&#xff0c; 对于已经学习过c的友友们可能没有难度了已经。没有学习过c的友友&#xff0c; 如果顺序表不会写&#xff0c; 或者说没有自己实现过&#xff0c; 请移步学习顺序表相关内…

xgo: golang基于-toolexec实现猴子补丁

注&#xff1a; 转载请注明出处&#xff0c; 原文链接。 概述 在这篇博客中&#xff0c;我将详细介绍 xgo 的实现细节。 如果你不知道&#xff0c;xgo 项目位于 https://github.com/xhd2015/xgo。 它的作用很简单&#xff0c;就是在每个 Go 函数的开头添加拦截器&#xff0…

python-面向对象编程

面向对象编程 面向对象&#xff0c;python中支持两种编程方式&#xff0c;来写代码&#xff0c;分别是&#xff1a;函数式编程和面向对象 函数式&#xff1a; # 定义函数&#xff0c;在函数中实现功能 def func():print("一个NB的功能")面向对象 calss FOO(object):d…

git提交代码时报错,提不了

问题 今天在换了新电脑&#xff0c;提交代码时报错 ✖ eslint --fix found some errors. Please fix them and try committing again. ✖ 21 problems (20 errors, 1 warning) husky > pre-commit hook failed (add --no-verify to bypass) 解决 通过 --no-verify 解决&…

JavaScript - 请你说一说对随机数的理解

难度级别:初级及以上 提问概率:40% 在前端开发中,随机数的应用场景非常多,而且也是一个常见的考点。例如网页登录的验证码,看似只有4个随机数字加字母的组合,其实这也是随机数的范畴;例如在抽奖算法中,可以用随机数确定用户中奖的概率…

解决电脑无故自动关机或重启的15种方法,总有一种适合你

序言 你的Windows PC是否在没有警告的情况下关闭或重新启动?这背后有几个潜在的原因。例如,它可能是软件/硬件冲突、过热或硬盘驱动器错误。本故障排除指南将概述在Windows 10/11中修复自动关闭和重新启动的多个解决方案。 如果你的计算机经常关闭,则必须在安全模式下启动…