复写零——双指针算法
题目链接
复写零
https://leetcode.cn/problems/duplicate-zeros/description/
题目要求
样例
题目分析
先看示例1，题目要求将数组中所有的0，均复写一遍，且要在原数组上进行更改，多余的元素消失
但我们发现，如果双指针从后往前遍历，即
cur 初始指向最后一个复写的数，按上述方法，进行从后往前复写，显然是可以的，所以我们首先要找出最后一个复写的数，再进行遍历即可
算法思路
如果「从前向后」进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两 步：
i. 先找到最后⼀个复写的数；
ii. 然后从后向前进行复写操作 ；
个人复写思路
1、找到最后复写的数
（1）定义两个指针如下图，判断cur的值处是否为 0 ？
为 0：dest 后移两步
不为 0：dest 后移一步
（2）判断 dest 是否指向数组最后一个元素位置 ，如果是，则停止，不是 cur 后移一步
（3） 最后 cur 指向即最后复写元素
2，判断 dest 是否越界
此情况下，dest 会越界，此时我们需要将数组最后位置设置为 0 ，dest 前移2步，cur 前移1步即可，如图：
3、从后向前进行复写操作
解题代码
class Solution {
public void duplicateZeros(int[] arr) {
int cur=0,dest=-1;
while(cur<arr.length){
if(arr[cur]==0){
dest+=2;
}else{
dest++;
}
if(dest>=arr.le-1){
break;
}
cur++;
}
if(dest==arr.length){
arr[arr.length-1]=0;
dest-=2;
cur--;
}
while(cur>=0){
if(arr[cur]==0){
arr[dest--]=0;
arr[dest--]=0;
}else{
arr[dest--]=arr[cur];
}
cur--;
}
}
}