走进算法大门---双指针问题(一)

一.双指针算法介绍

概念:双指针是指在遍历数据结构(如数组、链表等)时使用两个指针,通过特定的移动规则来解决问题。这两个指针可以同向移动,也可以相向移动。

  • 同向双指针:常用于解决需要两个位置信息的问题。例如,在一个有序数组中查找两个数的和等于目标值的情况。一个指针从数组头部开始,另一个指针从当前指针的后面开始,通过不断调整指针位置来找到符合条件的数对。
  • 相向双指针:典型应用是在排序数组中查找满足某种条件的子数组。比如,在一个递增的数组中,一个指针从数组开头,一个指针从数组末尾,根据两个指针所指元素的和、差等关系,向中间移动指针,直到满足特定条件。
  • 优势:双指针算法可以降低时间复杂度,将原本需要嵌套循环的问题简化为单循环或更高效的遍历方式。例如,在某些情况下,可以将时间复杂度从n^2 降低到n 。

二.移动0

题目链接
在这里插入图片描述

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1;cur<nums.length;cur++){if(nums[cur]!=0){dest++;int tmp = nums[cur];nums[cur]=nums[dest];nums[dest] =tmp;}}}
}

在这里插入图片描述

解题思路:主要把数组分为3个区间,已经处理过的非0区间,0元素区间和未处理的区间。

把数组分为3部分:

  • [0,dest] :处理过的非0元素
  • [dest+1,cur-1] 处理过的0元素
  • [cur,arry,length-1] 未被处理的元素

在这里插入图片描述

初始化时让cur 指向0元素位置,dest指向-1。刚开始所有元素都未处理,按照划分区间,未被处理的元素区间为【0,dest】,所以dest不能等于0,等于0说明第一个元素已经被处理过,边界不好区分,因此让dest=-1。
在这里插入图片描述

当cur的值等于0时,cur++;cur的值不等于0,让dest先走一步接着dest和cur 对应元素的值互相交换,每次都能保证数组的3个范围的划分。
在这里插入图片描述

在代码执行中,非零元素会依次覆盖零元素的位置,最终达到将所有零移动到数组末尾的目的。此方法的时间复杂度为 O(n),空间复杂度为 O(1),即为原地操作,不占用额外空间。如果暴力求解时间复杂度n方,双指针确实比暴力求解时间复杂度低。

三.快乐数

快乐数
在这里插入图片描述

class Solution {public int Num(int n) {int sum = 0;while (n!= 0) {int t = n % 10;sum += t * t;n /= 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = Num(n);while (fast!= slow) {slow = Num(slow);fast = Num(Num(fast));}return slow == 1;}
}

解法:前面学习链表的时候我们学过判断链表是否带环,让快指针一次走2步,慢指针一次走一步,如果存在环它们总能相遇。

以19为例是该树快乐数,通过对19的运算结果确实是1,说明是快乐数。
在这里插入图片描述

以2为例判断不是快乐数。4和20形成了一个环,说明不是快乐数。
在这里插入图片描述
把这个环想象成链表带环,让快指针在环里面一次走2步,慢指针一次走一步总会在环里面的某个位置相遇,相遇后跳出循环判断相遇点的值是否为1,如果是1说明是快乐数,不是1说明不是。

关于是否会陷入死循环
在这个算法中,实际上是利用了快慢指针的思想。对于一个正整数,如果它不是快乐数,那么在不断计算各位数字平方和的过程中,最终会陷入一个循环。
由于数字的范围是有限的(对于给定的正整数,经过有限次的数字平方和计算后,得到的结果一定在一个有限的范围内)。
假设存在一个非快乐数,在计算过程中会进入一个循环,那么快慢指针一定会在这个循环中相遇。因为快指针每次移动两步,慢指针每次移动一步,在一个有限的循环中,快指针必然会追上慢指针。
如果这个数是快乐数,那么最终会得到1,此时快慢指针也会相等(因为最终都会到达1这个结果)。

四.盛最多容器的水

盛最多容器的水
在这里插入图片描述
在这里插入图片描述

class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int v = 0;while (left < right) {int min = Math.min(height[left], height[right]);v = Math.max(v, min*(right - left));if (height[right] > height[left]) {left++;} else {right--;}}return v;}
}

在这里插入图片描述

解法:如果本题暴力求解去枚举算最大值比较大小,那么时间复杂度太高。

简单方法是去掉一些没必要的值。举个例子:算8和5的容积。该容器高度是5,宽度为(right-left)=6。因此v=5*6=30。

在这里插入图片描述
接着枚举该数组v的最大值那么宽度必然是减少的,因为求下一个容积会让left++,或者right–,那么(right-left)的值必然减少。因此宽度会减少。
在这里插入图片描述

对于v=宽度*高度,宽度减少要想体积增大必须高度增加。8和5的最小值是5,要想高度增加,那么right的值必然要大于5,所以可以看做舍弃5,让right减减。计算容器8和9容积
在这里插入图片描述

v=5*8=40,v上次的值是30,40大于30,所以v的值更新为40。求下一个容积也是同样的做法,要想v在宽度减少的情况下增大,那么高度的最小值一定要增大,也就是比较left和right的对应值的最小值,把这个最小值舍弃掉,在去求v。每次比较和上次v值的大小看是否更新v的值。
在这里插入图片描述

这道题考察了如何通过合理的指针移动来减少不必要的计算,双指针法的精髓在于每次有目的地舍弃一些不可能产生最大值的组合,从而将时间复杂度降至线性。在实际解题时,双指针法是一种非常高效的解法,特别适用于涉及到对区间或边界的遍历优化问题。

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

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

相关文章

智能问答系统流程详解:多轮对话与模型训练的技术要点及案例

随着智能客服系统的广泛应用&#xff0c;如何在提升用户体验的同时保障系统的准确性与效率&#xff0c;成为了智能问答系统设计中的重要问题。本文将介绍一种智能问答系统的流程设计&#xff0c;涵盖从识别用户意图、匹配知识库、多轮对话到模型训练的全流程&#xff0c;并通过…

03集合基础

目录 1.集合 Collection Map 常用集合 List 接口及其实现 Set 接口及其实现 Map 接口及其实现 Queue 接口及其实现 Deque 接口及其实现 Stack类 并发集合类 工具类 2.ArrayList 3.LinkedList 单向链表的实现 1. 节点类&#xff08;Node&#xff09; 2. 链表类&a…

pyspark基础准备

1.前言介绍 学习目标&#xff1a;了解什么是Speak、PySpark&#xff0c;了解为什么学习PySpark&#xff0c;了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码&#xff0c;既可以在电脑上简单运行&#xff0c;进行数据分析处理&#xff0c;又可以把代码无缝…

gitlab项目如何修改主分支main为master,以及可能遇到的问题

如果你希望将 Git 仓库的主分支名称从 main 修改为 master&#xff1a; 1. 本地修改分支名称 首先&#xff0c;切换到 main 分支&#xff1a; git checkout main将 main 分支重命名为 master&#xff1a; git branch -m main master2. 更新远程仓库 将本地更改推送到远程仓库…

albert模型实现微信公众号虚假新闻分类

项目源码获取方式见文章末尾&#xff01; 600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【基于CNN-RNN的影像报告生成】 2.【卫星图像道路检测DeepLabV3Plus模型】 3.【GAN模型实现二次元头像生成】 4.【CNN模型实现…

最新三维视觉下的扩散模型综述——Diffusion Models in 3D Vision: A Survey

目录 摘要 一、引言 二、扩散模型简介 A.扩散模型的介绍 B.扩散模型的数学基础 C.扩散模型的变体 D.三维视觉中的生成过程 三、三维视觉基础 A.三维表示 B.三维视觉中的深度学习方法 C.3D视觉中的挑战 四、三维扩散生成任务 A.无条件生成 B.图像到三维 C.文本到…

《今日制造与升级》是什么级别的期刊?是正规期刊吗?能评职称吗?

​问题解答 问&#xff1a;《今日制造与升级》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的正规学术期刊。 问&#xff1a;《今日制造与升级》级别&#xff1f; 答&#xff1a;国家级。主管单位&#xff1a;中国机械工业联合会 …

基于开源 AI 智能名片 S2B2C 商城小程序的视频号交易小程序优化研究

摘要&#xff1a;本文探讨了完善适配视频号交易小程序的重要意义&#xff0c;重点阐述了开源 AI 智能名片 S2B2C 商城小程序在这一过程中的应用。通过分析其与直播间和社群的无缝衔接特点&#xff0c;以及满足新流量结构下基础设施需求的能力&#xff0c;为门店在视频号直播交易…

A021基于Spring Boot的自习室管理和预约系统设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

while()与string::length()的使用错误

在写KMP算法时&#xff0c;把i<S.length()&&j<T.length()直接放到了while()中&#xff0c;当j为负数时&#xff0c;发现循环进不去&#xff1a; void KMP(string S,string T){int i0,j0;while(i<S.length()&&j<T.length()){cout<<"i&q…

Java I/O流面试之道

先赞后看&#xff0c;Java进阶一大半 南哥在国外 stackoverflow 看到13年前的这么一个问题&#xff1a;如何使用 Java 逐行读取大型文本文件。大家有什么思路吗&#xff1f;评论区一起讨论讨论。 I need to read a large text file of around 5-6 GB line by line using Java. …

精选 Top10 开源调度工具,解锁高效工作负裁自动化

在大数据和现代 IT 环境中&#xff0c;任务调度与工作负载自动化&#xff08;WLA&#xff09;工具是优化资源利用、提升生产效率的核心驱动力。随着企业对数据分析、实时处理和多地域任务调度需求的增加&#xff0c;这些工具成为关键技术。 本文将介绍当前技术发展背景下的Top …

微软域名邮箱:如何设置管理烽火域名邮箱?

微软域名邮箱的设置技巧&#xff1f;免费域名邮箱注册设置教程&#xff1f; 微软域名邮箱为企业提供了一个强大且灵活的解决方案&#xff0c;帮助企业轻松管理其域名邮箱。烽火将详细介绍如何设置和管理微软域名邮箱&#xff0c;确保您的团队能够高效地使用这一工具。 微软域…

VS ssh连接linux无法运行的问题 GDB 的解决方法

Unable to start debugging. Program path ... is missing or invalid. GDB failed with message:/home/zsy/projects/是一个目录 把这个将解决方案和项目放在同一目录中勾选

Python酷库之旅-第三方库Pandas(203)

目录 一、用法精讲 946、pandas.IntervalIndex类 946-1、语法 946-2、参数 946-3、功能 946-4、返回值 946-5、说明 946-6、用法 946-6-1、数据准备 946-6-2、代码示例 946-6-3、结果输出 947、pandas.IntervalIndex.closed属性 947-1、语法 947-2、参数 947-3、…

Trimble X12三维激光扫描仪正在改变游戏规则【上海沪敖3D】

Trimble X12 三维激光扫描仪凭借清晰、纯净的点云数据和亚毫米级的精度正在改变游戏规则。今天的案例我们将与您分享&#xff0c;X12是如何帮助专业测量咨询公司OR3D完成的一个模拟受损平转桥运动的项目。 由于习惯于以微米为单位工作&#xff0c;专业测量机构OR3D是一家要求…

【大数据学习 | kafka】简述kafka的消费者consumer

1. 消费者的结构 能够在kafka中拉取数据进行消费的组件或者程序都叫做消费者。 这里面要涉及到一个动作叫做拉取。 首先我们要知道kafka这个消息队列主要的功能就是起到缓冲的作用&#xff0c;比如flume采集数据然后交给spark或者flink进行计算分析&#xff0c;但是flume采用的…

uniapp发布到微信小程序,提示接口未配置在app.json文件中

使用uniapp打包上传微信小程序发布&#xff0c;在提交审核时提示 “接口未配置在app.json文件中” 如下图所示 解决方法&#xff1a;在manifest.json文件中打开源码视图&#xff0c;添加 requiredPrivateInfos 字段键入所需要的接口&#xff08;数组&#xff09;

重新下载Window11系统中的mfc100.dll文件

环境 Xshell6Xftp6Window11 前言 最近下载了一款绿色版本的Xshell远程客户端软件&#xff0c;用来登录Linux服务器&#xff0c;在Window11使用&#xff0c;点击时候提示很多dll文件缺失&#xff0c;所以比较纠结&#xff0c;因为是绿色版本软件&#xff0c;所以不能重装&…

js基础篇笔记 (万字速通)

此笔记来自于黑马程序员,仅供笔者复习 JavaScript 基础 - 第1天 了解变量、数据类型、运算符等基础概念&#xff0c;能够实现数据类型的转换&#xff0c;结合四则运算体会如何编程。 体会现实世界中的事物与计算机的关系理解什么是数据并知道数据的分类理解变量存储数据的“容…