给你一个长度固定的整数数组 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
解题思路一：暴力破解
这里的暴力破解，其实也是算双指针做法，但是因为我们没有很好的利用双指针的特性，就会变成暴力破解的方式，但是这是一种比较好想到的解法，虽说时间复杂度达到了 O(n^2) 哈哈，这里看个意思就行！
其实就是我们去从头遍历数组的时候，一遇到了零，就在数组末尾从后往前将元素往后移动一位，所以时间复杂度才很高！
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0;
while(cur < arr.size())
{
int dest = arr.size() - 2;
if(arr[cur] == 0)
{
// 遇到0就让dest从后往前将元素后移
while(dest >= cur)
{
arr[dest + 1] = arr[dest];
dest--;
}
cur += 2;
}
else
cur++;
}
}
};💥解题思路二：双指针
算法思路
其实上面这种解法之所以变成了暴力破解，其实是因为我们没办法做到一次性的去往后移动那些元素，如果遇到比较棘手的样例比如说全0，那么时间复杂度是非常高的！
但是上面的思想，也就是从后往前复写是正确的，如果我们是从前往后复写的话，那么就会导致后面元素先被覆盖就不见了！
所以我们最后还是得从后往前去遍历，也就是说我们要想办法在从后往前复写元素的时候，能一步到位！
如上图所示，其实我们只需要找到最后一个复写的数也就是上面的 4 的位置，然后再用另一个指针指向最后一个元素 0，此时直接复写，就能一次到位啦！所以我们的算法过程分为以下两步：
- 先找到最后一个复写的数
- 然后从后往前进行复写操作
算法流程
- 初始化两个指针
cur = 0，dest = -1 - 找最后一个复写的数
- 若
arr[cur] != 0，则说明不需要复写，此时cur++，dest++即可！ - 若
arr[cur] == 0，说明该位置需要复写，此时要让dest += 2，而cur++即可！ - 重复上述判断直到
dest遍历结束为止！
- 若
- 此时不能直接复写，因为
dest有可能不在数组内，需要做些处理：- 如下图所示的情况，其实就是因为
dest还差一步就结束了，而此时cur刚刚好遇到的是0，此时dest多走了一步，就出界了！
- 处理很简单，首先判断
dest是否出界- 如果出界了，则让
arr[n - 1] = 0，然后让dest -= 2，让cur--即可！ - 因为此时会出界只可能是因为遇到
0了，所以就说明n-1位置是要被复写的，而由因为后面我们的复写操作就是将arr[cur]赋值给arr[dest]，又因为是arr[cur]为0导致出界的，所以直接将arr[n - 1] 置为0即可！
- 如果出界了，则让
- 如下图所示的情况，其实就是因为
- 从后往前进行复写操作
- 若
arr[cur] == 0，则说明要复写，将arr[dest]以及arr[dest - 1]置为0，然后dest -= 2 - 若
arr[cur] != 0，则说明不需要复写，只需要让arr[dest]修改为arr[cur]，然后dest--即可！ - 而对于
cur来说，一直cur--即可！
- 若
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1;
// 找到最后一个复写的数字
while(cur < arr.size())
{
if(arr[cur] == 0)
dest += 2;
else
dest++;
if(dest >= arr.size() - 1) // 如果到达数组末尾或者出界则break
break;
cur++;
}
// 对dest出界情况进行处理
if(dest == arr.size())
{
arr[arr.size() - 1] = 0;
cur--;
dest -= 2;
}
// 从后往前复写
while(cur >= 0)
{
if(arr[cur] == 0)
{
arr[dest] = arr[dest - 1] = 0;
dest -= 2;
}
else
{
arr[dest--] = arr[cur];
}
cur--;
}
}
};