【算法学习】-【双指针】-【复写零】

2023-10-02 21:59
文章标签 算法 复写 指针 学习

本文主要是介绍【算法学习】-【双指针】-【复写零】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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用于控制放入操作是否需要停止。接着遍历原数组,遇到非零元素movsize一起++;遇到零元素mov++size+=2表示将0放了两次到新数组中;循环直至size大于等于原数组的大小。循环结束后mov的位置即为新数组的最后一个数(示例一中的4)在原数组中的位置的下一个位置,故让mov--指向新数组的最后一个数在原数组中的位置,准备进行复写

  • 接下来是复写过程
    原数组最后一个元素开始进行复写;用一个指针end指向它,接着以mov指针所对应的元素为判断依据,若是非零元素,则执行一次复写,复写完成后movend往前移一位;若是零元素,则执行两次复写,复写完成后mov往前移一位end往前移两位。循环执行如上过程直至复写完整个数组。

  • 还有个坑:
    上面说过,当新数组的大小等于或超过了原数组的大小时停止复写,等于原数组算是“正常”情况,新数组中零元素的个数为偶数个,即在原数组上复写时可以执行正确执行两次复写;但还有新数组的大小超过原数组的大小的情况,此时新数组中零元素的个数并不是偶数个,按照正常复写过程直接在原数组上复写会覆盖掉之前的数据,出现这种情况原因是最后需要复写两个零但空间只能再容纳一个零了,如这个测试用例:
    [8,4,5,0,0,0,0,7]
    i = 5时,新数组中的size = 7,此时仅能再放入一个0,这意味着用双指针进行复写的时候,最后一个0只能复写一次
    解决方法
    根据遇到0放入两次的操作,不符合条件跳出循环后,size的值是大于原数组的大小的(准确来说等于原数组大小+1),对这种情况进行特殊判断后先将最后一个元素进行复写,且movend都往前移一位后,再进行正常的复写即可。

完整的代码如下

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--;}}
};

看完觉得有觉得帮助的话不妨点赞收藏鼓励一下,有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论,多多指点,谢谢朋友们!🌹🌹🌹

这篇关于【算法学习】-【双指针】-【复写零】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

Java空指针异常NullPointerException的原因与解决方案

《Java空指针异常NullPointerException的原因与解决方案》在Java开发中,NullPointerException(空指针异常)是最常见的运行时异常之一,通常发生在程序尝试访问或... 目录一、空指针异常产生的原因1. 变量未初始化2. 对象引用被显式置为null3. 方法返回null

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各