双指针算法实战：移动零与复写零详解

02. 复写零

这道题要求将数组中的每个 0 都复写一遍，后面的元素向后移动。如果从前往后操作，后面的数据会被覆盖，因此我们需要更巧妙的策略。

1089. 复写零 - 力扣（LeetCode）

题目描述

在一个固定的长度数组中，将每个出现的 0 重复复制一份，后续元素向右移动。超出原数组长度的元素将被丢弃。

算法思路

由于是原地修改且不能覆盖未处理的数据，最佳策略是先计算边界，再从后往前填充。

1. 确定边界：先遍历一遍数组，模拟扩展示意过程，找到最后一个需要被写入的位置 dest。
2. 倒序填充：从后往前遍历，如果是 0 则写入两次，否则写入一次。

算法流程

1. 初始化 cur = 0, dest = -1，获取数组长度 n。
2. 寻找边界：
   • 若 arr[cur] 为 0，dest 增加 2；否则 dest 增加 1。
   • 当 dest >= n - 1 时停止，说明已经找到了最后一个有效写入位置。
3. 处理越界情况：
   • 如果 dest >= n，说明最后一个 0 被截断了，需要将数组最后一位设为 0，并调整指针回退。
4. 倒序复写：
   • 从 cur 向前遍历，判断当前值。如果是 0，在 dest 和 dest-1 处写入 0；否则在 dest 处写入原值。

C++ 代码演示

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        
        // 第一步：找到最后一个复写的数
        while (cur < n) {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        
        // 第二步：处理可能的越界情况
        if (dest >= n) {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }
        
        // 第三步：从后往前进行复写
        while (cur >= 0) {
            if (arr[cur]) {
                arr[dest--] = arr[cur];
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }
};