复写零
题目链接：1089. 复写零 - 力扣（LeetCode）
给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
思路解析：
本题有两种思路：
- 暴力复写
- 双指针原地复写
- 暴力复写
暴力的方法很简单，因为是复写，所以只需要遇到0先将0位置后面的数据进行挪动覆盖，但是注意要从尾部开始挪动，挪动完毕后在当前位置的下一个位置插入一个数字0，让指针走两步
暴力复写参考代码：
/*
* @lc app=leetcode.cn id=1089 lang=cpp
*
* [1089] 复写零
*/
// @lc code=start
// 暴力解法
class Solution
{
public:
void duplicateZeros(vector<int> &arr)
{
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] == 0 && arr.size() - 2 > 0)
{
int j = arr.size() - 2;
while (j + 1 < arr.size() && j > i)
{
arr[j + 1] = arr[j];
j--;
}
if (i + 1 < arr.size())
{
arr[++i] = 0;
}
}
}
}
};
// @lc code=end- 双指针原地复写
对于双指针算法来说，有两种实现方式，第一种是异地复写，即开辟一个新空间，基本思路为遇到非0数字复写一次，遇到数字0复写两次，但是这个算法的空间复杂度为O(N)，所以考虑原地复写
双指针——异地复写参考代码：
/*
* @lc app=leetcode.cn id=1089 lang=cpp
*
* [1089] 复写零
*/
// @lc code=start
// 双指针——异地操作
class Solution
{
public:
void duplicateZeros(vector<int> &arr)
{
vector<int> ret;
ret.resize(arr.size());
int cur = 0;
int dest = 0;
while (dest < ret.size())
{
if (arr[cur] == 0)
{
dest++;
dest++;
cur++;
}
else
{
ret[dest++] = arr[cur++];
}
}
arr.assign(ret.begin(), ret.end());
}
};
// @lc code=end原地复写和异地复写的思路是一致的，但是原地复写不可以从源数组的第一个元素开始复写，这样会导致遇到数字0时后面的内容全部都覆盖为0，正确的做法是从最后一个待复写元素开始向最后一个位置进行复写，再依次往前遍历执行复写操作，复写具体操作为：
- 遇到非0数字向dest位置覆写当前cur位置的数字
- 遇到0数字向dest位置和dest-1位置复写两个0
- cur向前移动1步
现在的问题就是如何找到最后一个待复写的元素，可以考虑一次正向遍历，但是在这一次遍历中不进行任何的复写操作，具体操作为：
- cur所在位置是非0的数字：dest移动一步
- cur所在位置是数字0：dest移动两步
- 判断dest是否到最后一个元素的位置
- cur移动一步
遍历完成后cur所指向的位置即为最后一个待复写的元素，而dest所指向的位置即为最后一个元素的位置，如图所示：
但是此时需要注意一种特殊情况：
当指向的待复写元素是0时，那么此时dest指向的位置已经超出了数组的范围，如果此时在dest位置复写时就会出现越界访问的情况，那么此时需要进行边界修正，修正方法如下：
- 在
dest-1的位置处覆写数字0 cur向前走动一步dest向前走动两步
处理完边界情况后就可以进行正常的复写操作过程
双指针——原地复写参考代码：
/*
* @lc app=leetcode.cn id=1089 lang=cpp
*
* [1089] 复写零
*/
// @lc code=start
// 双指针——原地操作
class Solution
{
public:
void duplicateZeros(vector<int> &arr)
{
int cur = 0, dest = -1;
int sz = arr.size();
// 找到结果数组中的最后一个重写的元素的位置
while (cur < sz)
{
if (arr[cur] == 0)
{
dest += 2;
}
else
{
dest++;
}
if (dest >= sz - 1)
{
break;
}
cur++;
}
// 修正边界情况
if (dest == sz)
{
arr[dest - 1] = 0;
cur--;
dest -= 2;
}
// 覆写
while (cur >= 0)
{
if (arr[cur])
{
arr[dest--] = arr[cur--];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
// @lc code=end
