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

【寻找one piece的算法之路】——双指针算法!他与她是否会相遇呢?

💐个人主页:初晴~

📚相关专栏:寻找one piece的刷题之路


什么是双指针算法 

双指针算法是一种常用的编程技巧,尤其在处理数组字符串问题时非常有效。这种方法的核心思想是使用两个指针遍历数据结构,这两个指针通常分别位于数据结构的起始位置或某些特定位置,通过移动这两个指针来达到解决问题的目的。双指针算法可以显著减少时间复杂度,使其从O(n2)O(n2)降低到O(n)O(n),甚至在某些情况下可以达到O(log⁡n)O(logn)。

常⻅的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针
对撞指针:⼀般⽤于顺序结构中,也称左右指针。
  • 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循 环),也就是:
  • left == right (两个指针指向同⼀个位置)
  • left > right (两个指针错开)
快慢指针:⼜称为⻳兔赛跑算法,其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表数组⾮常有⽤。
其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使⽤快慢指针的思想。
快慢指针的实现⽅式有很多种,最常⽤的⼀种就是:
在⼀次循环中,每次让慢的指针向后移动⼀位,⽽快的指针往后移动两位,实现⼀快⼀慢

一、复写零

题目链接

题目描述:

题目分析:

题目的意思就是遍历原数组,每遇到一次0,就将后面所有的数水平向右移动一位,并再插入一个0,最后仍丢弃溢出的数据,仍取原来的数组长度的数据。

分析:

如果「从前向后」进⾏原地复写操作的话,由于 0 的出现会复写两次,导致没有复写的数「被覆
盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候,我们需要找到「最后⼀个复写的数」,因此我们的⼤体流程分两
步:
  1. 先找到最后⼀个复写的数

我们先初始化两个指针 cur = 0 dest = -1

cur < n 的时候,⼀直执⾏下⾯循环:
判断 cur 位置的元素:
如果是 0 的话, dest 往后移动两位;
否则, dest 往后移动⼀位。
判断 dest 时候已经到结束位置,如果结束就终⽌循环;
如果没有结束, cur++ ,继续判断。

注意:

要判断 dest 是否越界到 n 的位置:
如果越界,执⾏下⾯三步:
  1. n - 1 位置的值修改成 0
  2. cur 向移动⼀步;
  1. dest 向前移动两步。

  2.然后从后向前进⾏复写操作

cur 位置开始往前遍历原数组,依次还原出复写后的结果数组:

判断 cur 位置的值:
1. 如果是 0 dest 以及 dest - 1 位置修改成 0 dest -= 2
2. 如果⾮ 0: dest 位置修改成 0 dest -= 1
cur-- ,复写下⼀个位置

代码实现:

class Solution {public void duplicateZeros(int[] arr) {int len=arr.length,cur=0,dest=-1;while(cur<len){if(arr[cur]==0){dest+=2;}else{dest++;}if(dest==len-1)break;if(dest>len-1){arr[len-1]=0;cur--;dest=len-2;break;}cur++;}if(dest==cur)return;while(cur>=0){if(arr[cur]!=0){arr[dest--]=arr[cur--];}else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
}


二、盛⽔最多的容器

题目描述:

题目分析:

我们可以设两个指针 left right 分别指向容器的左右两个端点,此时容器的容积 :
v = (right - left) * min( height[right], height[left])
容器的左边界为 height[left] ,右边界为 height[right]
为了⽅便叙述,我们假设「左边边界」⼩于「右边边界」
如果此时我们固定⼀个边界,改变另⼀个边界,⽔的容积会有如下变化形式:
  • 容器的宽度⼀定变⼩
  • 由于左边界较⼩,决定了⽔的⾼度。如果改变左边界,新的⽔⾯⾼度不确定,但是可能会超过原来左边界的柱⼦⾼度,因此容器的容积可能会增⼤。
  • 如果改变右边界,⽆论右边界移动到哪⾥,新的⽔⾯的⾼度⼀定不会超过左边界,也就是不会超过现在的⽔⾯⾼度,但是由于容器的宽度减⼩,因此容器的容积⼀定会变⼩的
由此可⻅,左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界,继续去判断下⼀个左右边界。
  • 当我们不断重复上述过程,每次都可以舍去⼤量不必要的枚举过程,直到 left right 遇。期间产⽣的所有的容积⾥⾯的最⼤值,就是最终答案。

代码实现:

class Solution {public int maxArea(int[] height) {int l=0,r=height.length-1,max=0,t;while(l<r){if(height[l]<height[r]){t=height[l]*(r-l);l++;}else{t=height[r]*(r-l);r--;}if(max<t)max=t;}return max;}
}


三、有效三⻆形的个数

题目链接

题目描述:

题目分析:

首先我们得知道,三条边能构成三角形的充要条件是:任意两边之和大于第三边。

不过事实上,我们只要保证两条短边和大于最长边即可。

因此,我们可以先将数组从小到大进行排序,接着用一个指针 j 固定一个「最⻓边」,然后在⽐这条边⼩的有序数组中找出⼀个⼆元组,使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的,我们可以利⽤「对撞指针」来优化

设最⻓边枚举到 j 位置,区间 [left, right] 是 j 位置左边的区间(也就是⽐它⼩的区间):

  • 如果 nums[left] + nums[right] > nums[i]

说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[j] ⼤的⼆元组

则满⾜条件的有 right - left

此时 right 位置的元素的所有情况相当于全部考虑完毕, right-- ,进⼊下⼀轮判断

  •  如果 nums[left] + nums[right] <= nums[i]

说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件的⼆元组

left 位置的元素可以舍去, left++ 进⼊下轮循环

代码实现:

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int sum=0;for(int j=nums.length-1;j>=2;j--){int l=0,r=j-1;while(l<r){if(nums[l]+nums[r]>nums[j]){sum=sum+r-l;r--;}else{l++;}}}return sum;}
}


 四、三数之和

题目链接

题目描述:

题目分析:

这题其实与上一题十分相似,都是要找一个满足一定条件的三元组,因此同样,我们可以采用先排序,接着用一个指针 j 固定一个数 a,接着在之后的区间内,利用双指针算法找到两数之和等于-a即可

需要注意的是,题目要求进行「去重」操作:

  1. 找到⼀个结果之后, left right 指针要「跳过重复」的元素;
  2. 当使⽤完⼀次双指针算法之后,固定的 a 也要「跳过重复」的元素

代码实现:

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();int n=nums.length;for(int j=0;j<n;){if(nums[j]>0)break;int l=j+1,r=n-1;int target=-nums[j];while(l<r){int sum=nums[l]+nums[r];if(sum==target){ans.add(new ArrayList<Integer>(Arrays.asList(nums[l],nums[r],                                         nums[j])));if(nums[r]==nums[l])break;l++;r--;while(l<r&&nums[r+1]==nums[r])r--;while(l<r&&nums[l-1]==nums[l])l++;}else if(sum>target){r--;}else{l++;    }  }j++;while(j<n&&nums[j]==nums[j-1])j++;}return ans;}
}


五、四数之和

题目链接

题目描述:

题目描述:

这题的思想其实也与三数之和类似,我们只需要先排序,再用一个指针 i 固定一个数 a在这个数 a 的后⾯区间上,利⽤「三数之和」找到三个数,使这三个数的和等于 target - a 即可

代码实现:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {int n=nums.length;long t,q;Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<List<Integer>>();for(int i=0;i<n;){t=target;t-=nums[i];//if(t<0)return ans;for(int j=i+1;j<n;){q=t;q-=nums[j];int l=j+1,r=n-1;while(l<r){int sum=nums[l]+nums[r];if(sum==q){List<Integer> list=new ArrayList<Integer>();list.add(nums[i]);list.add(nums[j]);list.add(nums[l]);list.add(nums[r]);ans.add(list);l++;r--;while(l<r&&nums[l]==nums[l-1])l++;while(l<r&&nums[r]==nums[r+1])r--;}else if(sum>q)r--;else l++;}j++;while(j<n&&nums[j]==nums[j-1])j++;}i++;while(i<n&&nums[i]==nums[i-1])i++;}return ans;}
}


 总结

双指针技巧的关键点

  1. 初始化:通常一个指针指向序列的开始位置,另一个指针指向序列的结束位置或某个特定位置。
  2. 移动规则:根据问题的具体情况定义指针的移动规则,如当条件不满足时向前或向后移动。
  3. 更新状态:在每次移动指针之后更新当前的状态,如累加、记录最大值等。
  4. 退出条件:当两个指针相遇或某个指针超出界限时结束循环。

双指针算法是一种简单而有效的算法技巧,通过维护两个指针的状态来简化问题的复杂度。合理地运用双指针法,可以帮助我们在处理数组和字符串问题时更加高效地达成目标。


那么本篇文章就到此为止了,如果觉得这篇文章对你有帮助的话,可以点一下关注和点赞来支持作者哦。如果有什么讲的不对的地方欢迎在评论区指出,希望能够和你们一起进步✊

相关文章:

【寻找one piece的算法之路】——双指针算法!他与她是否会相遇呢?

&#x1f490;个人主页&#xff1a;初晴~ &#x1f4da;相关专栏&#xff1a;寻找one piece的刷题之路 什么是双指针算法 双指针算法是一种常用的编程技巧&#xff0c;尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构&#xff0c;这两…...

UFS 3.1架构简介

整个UFS协议栈可以分为三层:应用层(UFS Application Layer(UAP)),传输层(UFS Transport Layer(UTP)),链路层(UIC InterConnect Layer(UIC))。应用层发出SCSI命令(UFS没有自己的命令使用的是简化的SCSI命令),在传输层将SCSI分装为UPIU,再经过链路层将命令发送给Devices。下…...

注册安全分析报告:科研诚信查询平台无验证方式导致安全隐患

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…...

04.useTitle

在 React 应用中,动态更新页面标题是提升用户体验的一个重要方面。它可以让用户更清楚地知道当前页面的内容或状态,特别是在单页应用(SPA)中。useTitle 钩子提供了一种简单而有效的方式来管理文档标题。以下是如何实现和使用这个自定义钩子: const useTitle = title =>…...

ROS2中的srv、action、发布订阅三种方式

ROS2中的srv、action、发布订阅三种方式 以下是ROS2中srv、action、发布订阅三种方式的差异和使用场景的表格形式呈现&#xff1a; 特性/方式srv&#xff08;服务&#xff09;action&#xff08;动作&#xff09;发布订阅&#xff08;Publish-Subscribe&#xff09;通信模式请…...

HarmonyOS/OpenHarmony 自定义弹窗页面级层级控制解决方案

关键词&#xff1a;CuntomDialog自定义弹窗、SubWindow子窗口、页面级、弹窗层级控制、鸿蒙、弹窗展示层级异常 问题存在API版本&#xff1a;API10 - API12&#xff08;该问题已反馈&#xff0c;期望后续官方能增加页面级控制能力&#xff09; 在正常的鸿蒙app开发过程中&…...

C/C++进阶(一)--内存管理

更多精彩内容..... &#x1f389;❤️播主の主页✨&#x1f618; Stark、-CSDN博客 本文所在专栏&#xff1a; 学习专栏C语言_Stark、的博客-CSDN博客 其它专栏&#xff1a; 数据结构与算法_Stark、的博客-CSDN博客 ​​​​​​项目实战C系列_Stark、的博客-CSDN博客 座右铭&a…...

docker-compose 快速部署clickhouse集群

在本教程中&#xff0c;我们将学习如何使用 Docker Compose 部署一个带有三节点的 ClickHouse 集群&#xff0c;并使用 ZooKeeper 作为分布式协调服务。 前提条件 注意事项&#xff1a; 镜像版本号注意保持一致 [zookeeper:3.7, clickhouse/clickhouse-server:22.5.4]config…...

闯关训练三:Git 基础知识

任务1: 破冰活动&#xff1a;自我介绍 点击Fork目标项目&#xff0c;创建一个新的Fork 获取仓库链接 在连接好开发机的vscode终端中逐行执行以下代码&#xff1a; git clone https://github.com/KelvinIII/Tutorial.git # 修改为自己frok的仓库 cd Tutorial/ git branch -a g…...

Java--IO基本流

IO流 概述 生活中&#xff0c;你肯定经历过这样的场景。当你编辑一个文本文件&#xff0c;忘记了ctrls &#xff0c;可能文件就白白编辑了。当你电脑上插入一个U盘&#xff0c;可以把一个视频&#xff0c;拷贝到你的电脑硬盘里。那么数据都是在哪些设备上的呢&#xff1f;键盘…...

结合大语言模型的机械臂抓取操作简单介绍

一、大语言模型与机械臂抓取的基本操作 1. 大语言模型简介 大语言模型是基于深度学习技术构建的自然语言处理模型&#xff0c;能够生成、理解和处理文本信息。这些模型通过训练大量的文本数据&#xff0c;学习语法、上下文和常识&#xff0c;能够执行多种任务&#xff0c;如文…...

Vivado - BD(差分时钟、简单分频、RESET、KEY)

目录 1. 简介 1.1 要点 1.2 buffer 介绍 2. vivado 工程 2.1 Block Design 2.2 IBUFDS 2.3 BUFGCE_DIV 2.4 Processor System Reset 2.5 key_mod 2.6 led_drv 3. 编译与调试 3.1 XDC 3.2 Debug 4. 总结 1. 简介 1.1 要点 了解 Utility Buffer v2.2 中的 Buffer…...

7--苍穹外卖-SpringBoot项目中套餐管理 详解(一)

前言 目录 新增套餐 需求分析和设计 代码开发 根据分类id查询菜品 Controller层 Service层 ServiceImpl层 Mapper层 DishMapper.xml 新增套餐 实体类 mapper层 Service层 ServiceImpl层 Mapper层 SetmealMapper.xml setmealDishMapper.xml 套餐分页查询 需求分…...

【尚硅谷】RocketMQ 消息队列学习笔记

RocketMQ 和 Kafka 消息队列概念比较&#xff1f; 好的&#xff01;RocketMQ 和 Kafka 都是分布式消息队列系统&#xff0c;它们的核心概念有很多相似之处&#xff0c;但在具体实现和命名上有所不同。下面我通过一个表格来对比 RocketMQ 和 Kafka 中的五个概念&#xff1a;消息…...

C题(三)芝麻开门 --- strcmp函数应用

场景一&#xff1a;“芝麻开门 ”是通往C语言的大门的暗号&#xff0c;现在你需要说对暗号&#xff0c;大门才会打开。 【分解目标1】字符串的输入 char arr[20] { 0 }; //字符的集合---字符串&#xff08;数组表示&#xff09;//20为预定的数组的大小scanf("%s", a…...

C++函数模板、选择排序实现(从大到小)

template <class T> void mysw (T &a , T &b) {T temp b;b a;a temp; }template <class T> void muSort( T &arr ,int len) {//该实现为选择排序(高到低)for (int i 0; i < len; i) {int max i ; //首先默认本次循环首位元素为最大for (int j …...

EasyExcel使用介绍

EasyExcel使用 1、EasyExcel介绍 1.1 官网介绍 传统操作Excel大多都是利用Apach POI进行操作的&#xff0c;但是POI框架并不完善&#xff0c;使用过程非常繁琐且有较多的缺陷&#xff1a; 动态操作Excel非常繁琐,对于新手来说&#xff0c;很难在短时间内上手;读写时需要占用…...

字段临时缓存包装器

前言 在实际开发中&#xff0c;我们有时候存在一种需求&#xff0c;例如对于某个字段&#xff0c;我们希望在某个明确的保存节点前对字段的修改都仅作为缓存保留&#xff0c;最终是否应用这些修改取决于某些条件&#xff0c;比如玩家对游戏设置的修改可能需要玩家明确确认应用修…...

Python(三)——列表

文章目录 创建列表访问下标遍历列表元素新增元素查找元素删除元素连接列表切片操作 创建列表 创建列表主要有两种方式 [ ]表示一个空的列表 a [] print(type(a)) # <class list> print(a) # []通过list()的方式来创建一个空列表 a list() print(type(a)) # …...

MySQL--三大范式(超详解)

目录 一、前言二、三大范式2.1概念2.2第一范式&#xff08;1NF&#xff09;2.3第二范式&#xff08;2NF&#xff09;2.3第三范式&#xff08;3NF&#xff09; 一、前言 欢迎大家来到权权的博客~欢迎大家对我的博客进行指导&#xff0c;有什么不对的地方&#xff0c;我会及时改进…...

追梦无Bug的软件世界

追梦无Bug的软件世界&#xff1a;测试人员的视角与探索 我有一个梦想&#xff0c;今天我们共同承载着一个愿景&#xff1a;创造一个没有Bug的软件世界。 我梦想有一天&#xff0c;用户将享受到完全无Bug的软件体验&#xff0c;用户不再因为软件中的Bug而感到困扰和沮丧。 我梦…...

在C#中使用Redis实现高效消息队列

使用Redis实现C#中的消息队列 Redis是一种开源的内存数据结构存储系统,因其高性能和灵活性被广泛用于缓存、数据库和消息队列等场景。本文将详细介绍如何在C#中使用Redis实现一个简单的消息队列,涵盖环境准备、代码实现和使用示例。 1. 环境准备 1.1 安装Redis 首先,确保…...

微服务JMeter解析部署使用全流程

目录 1、介绍 2、下载 3、运行 4、设置简体中文版 5、开始测试 1、添加线程组 2、添加监听器 3、添加请求 先.测试userController里的查询方法 6、查看结果 1、查看结果树 2、汇总报告 3、聚合报告 7、JMeter报错 1、介绍 Apache JMeter 是 Apache 组织基于 Java…...

Python 从入门到实战32(数据库MySQL)

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;通过熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们讨论了数据库编程接口操作的相关知识。今天我们将学习…...

hrnet训练的pt模型结合目标检测进行关键点识别的更准确前向推理

本篇在将图像输入hrnet识别之前先进行目标检测来确定识别的位置&#xff0c;让识别更加精准。 本段代码设置了一个区域框BOX&#xff0c;让人走入区域内才开始检测&#xff0c;适用于考核等场景&#xff0c;也可以直接去掉BOX也是一样的效果。若画面背景中有多个行人&#xff0…...

Leetcode 3306. Count of Substrings Containing Every Vowel and K Consonants II

Leetcode 3306. Count of Substrings Containing Every Vowel and K Consonants II 1. 解题思路2. 代码实现 题目链接&#xff1a;3306. Count of Substrings Containing Every Vowel and K Consonants II 1. 解题思路 这一题的话思路上就是一个滑动窗口&#xff0c;考察没一…...

算法笔记(五)——分治

文章目录 算法笔记&#xff08;五&#xff09;——分治快排颜色分类排序数组数组中的第K个最大元素库存管理 III 归并排序数组交易逆序对的总数计算右侧小于当前元素的个数翻转对 算法笔记&#xff08;五&#xff09;——分治 分治算法字面上的解释是“分而治之”&#xff0c;就…...

多级侧边菜单(递归)

需要编写两个文件 aside-menu.vue 和 menu-item.vue menu-item.vue <script setup> defineOptions({name: MenuItem}) defineProps({menuList: Array}) </script><template><template v-for"menu of menuList"><!-- 如果当前有子菜单&a…...

JavaScript break与continue语句

break语句和continue语句都具有跳转作用&#xff0c;可以让代码不按既有的顺序执行。 break break语句用于跳出代码块或循环 for(i0;i<100;i){if(i5){break;}console.log(i);} continue continue语句用于应即终止本轮循环,返回循环结构的头部&#xff0c;开始下一轮循环。…...

算法【从递归入手一维动态规划】

动态规划&#xff1a;用空间代替重复计算&#xff0c;包含一整套原理和技巧的总和。后面会有非常多的文章介绍动态规划。 有些递归在展开计算时&#xff0c;总是重复调用同一个子问题的解&#xff0c;这种重复调用的递归变成动态规划很有收益。如果每次展开都是不同的解&#…...

wordpress一页主题/河南郑州最新事件

一、前言&#xff1a;帝国CMS提供了强大的自定义字段处理函数功能&#xff0c;极大的方便了用户对帝国CMS进行二次开发&#xff01;帝国CMS在增加/修改字段时可以设置“后台增加信息处理函数”、“后台修改信息处理函数”、“前台增加信息处理函数”、“前台修改信息处理函数”…...

做兼职推荐网站/网络营销方法有哪些

Hive数据库对象与用户自定义函数 Hive视图 Hive中的视图和关系型数据库中视图在概念上是一致的&#xff0c;都是一组数据的逻辑表示&#xff0c;享用基本原始表的数据而不会另生成一份数据&#xff0c;是纯粹的逻辑对象。本质上&#xff0c;视图是一条SQL语句的集合&#xff…...

网站备案后 换服务器/百度云

(1).Ansible具有如下特点&#xff1a; 部署简单&#xff0c;只需在主控端部署Ansible环境&#xff0c;被控端无需做任何操作&#xff1b;  默认使用SSH协议对设备进行管理&#xff1b;  主从集中化管理&#xff1b;  配置简单、功能强大、扩展性强&#xff1b;  支持AP…...

四川省乐山市建设银行网站/百度指数查询官方下载

在写xml文件的时候&#xff0c;需要注意有5个特殊的字符&#xff0c;分别是&#xff1a; &<>“’ 。如果在文件中需要写入这5个字符的时候&#xff0c;需要转换处理。常用处理方式有转义字符和CDATA。 转义字符 在 XML 中有 5 个预定义的实体引用&#xff1a; <&l…...

做车身拉花的网站/搜索引擎优化方法有哪些

https://blog.csdn.net/C_chuxin/article/details/88762694...

卡盟网站专用主机/seo软文是什么意思

Win7之家(www.win7china.com)&#xff1a;软媒时间3.08正式版&#xff1a;让Win7用上最美桌面日历一直以来&#xff0c;我们都希望软媒时间能够承担起我们的一份愿景&#xff0c;就是能让您的工作、学习、生活更加得心应手。这次我们要发布的软媒时间3.08正式版&#xff0c;就是…...