【算法学习】-【双指针】-【复写零】
LeetCode原题链接:1089. 复写零
下面是题目描述:
给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。
注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。
- 示例 1:
输入:arr = [1,0,2,3,0,4,5,0]
输出:[1,0,0,2,3,0,0,4]
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4] - 示例 2:
输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]
通过这道题可以获得的经验主要有如下两点:
- 实现“复写”之类的操作时,可以优先考虑从后往前进行复写,即多思考算法执行的顺序;
- 题目要求在原地对数组进行修改,但在分析时可以先按另外开辟空间的角度进行分析,然后再根据过程中进行操作的特点,通过指针模拟出在原数组中模拟出整个过程
下面是解题思路以及具体代码:
1、BF解法
根据题目描述,很容易想到这个暴力解法,也不涉及到有关双指针算法的运用,所以这里仅进行简单的陈述,对于想了解双指针解法的朋友可直接跳过~。
思路:从后往前遍历,每遇到一个0时,就从数组的倒数第二位开始,往自己的后一位去复写,即arr[n] = arr[n-1]
;直至到当前0的后一个位置。
如示例1中,从后往前第一个0的下标为4,那么当从后往前遍历到下标为4时,就从下标为6的位置(倒数第二位)开始依次往自己的后一位复写,直到下标为5(到当前0的后一个位置)。循环直至遍历完整个数组
具体代码为:
class Solution {
public:void duplicateZeros(vector<int>& arr) {int end = arr.size() - 1;int mov = end - 1;while(mov >= 0){if(arr[mov] == 0){while(end > mov){arr[end] = arr[end - 1];end--;}}mov--;end = arr.size() - 1;}}
};
2、双指针模拟容器
这是相对于解法1来说更好的解法,也是本文说明的重点。(PS:主要是对官方题解的理解总结)
我们可以先进行另开空间的过程分析,最后再通过指针在原数组上模拟。
那么从本题的要求来看,可以通过一个新的数组来进行数据的存储,即遍历原数组,遇到非0元素就将其放入一次进新数组中,遇到0就将其放入两次进vector中,直到新数组的大小等于或超过了(伏笔)原数组;
用示例1进行如上过程就为:
最后再将新数组对应原数组中的位置进行复写即可。
那么接下来的问题就是如何在原数组中模拟出这个过程。
-
首先是 “构建” 新数组:
说是构建,其实本质上是在原数组中找到新数组中最后一个数(或者说是用于复写原数组的第一个数),为复写做准备工作。
那么结合过程,我们可以这样找到这个数:
假设一个变量为mov
用于表示将要放入新数组中的下一个数在原数组中的下标(也就是上图中的i),另一个变量size
用于控制放入操作是否需要停止。接着遍历原数组,遇到非零元素mov
和size
一起++
;遇到零元素mov++
但size+=2
,表示将0放了两次到新数组中;循环直至size
大于等于原数组的大小。循环结束后mov
的位置即为新数组的最后一个数(示例一中的4)在原数组中的位置的下一个位置,故让mov--
指向新数组的最后一个数在原数组中的位置,准备进行复写 -
接下来是复写过程:
从原数组最后一个元素开始进行复写;用一个指针end
指向它,接着以mov
指针所对应的元素为判断依据,若是非零元素,则执行一次复写,复写完成后mov
和end
都往前移一位;若是零元素,则执行两次复写,复写完成后mov
往前移一位,end
往前移两位。循环执行如上过程直至复写完整个数组。 -
还有个坑:
上面说过,当新数组的大小等于或超过了原数组的大小时停止复写,等于原数组算是“正常”情况,新数组中零元素的个数为偶数个,即在原数组上复写时可以执行正确执行两次复写;但还有新数组的大小超过原数组的大小的情况,此时新数组中零元素的个数并不是偶数个,按照正常复写过程直接在原数组上复写会覆盖掉之前的数据,出现这种情况原因是最后需要复写两个零但空间只能再容纳一个零了,如这个测试用例:
[8,4,5,0,0,0,0,7]
当i = 5
时,新数组中的size = 7
,此时仅能再放入一个0,这意味着用双指针进行复写的时候,最后一个0只能复写一次
解决方法:
根据遇到0放入两次的操作,不符合条件跳出循环后,size的值是大于原数组的大小的(准确来说等于原数组大小+1),对这种情况进行特殊判断后先将最后一个元素进行复写,且mov
和end
都往前移一位后,再进行正常的复写即可。
完整的代码如下:
class Solution {
public:void duplicateZeros(vector<int>& arr) {int mov = 0;int size = 0;while(size < arr.size()){if(arr[mov] == 0){size+=2;}else{size++;}mov++;}mov--;int end;if(size == arr.size() + 1) //特殊判断{end = size - 2;arr[end] = 0;mov--;end--;}else{end = size - 1;}while(mov>= 0) {arr[end] = arr[mov]; //正常复写一次end--;if(arr[mov] == 0) //等于零再复写一次{arr[end] = arr[mov];end--; } mov--;}}
};
看完觉得有觉得帮助的话不妨点赞收藏鼓励一下,有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论,多多指点,谢谢朋友们!🌹🌹🌹
相关文章:

【算法学习】-【双指针】-【复写零】
LeetCode原题链接:1089. 复写零 下面是题目描述: 给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 …...
【算法优选】双指针专题——叁
文章目录 😎前言🌳[两数之和](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)🚩题目描述:🚩算法思路:🚩算法流程:🚩代码实现 🎄[三数之和]…...

Java栈的压入、弹出序列(详解)
目录 1.题目描述 2.题解 方法1 方法2 1.题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序…...

RabbitMQ学习笔记(消息发布确认,死信队列,集群,交换机,持久化,生产者、消费者)
MQ(message queue):本质上是个队列,遵循FIFO原则,队列中存放的是message,是一种跨进程的通信机制,用于上下游传递消息。MQ提供“逻辑解耦物理解耦”的消息通信服务。使用了MQ之后消息发送上游只…...

PyTorch - 模型训练损失 (Loss) NaN 问题的解决方案
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/133378367 在模型训练中,如果出现 NaN 的问题,严重影响 Loss 的反传过程,因此,需要加入一些微小值…...

8、Nacos服务注册服务端源码分析(七)
本文收录于专栏 Nacos 中 。 文章目录 前言确定前端路由CatalogController.listDetail()ServiceManager总结 前言 前文我们分析了Nacos中客户端注册时数据分发的设计链路,本文根据Nacos前端页面请求,看下前端页面中的服务列表的数据源于哪里。 确定前端…...

MySQL使用Xtrabackup在线做主从
1、主库上操作 1.1前提 172.16.11.2(主库) 172.16.11.4(从库) 在执行备份之前,确保数据库没有锁定,以避免备份期间的任何写操作。 确保主库上的 MySQL 服务器正在运行,以便备份数据的一致性。…...

scala基础入门
一、Scala安装 下载网址:Install | The Scala Programming Language ideal安装 (1)下载安装Scala plugins (2)统一JDK环境,统一为8 (3)加载Scala (4)创建工…...
【Java-LangChain:面向开发者的提示工程-5】推断
第五章 推断 推断任务可以看作是模型接收文本作为输入,并执行某种分析的过程。其中涉及提取标签、提取实体、理解文本情感等等。如果你想要从一段文本中提取正面或负面情感,在传统的机器学习工作流程中,需要收集标签数据集、训练模型、确定如…...

【C++】手撕vector(vector的模拟实现)
手撕vector目录: 一、基本实现思路方针 二、vector的构造函数剖析(构造歧义拷贝构造) 2.1构造函数使用的歧义问题 2.2 vector的拷贝构造和赋值重载(赋值重载不是构造哦,为了方便写在一起) 三、vector的…...
智能指针那些事
《Effective Modern C》学习笔记之条款二十一:优先选用std::make_unique和std::make_shared,而非直接new - 知乎...

Fiddler抓取手机https包的步骤
做接口测试时,有时我们需要使用fiddler进行抓包分析,那么如何抓取https包。主要分为以下七步: 1.设置fiddler选项:Tools->Options,按如下图勾选 2.下载并安装Fiddler证书生成器 下载地址:http://www.telerik.com/…...

idea没有maven工具栏解决方法
背景:接手的一些旧项目,有pom文件,但是用idea打开的时候,没有认为是maven文件,所以没有maven工具栏,不能进行重新加载pom文件中的依赖。 解决方法:选中pom.xml文件,右键 选择添加为…...

levelDB引擎
一、背景 1.1、影响磁盘性能的因素: 主要受限于磁盘的寻道时间,优化磁盘数据访问的方法是尽量减少磁盘的IO次数。磁盘数据访问效率取决于磁盘IO次数,而磁盘IO次数又取决于数据在磁盘上的组织方式。磁盘数据存储大多采用B树类型数据结构&…...
IM同步服务
设计概述 后台同步方案的设计就是数据存储结构的设计,如何快速体现“信息变化”,如何快速计算出“变化信息”。后台数据存储结构是由同步协议中同步契约决定的。 设计方案 该方案的同步是按照业务粒度来划分,只需要同步sdk要求同步的数据。…...
MySQL 运维常用脚本
常用功能脚本 1.导出整个数据库 mysqldump -u 用户名 -p –default-character-setlatin1 数据库名 > 导出的文件名(数据库默认编码是latin1) mysqldump -u wcnc -p smgp_apps_wcnc > wcnc.sql 2.导出一个表 mysqldump -u 用户名 -p 数据库名 表名> 导出的文件…...
ABC322刷题记
ABC322刷题记 T1.A A - First ABC 2。 妥妥的简单题…… 用find函数做就行。(如果不存在那个子串就返回-1,否则返回第一次出现位置) 注意题目中编号是从1开始的。 时间复杂度:O(log(n))。find函数有一定代价,我记…...

visual studio的安装及scanf报错的解决
visual studio是一款很不错的c语言编译器 下载地址:官网 点击后跳转到以下界面 下滑后点击下载Vasual Sutdio,选择社区版即可 选择位置存放下载文件后,即可开始安装 安装时会稍微等一小会儿。然后会弹出这个窗口,我们选择安装位…...
React生命周期
React的生命周期主要是指React组件从创建到销毁的过程,包括三个阶段:挂载期(实例化期)、更新期(存在期)、卸载期(销毁期) 挂载期: constructor(props&#…...

SpringBoot整合RocketMQ笔记
SpringBoot版本为2.3.12.Release RocketMQ对比kafka 学习链接 https://zhuanlan.zhihu.com/p/335216381 代码实战 https://www.cnblogs.com/RedOrange/p/17401238.html Centos安装rocketmq https://blog.csdn.net/chuige2013/article/details/123783612 RocketMQ详细配置与…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...

ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器
从本章节开始,进入到函数有多个参数的情况,前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参,ECX是整型的第一个参数的寄存器,那么多个参数的情况下函数如何传参,下面展开介绍参数为整型时候的几种情…...