双指针算法实例1(移动零)
常⻅的双指针有两种形式:
1 对撞指针(左右指针):
a 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼
近
b 终止条件一般是两指针相遇or错过(也可能在循环过程中找到结果直接跳出循环),即
left == right (两个指针指向同⼀个位置)
left > right (两个指针错开)
2 快慢指针:
使⽤两个移动速度不同的指针在数组或链表等结构上移动
特别是处理环形链表或数组时有很大用处,也就是说当问题出现循环往复的情况时,可考虑使用快慢指针的思想
题目:
给定一个数组 ,编写一个函数将所有 移动到数组的末尾,同时保持非零元素的相对顺序。nums0
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
代码实现:
class Solution
{
public:void moveZeroes(vector<int>& nums){int cur = 0;//遍历数组int pre = -1;//指向非0元素区域中最后一个非0元素while(cur<nums.size()){if(nums[cur])//找到非0元素{swap(nums[++pre],nums[cur]);//将非0元素与0元素交换,++pre指向的一定是0元素}cur++;}}
};
思路详解:
题目要求实现的功能,可以说是数组划分(数组分块)让非0元素排在前半部分,0元素排在后半部分,且要求元素间的相对顺序保持不变。
方法:
前后指针法
(此处的指针是用数组的下标来充当的,并不是真正意义上的指针)
1 cur指针去从左向右遍历数组(只需要一直向前走就行)指向的是待处理的元素
2 pre指针记录已处理区间内的非0元素区域,最后一个非0元素的下标
cur初始化为0,因为要从0下标开始遍历
pre初始化为-1,因为pre指向的是已处理区间中的非0元素区的最后一个非0元素下标,刚开始还没有确定任何一个元素是否是非0元素
思想:
cur负责遍历数组,指向待处理的元素:
找到的是非0元素,则将它交换到前面
找到的是0元素,则视而不见,直接++走向下一个待处理元素
pre指向的始终是已处理区间中的非0元素区的最后一个非0元素的下标,cur因为遇到0而不断++,与pre拉开距离
那么[pre+1,cur-1]的区间是已处理区间中的0元素区
在处理过程中,数据分三区:
[0,pre]:全都是非0元素
[pre+1,cur-1]:全是0元素
[cur,n-1]:n是数组元素个数,是待处理的元素

简单来说,就是cur在遍历过程中若是遇到非0元素,则将它与0元素交换,让非0元素换到前面,0元素换到后面,[pre+1,cur-1]的区域内全是0元素,遇到0元素则不管,直接++找下一个待处理元素
完结撒花~
题外话:解决此题目的前后指针法其实和快排中实现数组划分的方法之一类似,也可以成之为前后指针法,但是实现略有差异,且在实现后,快排中数组元素的相对顺序可能会发生改变
详情在我的另一篇快排模拟实现的博客中:
http://t.csdn.cn/2Km96
相关文章:
双指针算法实例1(移动零)
常⻅的双指针有两种形式: 1 对撞指针(左右指针): a 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼 近 b 终止条件一般是两指针相遇or错过(也可能在循…...
C#程序随系统启动例子 - 开源研究系列文章
今天讲讲C#中应用程序随系统启动的例子。 我们知道,应用程序随系统启动,都是直接在操作系统注册表中写入程序的启动参数,这样操作系统在启动的时候就根据启动参数来启动应用程序,而我们要做的就是将程序启动参数写入注册表即可。此…...
最全攻略之人工智能顶会论文发表
最全攻略之人工智能顶会论文发表 1. 人工智能顶会1.1 CCF 顶会列表2023年人工智能顶会时间线 2.人工智能顶会论文发表流程2.1 顶会论文发表流程2.2 顶会论文审稿流程 3.1顶会论文发表指南3.1 顶会论文七要素3.2 顶会论文写作要点 4.人工智能发展趋势4.1 人工智能未来趋势4.2 人…...
Redis基于内存的key-value结构化NOSQL(非关系型)数据库
Redis Redis介绍Redis的优点Redis的缺点Redis的安装Redis的连接Redis的使用Redis中的数据类型String的使用get setsetex(expire)ttlsetnx(not exit)HashList列表(队列)Set集合ZSet集合Redis 通用命令Redis图形客户端Redis在Java中的使用RedisTemplate...
Spring学习笔记+SpringMvc+SpringBoot学习笔记
壹、核心概念: 1.1. IOC和DI IOC(Inversion of Control)控制反转:对象的创建控制权由程序转移到外部,这种思想称为控制反转。/使用对象时,由主动new产生对象转换为由外部提供对象,此过程种对象…...
如何在 3Ds Max 中准确地将参考图像调整为正确的尺寸?
您是否想知道如何在 3Ds Max 中轻松直观地调整参考图像的大小,而无需借助第三方解决方案、插件或脚本? 我问自己这个问题,并高兴地发现了FFD Box 2x2x2,我无法停止钦佩这个修改器的多功能性。 在本文中,我想与您分享一…...
集简云推出的全国第一款 AI+连接器解决方案产品语聚AI
语聚AI是集简云推出的全国第一款 AI连接器解决方案产品,官网:https://yuju.jijyun.cn 语聚AI包括了多个不同的AI功能,协助企业和个人更好的使用AI语言模型所带来的能力,包括: 应用助手 希望通过AI智能助手帮助您查询C…...
git错误记录
露id没有影响,搞得微软不知道我ip一样 git fatal: 拒绝合并无关的历史的错误解决(亲测有效)...
linux使用jmeter进行压测
1.准备好服务器,这里默认服务器用的系统镜像为contos7.9.2009 2.准备好jmeter的测试计划文件 .jmx 这里默认测试计划的jmx文件在 /nas目录下 3.安装JDK与jmeter进行测试 #创建JDK与jmeter目录,并复制安装文件 mkdir /jmeter mkdir /jmeter/jav…...
leetcode 139. 单词拆分
2023.8.18 本题可以看作完全背包问题,字符串s为背包,字符串列表worddict中的字符串为物品。由于本题的物品集合是排列问题(即物品的排列顺序对结果有影响),所以遍历顺序为:先遍历背包再遍历物品。 接下来看代码: clas…...
若依的使用(token补充、HTTPS(网络安全)、分页前后端配置)
本文章转载于公众号:王清江唷,仅用于学习和讨论,如有侵权请联系 QQ交流群:298405437 本人QQ:4206359 具体视频地址:8 跑后端_哔哩哔哩_bilibili 1、HTTP? 曾经我们在讲JWT的时候,当时JWT需要配合https…...
Java源码分析(一)Integer
当你掌握Java语言到了一定的阶段,或者说已经对Java的常用类和API都使用的行云流水。你会不会有一些思考?比如,这个类是如何设计的?这个方法是怎么实现的?接下来的一系列文章,我们一起学习下Java的一些常见类…...
WebRTC音视频通话-WebRTC视频自定义RTCVideoCapturer相机
WebRTC音视频通话-WebRTC视频自定义RTCVideoCapturer相机 在之前已经实现了WebRTC调用ossrs服务,实现直播视频通话功能。但是在使用过程中,RTCCameraVideoCapturer类提供的方法不能修改及调节相机的灯光等设置,那就需要自定义RTCVideoCaptur…...
【基于鲲鹏及openEuler20.03TLS下MySQL8.0.17性能调优】
【基于鲲鹏及openEuler20.03TLS下MySQL8.0.17性能调优】 一、环境说明二、实验过程三、实验小结 一、环境说明 华为云ECS 规格:8vCPU 32G arm架构操作系统:openEuler 20.03.TLSMySQL版本:8.0.17 二、实验过程 创建用户及用户组:…...
GRPC 学习记录
GRPC 安装 安装 grpcio、grpcio-tools、protobuf、 pip install grpcio -i https://pypi.tuna.tsinghua.edu.cn/simple pip install grpcio-tools -i https://pypi.tuna.tsinghua.edu.cn/simple pip install protobuf -i https://pypi.tuna.tsinghua.edu.cn/simple常用类型 p…...
C++语言的QT写软件界面,结合python深度学习模型的综合应用处理方案
C与python问题合集: 后面内容涉及到api的创建问题 如果我用C语言的QT写软件界面,然后用python语言去写和人工智能相关的东西。就比如说一些模型,那么现在我想将用python写的模型放在QT写的软件当中调用,那么请问是否会导致C语言…...
Linux环境下python连接Oracle教程
下载Oracle client需要的 安装包 rpm包下载地址:Oracle官方下载地址 选择系统版本 选择Oracle版本 下载3个rpm安装包 oracle-instantclient12.2-basic-12.2.0.1.0-1.i386.rpm oracle-instantclient12.2-devel-12.2.0.1.0-1.i386.rpm oracle-instantclient12.2-sq…...
第 7 章 排序算法(1)
7.1排序算法的介绍 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。 7.2排序的分类: 内部排序: 指将需要处理的所有数据都加载到**内部存储器(内存)**中进行排序。外部排序法: 数据量过大&am…...
wsl,字体乱码问题
配置wsl,字体乱码问题 一、前言 用zsh配置好wsl,每次打开还是会出现乱码,只有再新打开一个终端才会显示字体 如下图:第一次打开,出现乱码 如图:按加号,再开一个新终端才会显示字体。 二、解…...
【NetCore】10-路由定义
文章目录 路由与终结点:如何规划好Web Api1. 路由1.1 路由映射1.2 路由注册方式1.3 路由约束总结: Web Api定义 路由与终结点:如何规划好Web Api 1. 路由 1.1 路由映射 路由系统核心作用是指URL和应用程序Controller的对应关系的一种映射 这种映射的作…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
