双指针算法初阶详解：移动零与复写零

复写零

题目描述

给你一个长度固定的整数数组 arr，将该数组中出现的每个零都复写一遍，并将其余元素向右平移。注意不要超过该数组长度的位置写入元素。请就地修改，不返回任何东西。

示例 1:

cpp
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]

示例 2:

cpp
输入：arr = [1,2,3]
输出：[1,2,3]

提示:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

实现思路

需要判断特殊情况，找到复写后数组的最后一个元素复写前的下标。

1. 使用双指针遍历，确定最后一个可复写的值的位置。
2. 根据是否越界决定是从前往后还是从后往前填充。
3. 从后往前遍历数组进行复写操作，遇到零则写入两个零。

实现代码:

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, s = arr.size();
        while (cur < s) {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= s - 1) break;
            cur++;
        }
        if (dest == s) {
            arr[s - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0) {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};