优先算法 —— 双指针系列 - 复写零
优先算法 —— 双指针系列 - 复写零
1. 复写零
题目链接： 1089. 复写零 - 力扣（LeetCode）
https://leetcode.cn/problems/duplicate-zeros/description/
2. 算法原理
其实本题严格来说是一题半模拟半双指针的题目
一般情况下 我们可以先进行异地操作，然后再优化成为双指针下的就地操作 当Cur遇到非0元素的时候，直接写下来，当遇到0的时候，就需要写两遍.....
改为就地操作：从左到右（错误） 将两个指针定义到一个数组上
但是我们发现：当cur到达第一个0时，dest执行两次写入0，将原本2的值给覆盖掉了，那么整个数组都会出现错误，所以从左到右这个方法是不可以的
从右到左 那我们来试试从右到左能否成功 因为是从右到左，所以我们将dest指向最后一个数，cur指向最后一个复写的数，以示例1为例，就是指向4 如果cur当前指向的值不为0，那么就直接把cur指向的值写入dest，再同时-- 如果cur当前指向的值为0，那么cur往左移动一位，dest移动2位
然后我们发现从右到左这种方法是可以的
总结一下解决方法： 1. 先找到最后一个复写的数 2. 以从右到左的顺序完成复写操作
如何找到最后一个复写的数 双指针算法 1. 定义一个cur指向数组里第一个数的位置，dest指向-1的位置 因为要把dest定义为结果中最后一个的位置，因此我们只需要判断dest是否跑到最后一个位置就可以了
然后按照下面的步骤来重复进行：
然后就找到最后一个复写的数了
特殊情况 当查找最后一个复写的数时cur为0时，我们会发现会出现访问越界的问题，会造成内存泄漏的情况
解决方法也很简单：我们直接将4这个位置也就是n-1变为0，然后再进行cur--，dest-=2
完整步骤： 1. 先找到最后一个复写的数 2. 处理特殊情况 3. 以从右到左的顺序完成复写操作
3. 代码
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
//1. 先找到最后一个复写的数
int cur=0,dest=-1,n=arr.size();
while(cur<n)
{
//先判断cur位置的值
//不为0dest往后移动1步，为0移动2步
if(arr[cur]) dest++;
else dest+=2;
//判断一下dest是否已经到达结束位置
if(dest>=n-1) break;//n为size，在数组最后一个位置的下一个位置
//cur++
cur++;
}
//2. 处理特殊情况
//如果dest越界
if(dest==n)
{
arr[n-1]=0;
cur--;
dest-=2;
}
//3. 以从右到左的顺序完成复写操作
while(cur>=0)
{
//如果cur当前指向的值不为0，那么就直接把cur指向的值写入dest，再同时--
if(arr[cur]) arr[dest--]=arr[cur--];
else
{
//为0要写2遍
//然后cur往左移动一位，dest移动2位
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};未完待续~
腾讯云开发者
