【优选算法 — 双指针】双指针小专题

   

  和为 s 的两个数  

和为s的两个数


  题目描述  

  解法一:暴力枚举  

暴力枚举,先固定一个数,然后让这个数和另一个数匹配相加,

如果当前的数 + 所有剩余的数 = target,则返回这两个数,否则固定下一个数;

所以暴力枚举只需要两层 for() 即可,但是这种解法实在太慢了,题目中给的是一个有序的数组,我们要利用数组有序的特性


  解法二:利用单调性  

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

先固定数组的首尾元素,固定好后,让两个数相加一下,看看能否使用单调性进行优化。

先不管 target 等于多少,这两个数之和 sum 无非就是三种情况

注意:sum 指的是 left 和 right 指向的数组元素之和

  1. sum < target
  2. sum > target
  3. sum = target

对比暴力枚举,利用单调性,使用双指针的算法的时间复杂度得到大大的优化;

暴力枚举需要拿固定的数,和所有剩余的数相加,但是解法二只需要让固定的数相加一次即可,就能判断是否舍弃当前固定的数了 

  时间复杂度  

解法一 O(N^2),解法二O(N)


  编写代码  

报错原因:

没有返回值,我们已经写了 return 语句,那么为什么编译器还会认为我们没有返回值呢?

我们必须保证所以的路径都要有返回值,而在上述代码,编译器不会管 while 语句中的 return 是否被执行,而是会考虑 只有 return 前的else 成立才会有返回值;

对于其他路径,如 else 不成立时,那么这个函数就没有返回值了,所以为了照顾编译器,强行返回一个值,就是告诉编译器一定会有返回值的:


  快乐数   

快乐数


题目描述

第一种情况

 

return true


第二种情况


这个数在定义的过程中,会进入到一个没有 1 的环中,并且无限在环中循环,始终变不到 1

return false


  题目解析  


可以回忆OJ题:判断链表是否有环 ;

对于一个数,经过快乐数的定义变换后,是一定会成环的,并且题目也给出了提示;

如果题目没给提示,我们就需要验证是否会出现不成环的情况;其实是一定会成环的;

 

证明快乐数一定成环


 鸽巢原理(抽屉原理):n个巢,n+1 只鸽子,至少有一个巢,里面的鸽子数大于1


这道题的数据范围


最终,2^31 -1 的结果是一个10位整数,所以:


2^31 -1 < 999999999


快乐数转换(2^31 -1 ) < 快乐数转换(999999999)=81*10=810


所以快乐数的值的区间一定是[ 0,810 ),我们的巢穴出来了,我们随便找一个数,让他经过快乐数转换 811 次,转换的数一定是在 [ 0,810 )区间内的,在 转换 811 次之内,一定会出现重复的数,也就是一定会成环的。

所以对于这题,我们只需判断环中是否为1 ,来决定最终返回的boolean值


  解法:快慢双指针   

这里的指针并不是真正的指针,只是一种指针思想,在这题中,我们把变化过程中的数,抽象成指针;


  • 1. 定义快慢指针;
  • 2. 慢指针每次向后移动一步,快指针每次向后移动两步;
  • 3. 对于判断链表是否有环,我们看的是快慢双指针最终能否相遇;
  • 4. 对于快乐数,是一定会成环的,快慢双指针一定会相遇,我们只需要判断相遇点的值是否为1 ;

  编写代码  


因为每一次快乐数转换,都需要 求和 这个数的 每一位数 的平方,因此我们可以把这个过程封装成一个方法 bitSum() ,返回 n 这个数每一位上的平方和


  盛最多水的容器   

 盛最多水的容器


  题目解析   

 

 right - left = 两根柱子之间的格子个数 = 宽度,返回 S 即可


  解法一:暴力枚举  

通过两层 for 循环,先让 left 固定左边的柱子, right 依次枚举右边的柱子;一轮枚举后,让 left 固定第二根柱子;但是这种做法是超时的;


  解法二:对撞指针  

算法原理


首先让 left 和 right 指向 6 和 4 ; 

此时如果让 right 固定的是4,让left 向内枚举那么 wide 一直减小

在让 right 固定4,left 向内枚举时,会碰到三种情况:

  1. height[left] < height [right];
  2. height[left] = height [right];
  3. height[left] > height [right];

对于第一种情况,此时根据木桶原理,容器的高度是减小的,所以 S 减小;

第二种情况和第三种情况,根据木桶原理,容器的高度都是不变的,但是 wide 一直在减小;


所以无论是三种情况中的哪一种,向内枚举的 V 一直都是减小的;

所以拿 min( height[left] , height [right]) * wide 得到的 S,

如果固定其中任意一个指针,向内枚举一次,发现 S 减小,那就可以大胆的 舍弃当前 left 和 right 两个指针的较小值,固定较大值。

根据上面的思想,我们可以先固定 left 指向的1,让 right 向内枚举一次,得到的 S 是在减小的,因此可以大胆的舍弃 1,让left++;

 此时,我们可以尝试着把 right 指向的 7干掉,让 right--,因为如果固定 7,那拿left 向内枚举,通过木桶原理,得到的 S 一直都是在减小的;

 如果当前 left 和 right 是相同的,那么舍弃谁都可以,因为根据木桶原理,向内枚举体积都是在减小的;


  总结   


  • S 是由宽度和木桶的短板决定的,在向内枚举时,优先向内移动两个指针中,指向较小值的指针;
  • 每次枚举都求出对应的 S ,直到 left 和 right 对撞,返回这几次枚举中,S 的最大值

  时间复杂度  

解法一 O(N^2);解法二 O(N)


  编写代码  



  三数之和   

三数之和(这个题一定一定一定要画图,空想会错很多,自己把这个题的代码写出来)


题目描述


我们根据题意,可以选出三组和为0的三元组,但是输出结果只要两组数:

所以是因为,第一组和第二组,选出的三元组,虽然顺序不一样,但是三元组的元素一样;

所以不可以包含重复三元组的意思,就是三元组的顺序不重要,只要的是两组三元组的元素不能完全一样。

这道题的难点是去重操作,我们先来想解法 

解法一:先排序 + 暴力枚举 + 利用 set 去重

定义三层 for 循环,把能三个数之和等于0的,所有符合条件的三元组求出来,再对求出的组合去重;

去重操作,可以先把三元组从小到大排序,排好序之后再一 一 比对;

但是,如果在一个 length 非常大的数组中,找到了多对重复的,符合条件的三元组,那么一个一个找会非常麻烦。所以我们可以先把整个数组进行排序,然后再规定从左往右的顺序,进行所有三元组的枚举:

如果我们再一次找符合条件的三元组,就会发现找到的三元组已经是排好序的了;

比起刚刚的像刚刚没对数组排序,而是先找三元组,再对三元组排序 ;先对整个数组排序,再枚举所有三元组,更利于我们的查重操作

我们再利用 Java 中的 Set 集合,把所有得到的三元组,放入 HashSet 中,就会对数组去重,并且这是建立在排序整个数组,得到所有符合题意的三元组,才可以完美利用上 Set 的特性。

把所有三元组放入 Set 中,再把 Set 的结果拿出来作为返回值。

暴力枚举的时间复杂度:O( N^3 ),三层 for循环,去重操作针对的是有限个数的三元组,所以去重操作的时间复杂度可以忽略不记。


解法二:排序 + 双指针

用双指针,可以让时间复杂度降维,是非常优秀的算法,来看下面例子:

该数组已经排好序,利用暴力枚举时,我们是先固定一个数,然后在剩余区间中找到两个数组成符合题意的三元组

 固定一个数,在剩余的数字,并且是有序的数字中,利用双指针快速找到符合题意的两个数。

 处理细节问题:

去重;并且在上图的 left 和 right 区间中,有多对组合能相加凑出4,我们要把他们全部都找到;

  1. 不漏
  2. 去重 
  3. 避免指针越界(在去重过程中会出现越界)

这三步操作是本题最重要的

否则

此时 left + right =4,此时 i,left,right拼接成第一对符合题意的三元组;但是我们还要继续这个过程,直到固定当前 i指针 的情况下,left 和 right 相遇。

所以不漏的操作,需要注意:

找到一种结果,不要让 left 和 right 停下来,继续缩小两个指针的区间 。

当然,如果在找到如上图的组合后,后面重复的 0 和 4 就不需要继续枚举了,所以我们去重,是要在找到一种结果之后,left  和  right  要跳过重复元素:

此时 i指针固定的第一个数的所有情况都已经枚举完毕,i++,此时我们发现,i指针 由指向了 -4:

又会出现重复的计算,因此我们去重要注意两个地方

  • left 和 right 的去重
  • 当使用完一次双指针算法之后,i 指针 也需要跳过重复元素

紧扣这两个情况,就能处理好去重操作

去重完后,我们还要处理双指针越界的情况:

通过刚刚的去重思想,来遍历上面的组合,会让双指针越界,因此我们在移动 i,left,right指针,来避免重复元素的时候,一定要处理指针越界的问题,我们结合代码,来讲解处理越界的情况。

还有一个小细节:


 从煮啵写的代码来看,可以发现数据结构的基础很差~~~~

完整代码 

修改: 下面i++,for循环就不要 i++了,不然会跳过要固定的下一个a

 时间复杂度:O(N^2)

空间复杂度:用到了Arrays.sort(),快排,是递归产生的空间消耗,O(logN)


  四数之和 

四数之和


解法一:排序 + 暴力枚举 + 利用 set 去重

解法二:排序 + 双指针

  1. 依次固定一个数 a
  2. 在 a 后面的区间内,找到“三数之和”思想 得到的三个数,使这三个数的和等于 target - a 即可
  3. 依次固定一个数 b
  4. 在 b 后面的区间内,利用“双指针”找到两个数,舍得这两个数的和等于“target - a - b”即可

 

整体思路,两层 for 循环中套一个双指针算法,这只是整体思路,还需处理细节问题:

处理细节问题:

(1)去重:

  • left 和 right 要跳过重复的数
  • 利用完双指针,b要跳过重复元素
  • 利用“三数之和”后,a要跳过重复元素

(2)不漏(双指针在找到一组符合条件的数时,继续缩小区间)

编写代码:

解析:在计算的时候,会有溢出的风险,也就是计算结果和预期结果不符合:

 

时间复杂度:O(N^3)

空间复杂度:O(logN),和三数之和的原因相同


 

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

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

相关文章

轻松理解操作系统 - 轻松了解 inode 是如何管理文件的

Linux 由于其开源、比较稳定等特点统治了服务端领域。也因此&#xff0c;学习Linux 系统相关知识在后端开发等岗位中变得越来越重要&#xff0c;甚至可以说是必不可少的。 因为它的广泛应用&#xff0c;所以在程序员的日常工作和面试中&#xff0c;它都是经常出现的。它的开源特…

Vue(JavaScript)读取csv表格并求某一列之和(大浮点数处理: decimal.js)

文章目录 想要读这个表格&#xff0c;并且求第二列所有价格的和方法一&#xff1a;通过添加文件输入元素上传csv完整&#xff08;正确&#xff09;代码之前的错误部分因为价格是小数&#xff0c;所以下面的代码出错。如果把parseFloat改成parseInt&#xff0c;那么求和没有意义…

微信小程序-事件总线

一.事件总线的概念和作用 事件总线是对发布-订阅模式的一种实现&#xff0c;是一种集中式事件处理机制&#xff0c;允许不同组件之间进行彼此通信&#xff0c;常用于两个非父子组件和兄弟组件之间的通讯。 在日常开发过程中&#xff0c;我们可以使用第三方的发布订阅 JS 包来实…

成都郝蓉宜恺文化传媒:引领大数据应用新篇章

在信息化浪潮汹涌的今天&#xff0c;大数据被誉为新时代的“石油”&#xff0c;正在以前所未有的速度改变着我们的生活和工作方式。成都郝蓉宜恺文化传媒&#xff0c;作为大数据领域的领军企业&#xff0c;始终站在创新的前沿&#xff0c;引领着大数据应用的新篇章。 作为大数…

qt QDropEvent详解

1、概述 QDropEvent是Qt框架中用于处理拖放释放事件的一个类。它允许开发者在用户界面中更好地管理和处理拖放操作&#xff0c;从而实现交互式和响应式的应用程序。QDropEvent类提供了处理拖放释放事件所需的方法和信号&#xff0c;使得开发者能够轻松地实现拖放功能&#xff…

Kotlin的内置函数

Kotlin 提供了丰富的内置函数&#xff0c;它们极大简化了日常开发工作。常见内置函数包括 标准库函数&#xff08;let、apply、run 等&#xff09;&#xff0c;用于提高代码的简洁性和可读性。下面我们详细介绍这些函数的功能、用法以及它们之间的区别。 1. let 函数 let 通常…

Pod安装软件将CDN改为国内的镜像

1、碰到错误 在pod install的时候碰到以下的下载错误&#xff1a; 文字错误如下&#xff1a; CDN: trunk URL couldnt be downloaded: https://cdn.jsdelivr.net/cocoa/Specs/5/b/d/OpenCV/2.4.11/OpenCV.podspec.json Response: Timeout was reached CDN: trunk URL couldn…

Rockchip SoC AI 与视觉处理器路线图:赋能未来的 AI 驱动设备

随着人工智能&#xff08;AI&#xff09;和计算机视觉技术不断推动各行各业的创新&#xff0c;Rockchip 已成为提供强大系统级芯片&#xff08;SoC&#xff09;解决方案的领先厂商。该公司已开发出多款集成 AI 功能并支持先进多媒体与视觉技术的 SoC&#xff0c;非常适合用于 A…

尚庭公寓-小程序接口

7. 项目开发 7.4 移动端后端开发 7.4.1 项目初始配置 7.4.1.1 SpringBoot配置 1. 创建application.yml文件 在web-app模块的src/main/resources目录下创建application.yml配置文件&#xff0c;内容如下&#xff1a; server:port: 80812. 创建SpringBoot启动类 在web-app…

练习LabVIEW第三十八题

学习目标&#xff1a; 刚学了LabVIEW&#xff0c;在网上找了些题&#xff0c;练习一下LabVIEW&#xff0c;有不对不好不足的地方欢迎指正&#xff01; 第三十八题&#xff1a; 创建一个VI&#xff0c;实现对按钮状态的指示和按钮“按下”持续时间简单计算功能&#xff0c;按…

HTMLCSS:3D 旋转卡片的炫酷动画

效果演示 这段代码是一个HTML和CSS的组合&#xff0c;用于创建一个具有3D效果的动画卡片。 HTML <div class"obj"><div class"objchild"><span class"inn6"><h3 class"text">我是谁&#xff1f;我在那<…

微控制器(MCU)如何运行存储在Flash的程序???

忙&#xff0c;太忙了&#xff01;&#xff01;&#xff01;忙完就好了。MCU运行不也就如此&#xff1f;在微控制器单元&#xff08;MCU&#xff09;中&#xff0c;我们所编写的程序时通常是存储在闪存&#xff08;Flash&#xff09;中。当MCU启动时&#xff0c;它会从闪存中读…

yolov8涨点系列之引入CBAM注意力机制

文章目录 YOLOv8 中添加注意力机制 CBAM 具有多方面的好处特征增强与选择通道注意力方面空间注意力方面 提高模型性能计算效率优化&#xff1a; yolov8增加CBAM具体步骤CBAM代码(1)在__init.pyconv.py文件的__all__内添加‘CBAM’(2)conv.py文件复制粘贴CBAM代码(3)修改task.py…

如何无缝更换WordPress主题:关键步骤详解

更换WordPress主题对于希望刷新网站外观或改善用户体验的站长来说&#xff0c;是一项常见但不容忽视的任务。无论是为了提升性能还是实现新的设计风格&#xff0c;在更换主题时&#xff0c;确保不遗漏任何重要细节至关重要。本文将详细介绍更换WordPress主题的关键步骤&#xf…

推荐一款PowerPoint转Flash工具:iSpring Suite

iSpring Suite是一款PowerPoint转Flash工具&#xff0c;使用iSpring Suite 8可以轻松的将PPT演示文档转换为对Web友好的Flash影片格式。软件界面简洁&#xff0c;使用方便。为什么要转换成flash格式呢?Flash格式的最大特点是体积小巧、易于分发&#xff0c;兼容所有的操作系统…

【案例】故障雪花屏

开发平台&#xff1a;Unity 6.0 开发工具&#xff1a;Shader Graph 参考视频&#xff1a;【U2D Shader Graph】❄️雪❄️花❄️屏❄️   一、效果图 二、Shader Graph 路线图 三、案例分析 核心思路&#xff1a;雪花屏幕效果 &#xff08;混合&#xff09; 原图像 最终图像…

ffplay 实现视频流中音频的延迟

ffplay -rtsp_transport tcp -i rtsp://admin:1234qwer192.168.1.64:554/Streaming/Channels/101 -vn -af "adelay5000|5000"在这个命令中&#xff1a; -vn 参数表示只播放音频。 -af "adelay5000|5000" 参数表示将音频延迟5000毫秒&#xff08;即5秒&…

科技资讯|谷歌Play应用商店有望支持 XR 头显,AR / VR设备有望得到发展

据 Android Authority 报道&#xff0c;谷歌似乎正在为其 Play 商店增加对 XR 头显的支持。该媒体在 Play 商店的代码中发现了相关的线索&#xff0c;包括一个代表头显的小图标以及对“XR 头显”的提及。 谷歌也可能改变了此前拒绝将 Play 商店引入 Meta Quest 头显的决定。今…

Pr 视频效果:超级键

视频效果/键控/超级键 Keying/Ultra Key 超级键 Ultra Key效果是 Premiere Pro 中功能强大的抠像工具&#xff0c;主要用于绿幕/蓝幕抠像。通过选择要抠除的颜色&#xff08;通常是绿幕或蓝幕的颜色&#xff09;&#xff0c;即可以将该颜色的像素设为透明&#xff0c;实现主体与…

Git使用指南

目录 工作机制基本框架:流程图 基本命令分支操作远程仓库本地仓库关联远程仓库 参考 工作机制 基本框架: Workspace&#xff1a;开发者工作区&#xff0c;也就是你当前写代码的目录&#xff0c;它一般保持的是最新仓库代码。Index / Stage&#xff1a;暂存区&#xff0c;最早…