目录
题目描述
题目解析
算法原理讲解
代码
题目描述
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 <= arr.length <= 1040 <= arr[i] <= 9
题目解析
题目意思就是遇到0了再写一遍0，其他元素向右平移就行。只能在原来数组上修改，也就是空间复杂度为0.
算法原理讲解
一般像这种在数组中移动一些数的题目，也是用双指针算法来解决这个问题。
双指针算法是根据异地解法的操作，优化成双指针的就地操作。
异地操作
异地操作就是，重新开辟一个数组。
定义两个指针，cur用来扫描原数组，dest用来更新新数组。
当cur对应的值不等于0时，dest更新一个数，将cur值直接填入dest的位置，dest++，cur++就行。
当cur对应的值等于0时，dest指针更新两个数，都填入0,cur++就行。
当dest=arrSize就结束了。
就地操作
就是不用重新开辟数组，也就是题目要求的那样，我们可以把cur和dest这两个指针，都放在原数组上。
用双指针解决复写问题的步骤
1.找到最后一个复写的数
2.从后向前完成复写
让cur指向最后一个复写的数，对于[1,0,2,3,0,4,5,0]这个数组，最后一个复写的数是4，所以让cur指向4 ，best指向最后一个位置就行。
cur指向的这个数是非零的，所以复写一次就行，复写完后，cur--,dest--。
这次cur指向0，那就复写两次，后cur--。
从图中可以看出，当cur和dest都指向-1的时候就复写完成了。
接下来有一个问题就是？——怎么找到最后一个复写的数
还是利用双指针算法，定义两个指针cur和dest,cur用来扫描数组，dest用来标识最后一个复写的数。
cur指向的值决定dest向后移动两步还是移动一步
1.先判断cur里面的值
2.决定dest走两步还是走一步
3.在判断dest到没到结尾
4.没到结尾再cur++
咱们一步一步来，arr[cur]现在指向了1，所以dest走一步到达下标为0的位置，dest没有走到结尾，所以cur++。
arr[cur]现在指向了0，所以dest走两步到达下标为2的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了2，所以dest走一步到达下标为3的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了3，所以dest走一步到达下标为4的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了0，所以dest走两步到达下标为6的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了4，所以dest走一步到达下标为7的位置，dest走到结尾返回cur。
对于这个数组这种方法是刚好的，那么如果是【1，0，2，3，0，4】
arr[cur]现在指向了1，所以dest走一步到达下标为0的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了0，所以dest走两步到达下标为2的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了2，所以dest走一步到达下标为3的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了3，所以dest走一步到达下标为4的位置，dest没有走到结尾所以cur++。
arr[cur]现在指向了0，所以dest走两步到达下标为6的位置，但是这个数组没有下标6最大直到5,所以会产生越界。
接下来，我们怎么解决这个问题，我们要明白越界是怎么产生的，是因为复写0,复写两次就产生了越界。这个情况我们单独处理一下。
那么怎么处理呢？我们在复写的时候将最后一个位置，和越界的那个位置都复写成0。但是越界那个位置不能修改成0，我们只需要把最后一个位置修改成0（直接在这里复写），也就是arr[arrSzie-1]=0,就可以。
修改之后我们将dest向前移动两步，cur向前移动一步
cur现在就是最后一个复写的值，接下来复写就从dest现在的位置开始复写。
代码
void duplicateZeros(int* arr, int arrSize) {
//找到最后一个复写的位置
int cur=0;
int dest=-1;
while(cur<arrSize)
{
if(arr[cur]==0)dest+=2;
if(arr[cur]!=0)dest+=1;
//如果dest到达最后一个位置就跳出循环
//如果刚好的话是等于arrSzie-1，有越界的时候是等于arrSize
if(dest==arrSize-1||dest==arrSize)break;
cur++;
}
//处理边界
if(dest==arrSize)
{
arr[arrSize-1]=0;
cur-=1;
dest-=2;
}
while(cur>=0&&dest>=0)
{
if(arr[cur]==0)
{
arr[dest--]=arr[cur];
arr[dest--]=arr[cur--];
}
else
{
arr[dest--]=arr[cur--];
}
}
}
