优先算法 —— 双指针系列 - 复写零
目录
1. 复写零
2. 算法原理
一般情况下
改为就地操作：从左到右（错误）
从右到左
总结一下解决方法：
如何找到最后一个复写的数
特殊情况
完整步骤：
3. 代码
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--;}}}
};未完待续~