1. 题⽬链接：1089.复写零
2. 题⽬描述：
3. 解法（原地复写-双指针）：
算法思路：
如果「从前向后」进⾏原地复写操作的话，由于0 的出现会复写两次，导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两 步：
i. 先找到最后⼀个复写的数；
ii. 然后从后向前进⾏复写操作。
算法流程：
a. 初始化两个指针cur = 0 ， dest = 0 ；
b. 找到最后⼀个复写的数：
i. 当cur < n 的时候，⼀直执⾏下⾯循环：
• 判断cur 位置的元素: ◦ 如果是0 的话， dest 往后移动两位； ◦ 否则， dest 往后移动⼀位。
• 判断dest 时候已经到结束位置，如果结束就终⽌循环；
• 如果没有结束， cur++ ，继续判断。
c. 判断dest 是否越界到n 的位置：
i. 如果越界，执⾏下⾯三步：
1. n - 1 位置的值修改成0 ；
2. cur 向移动⼀步；
3. dest 向前移动两步。
d. 从cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
i. 判断cur 位置的值：
1. 如果是0 ： dest 以及dest - 1 位置修改成0 ， dest -= 2 ；
2. 如果⾮零： dest 位置修改成0 ， dest -= 1 ；
ii. cur-- ，复写下⼀个位置。
C++算法代码：
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
//先找到最后一个数
int cur = 0, dest = -1;
while (cur < arr.size())
{
//当元素非0
if (arr[cur])
{
dest++;
}
else
{
dest += 2;
}
//当复写范围占满数组范围
if (dest >= arr.size() - 1)
{
break;
}
cur++;
}
//处理边界情况,超出范围一位，说明arr[cur]==0
if (dest == arr.size())
{
//将未超出范围的复写0初始化
arr[arr.size() - 1] = 0;
//将操作流程往前推一次，解决dest的越界
cur -= 1;
dest -= 2;
}
//从后往前完成复写操作
while (cur >= 0)
{
//当cur位置的数非零，则再dest处写入一次
if (arr[cur])
{
arr[dest--] = arr[cur--];
}
else //cur处为0时，再dest前一位和所在为都复写为0
{
arr[dest--] = arr[cur];
arr[dest--] = arr[cur];
cur--;
}
}
}
};Java算法代码：
class Solution
{
public void duplicateZeros(int[] arr)
{
int cur = 0, dest = -1, n = arr.length;
// 1. 先找到最后⼀个需要复写的数
while(cur < n)
{
if(arr[cur] == 0) dest += 2;
else dest += 1;
if(dest >= n - 1) break;
cur++;
}
// 2. 处理⼀下边界情况
if(dest == n)
{
arr[n - 1] = 0;
cur--; dest -= 2;
}
// 3. 从后向前完成复写操作
while(cur >= 0)
{
if(arr[cur] != 0) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
}