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

C++ 代码演示：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        while(cur != nums.size()) {
            if(nums[cur]){
                swap(nums[++dest], nums[cur]);
            }
            cur++;
        }
    }
};

算法总结：

这里用到的方法就是我们在数据结构中学习快排算法的时候，数据划分过程的重要一步。如果将快排算法的递归拆解成单趟的话，这一小段代码就是实现快排单趟的核心步骤。

02、复写零

题目链接：

1089. 复写零 - 力扣（LeetCode）

题目描述：

题目示例：

解法：（原地复写——双指针）

算法思路：

• 如果【从前往后】进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数【被覆盖掉】。因此我们选择【从后往前】的复写策略。
• 但是【从后往前】复写的时候，我们需要找到【最后一个复写的数】，因此我们的大体流程分两步：1.先找到最后一个复写的数；2.然后从后往前进行复写操作

算法流程：

1. 初始化两个指针 cur = 0，dest = -1；
2. 找到最后一个复写的数：
   • 判断 cur 位置的元素：（1）如果是 0 的话，dest 往后移动两位；（2）否则，dest 往后移动一位
   • 判断 dest 这时候是否已经到结束位置，如果结束就终止循环；
   • 如果没有结束，cur++，继续判断。
3. 判断 dest 是否越界到 n 的位置： 如果越界，执行下面三步：
   • n-1 位置的值修改成 0；
   • cur 向前移动一步（cur--）；
   • dest 向前移动两步（dest -= 2）；
4. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组： 4.1 判断 cur 位置的值：
   • 如果是 0：dest 以及 dest-1 位置修改成 0，dest-=2；
   • 如果非零：dest 位置修改成 0，dest -= 1； 4.2 cur--，复写下一个位置。

C++ 代码演示：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1. 先找到最后一个复写的数
        int dest = -1;
        int cur = 0;
        while(1) {
            dest++;
            if(arr[cur] == 0) {
                dest++;
            }
            if(dest >= arr.size() - 1) {
                break;
            }
            cur++;
        }
        // 2. 处理越界情况
        if(dest == arr.size()) {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        } //之所以会越界是因为如果最后一个复写的数为 0
        //则可能出现复写的位置在下标 n-1 和 n，但下标为 n 就是越界
        //也就是说实际上并没有复写两遍 0 而只是数组最后一个位置复写为 0
        //所以如果越界操作就是数组最后位置手动置为 0 后让 dest 回到倒数第二个位置
        //cur--就是让最后一个复写的数变成前一个
        // 3. 从后向前完成复写操作
        while(cur >= 0) {
            if(arr[cur] == 0) {
                arr[dest--] = arr[cur];
            }
            arr[dest--] = arr[cur--];
        }
    }
};

算法总结及流程解析：