php双语网站,php网站开发教学,成都 网站建设培训,深圳市城乡建设部网站首页LeetCode原题链接#xff1a;1089. 复写零
下面是题目描述#xff1a; 给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。
注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 …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(vectorint 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但size2表示将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(vectorint arr) {int mov 0;int size 0;while(size arr.size()){if(arr[mov] 0){size2;}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--;}}
};看完觉得有觉得帮助的话不妨点赞收藏鼓励一下有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论多多指点谢谢朋友们
