每日一题
leetcode1089—复写零

给你一个长度固定的整数数组 `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]

解法一：双指针

先找到最后一个需要写进数组的元素，然后从后往前按照条件写，注意处理特殊情况——越界

时间复杂度：O(n)

空间复杂度：O(1)
void duplicateZeros(vector<int>& arr)
{
//1.查找最后一个写的元素
int cur = -1, dest = -1;
int sz = arr.size();
while (cur < sz)
{
if (arr[++cur]) dest++;
else dest += 2;
if(dest >= sz - 1) break;
}
//2.处理特殊情况——dest越界
if (dest == sz)
{
arr[--dest] = 0;
cur--;
dest--;
}
//3.从后往前复写
while (cur >= 0)
{
if(arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}