双指针算法_复写零

题目:

给一个固定长度的数组arr,将数组中出现的每一个0都复写一遍,并且将其余元素都往右移动

且不要再超过数组长度的位置写入元素,在数组上直接修改

示例:

双数组模拟操作: 

  • 从示例来看,因为数组的长度不能变动,导致右移动时,会把原来右边的元素挤出数组。
  • 在进行原数组修改之前,我们先进行双数组的模拟运算, 就如上图所示,开辟一个一模一样的数组空间,空间的首元素地址上方存在指针dest,而原数组的首元素地址上方摆放指针cur。
  • 当cur指针遇见非0元素时,将dest指向的空间位置拷贝该元素,随后dest和cur都同时向前移动。
  • 当cur遇见0元素时,dest指向的空间位置放入0元素,随后再向前一位,再度放置0元素,最后cur指针和dest指针向前移动。
  • 最后,dest移动到所在数组最后一个元素位置时,cur指针刚好移动到进行复写0操作后的最后一个存在于数组内部的元素。

操作总结: 

通过示例和双数组模拟操作的过程,我们可以得出结论,如果使用双指针从左到右进行0的复写,那么势必会覆盖数组原有的元素,所以双指针进行操作的方向必须改变,变成从右到左,从后向前! 

而如果往后向前操作,还是dest和cur一同出现再末端吗?

并不是,因为本题的示例中本就有右端的元素被挤出数组,所以直接将cur指针指向复写操作后数组的最后一个元素位置,而dest则指向数组的末端,直接进行元素的覆盖!

非0时直接将cur的元素交给dest,把dest指向的元素进行覆盖,而为cur指向0时dest指向的元素变成0并且往前移一步,再度把指向的元素变成0,随后cur和dest同时向前移动。

将cur指向的元素覆盖给dest指针指向的元素。 

复写操作后的最后一个元素的查询 :

继续使用双指针的操作,我们将dest定义为最后一个需要复写的位置,当前这里没有找到最后一个需要复写的位置,所以初始位置这里变成-1的位置,cur则是查看是0还是非0让dest向前1步还是两步。

cur遇到非0,dest向前一步!同时判断dest是否在数组的末端,不是则cur继续往前走! 

 当cur遇到0,dest向前移动两步,继续判断dest是否在数组末端,没有cur继续向前走!

因为cur是非0所以dest向前移动,然后dest抵达了数组的末端,随后结束得到了cur为最后一个复写的数 

操作总结:

处理边界问题: 

最后一个复写的数是0,且dest发生了越界!

所以要处理边界情况,当最后一个复写的数是0是,可能会把复写的数复写到外边!因为0复写两边!

处理:当最后一个是0时,必然会发送越界操作,因为我们是在查找到复写后的最后一个元素之后,进行直接返回操作,而遇到越界操作时,dest指针会跑到外面,所以拷贝的时候会出现错误。

所以为了处理这种问题,我们将dest前面一格的位置变成0,随后将cur指针向前移动一格,dest指针向前移动两格 

代码实现: 

 

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

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

相关文章

Linux 中搭建 主从dns域名解析服务器

CSDN 成就一亿技术人! 作者主页:点击! Linux专栏:点击! CSDN 成就一亿技术人! ————前言———— 主从(Master-Slave)DNS架构是一种用于提高DNS系统可靠性和性能的配置方式。…

视频素材在哪里找?5个无版权视频素材网站

今天我再给大家介绍几个视频素材在哪里找,希望能帮你的短视频创作更加顺手: 蛙学网: 蛙学网是国内的一个视频素材平台,适合做短视频的朋友。这里的素材非常多,涵盖了各种风格和主题。更新速度也很快,能够帮…

Java多线程实战-异步操作日志记录解决方案(AOP+注解+多线程)

🏷️个人主页:牵着猫散步的鼠鼠 🏷️系列专栏:Java全栈-专栏 🏷️本系列源码仓库:多线程并发编程学习的多个代码片段(github) 🏷️个人学习笔记,若有缺误,欢迎评论区指正…

Python笔记|字符串的转义

重新梳理一遍python的基础知识 除了数字,Python 还可以操作字符串。字符串有多种表现形式,用单引号(……)或双引号("……")标注的结果相同 。反斜杠 \ 用于转义: >>>spam e…

QT网络编程之实现TCP客户端和服务端

推荐一个不错的人工智能学习网站,通俗易懂,内容全面,作为入门科普和学习提升都不错,分享一下给大家:前言https://www.captainbed.cn/ai 一.QT5.12实现TCP客户端和服务端功能 1.QT中实现TCP通信主要用到了以下类&…

weblogic CVE-2023-21839详细复现

1、本次复现使用vulhub的靶场 切换到靶场的目录下,用docker -compose up -d启动靶场 使用docker-compose ps -a查看靶场的端口 2、访问开启的环境 3、准备工作都做好之后开始复现 (1)开启JNDIExploit 工具地址:GitHub - WhiteH…

拌合楼内部管理系统开发(一)立个flag,开始做准备

前言:项目背景情况介绍 公司有意开发一套适合拌合楼的内部管理系统给到客户使用,接触过一家拌合楼行业内号称标杆的企业,去过参观学习的都觉得他们软件好用,但是从软件开发角度看,就是crud钉钉机器人无人值守。虽然公司…

开源绘图工具 PlantUML 入门教程(常用于画类图、用例图、时序图等)

文章目录 一、类图二、用例图三、时序图 一、类图 类的UML图示 startuml skinparam classAttributeIconSize 0 class Dummy {-field1 : String#field2 : int~method1() : Stringmethod2() : void } enduml定义能见度(可访问性) startumlclass Dummy {-f…

基于ssm+layui的图书管理系统

基于ssmlayui的图书管理系统 账户类型分为:管理员,用户管理员私有功能用户私有功能公共功能技术栈功能实现图 视频演示 账户类型分为:管理员,用户 图书管理系统主要登录账户类型为管理员账户与用户账户 管理员私有功能 账户管理…

如何压缩图片文件大小?教大家几种方法

当图片文件较大时,图片压缩可以有效的缩小图片kb,从而使图片储存起来更加方便,也可以解决上传时图片大小被限制的问题,那么我们有什么方法可以简单快速的将图片大小压缩呢?下面就来给大家分享几个如何修改照片大小kb的…

VS2022开发上位机流程

1、生成串口调试助手的主要控件 2、生成串口对象 3、书写代码 3.1 串口的选择 跳转到图形化界面,然后双击空白位置,会自动生成From1_Load,此函数的作用是会更新串口的选择,然后加入代码,combox控件就可以识别串口 /* 新增自定义…

windows系统版本是win11 运行程序显示windows版本是win10,

在Windows 11系统中运行程序时显示的Windows版本是Windows 10,这种现象可能是由以下几个原因导致的: 程序兼容性问题: 某些程序可能尚未更新以识别Windows 11操作系统,因此它们仍然报告系统为Windows 10。程序读取的是遗留的系统信…

机器学习-04-分类算法-02贝叶斯算法

总结 本系列是机器学习课程的系列课程,主要介绍机器学习中分类算法,本篇为分类算法与贝叶斯算法部分。 本门课程的目标 完成一个特定行业的算法应用全过程: 懂业务会选择合适的算法数据处理算法训练算法调优算法融合 算法评估持续调优工程…

Linux服务器(RedHat、CentOS系)安全相关巡检shell脚本

提示:巡检脚本可以使用crontab定时执行,人工根据执行结束时间点统一收集报告文件即可。 #!/bin/bash# Define output file current_date$(date "%Y%m%d") # Gets the current date in YYYYMMDD format echo >server_security_inspection_r…

【C++ RB树】

文章目录 红黑树红黑树的概念红黑树的性质红黑树节点的定义红黑树的插入代码实现总结 红黑树 AVL树是一颗绝对平衡的二叉搜索树,要求每个节点的左右高度差的绝对值不超过1,这样保证查询时的高效时间复杂度O( l o g 2 N ) log_2 N) log2​N),…

openwrt下部署clouddrive2

在启动项上增加启动参数 在exit 0前面增加 mount --make-shared /mnt/data480g注意,后面的/mnt/data480g要替换成你设置的共享映射券。 拉取镜像 docker pull cloudnas/clouddrive2启动镜像 一定要用ssh在后台用docker run命令启动,因为openwrt前台…

Windows 安装配置 RabbitMQ 详解

目录 1、安装前准备2、安装Erlang2.1 安装2.2 配置环境变量 3、安装RabbitMQ3.1 安装3.2 配置环境变量3.3 安装rabbitmq_management插件3.4 启动RabbitMQ服务 4、常用命令 本文将详说如何在Windows系统中安装RabbitMQ。 1、安装前准备 因为RabbitMQ服务器是用Erlang语言编写的…

AQY214S固态继电器:用于控制各种应用中的模拟信号的紧凑解决方案

AQY214S是一款多功能固态继电器,是一款经过精心设计的精致固态继电器,可在多种应用中与低电平模拟信号共舞。在这次探索中,我们将揭开AQY214S的复杂性,重点介绍其独特的功能,并深入研究其在不同行业中的应用的迷人挂毯…

MySQL MHA故障切换

目录 一、案例分析 1.1、案例概述 1.2、案例前置知识点 1)什么是 MHA 2)MHA 的组成 3)MHA 的优势 4)MHA 现状 1.3、案例环境 1)本案例环境 ​编辑 2)案例需求 3)案例实现思路…

基于springboot的七彩云南文化旅游网站的设计与实现(论文+源码)_kaic

摘 要 传统办法管理信息首先需要花费的时间比较多,其次数据出错率比较高,而且对错误的数据进行更改也比较困难,最后,检索数据费事费力。因此,在计算机上安装七彩云南文化旅游网站软件来发挥其高效地信息处理的作用&am…