【优选算法必刷100题】第001~002题（双指针算法）：移动零、复写零问题求解
🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题、洛谷刷题、C/C++基础知识知识强化补充、C/C++干货分享&学习过程记录、测试开发要点全知道、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
🍉学习方向：C/C++方向学习者
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
目录
001 移动零
力扣链接：283. 移动零
力扣题解链接：双指针求解【移动零】问题
题目描述：
1.1 思路
双指针算法——
创建两个数组，cur和dest——
cur：从左往右扫描数组，遍历数组
dest：已处理的区间内，非零元素的最后一个位置
cur往后遍历数组的过程中：
1、遇到0元素：cur++;
2、遇到非零元素：swap(nums[dest+1],nums[cur])，然后dest++,cur++。
也就是说——
算法思路：
在本题中，我们可以用一个cur指针来扫描整个数组，另一个dest指针用来记录非零数序列的最后一个位置。根据cur在扫描过程中遇到的不同的情况，分类处理，实现数组的划分。
在cur遍历期间，使得[0 , dest]的元素全部都是非零元素，[dest + 1 , cur - 1]的元素都是零。
1.2 算法流程
1.2.1
初始化cur = 0（用来遍历数组），dest = -1（指向非零元素序列的最后一个位置。因为刚开始我们也不知道最后一个非零元素到底在什么位置，因此初始化为-1）
1.2.2
cur依次往后遍历每个元素，遍历到的元素会有下面两种情况：
1、遇到的元素都是0，cur直接++。因为我们的目标是让[dest + 1 , cur - 1]内的元素全都是零，因此当cur遇到0的时候，直接++，就可以让0在cur - 1的位置上，从而在[dest + 1 , cur - 1]内；
2、遇到的元素不是0，dest++，并且交换cur位置和dest位置的元素（swap），之后让cur++，扫描下一个元素。
（1）因为dest指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么它的位置就应该在dest + 1的位置上，因此dest先自增1；
（2）dest++之后，指向的元素就是0元素（因为非零元素区间末尾的后一个元素就是0），因此可以交换到cur所处的位置上，实现[0 , dest]的元素全部都是非零元素，[dest + 1 , cur - 1]的元素都是零。
1.3 代码实现
代码演示：
class Solution { public: void moveZeroes(vector<int>& nums) { for(int dest = -1,cur = 0;cur < nums.size();cur++) { if(nums[cur]) swap(nums[++dest],nums[cur]); } } };时间复杂度：O(N)，空间复杂度：O(1)。
1.4 过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！
002 复写零
力扣链接：1089. 复写零
力扣题解链接：双指针算法解决【复写零】问题
题目描述：
2.1 思路
双指针算法——
先根据“异地”操作，然后优化成双指针下的“就地”操作。
1、先找到最后一个“复写”的数： 双指针算法——
（1）先判断cur位置的值；
（2）决定dest向后走一步还是两步；
（3）判断一下dest是否已经到结束位置；
（4）cur++。
2、处理一下边界情况——
到达n-1位置，cur--，dest -= 2，复写两次0。
3、“从后往前”完成复写操作。
也就是说——
如果“从前向后”进行原地复写操作的话，由于0的出现会复写两次，导致没有复写的数会被覆盖掉。因此我们选择“从后往前”的复写策略。
但是我们选择“从后往前”的复写的时候，需要找到“最后一个复写的数”，因此我们的大体流程分两步：（1）先找到最后一个复写的数；（2）然后从后往前进行复写操作。
2.2 算法流程
2.2.1
初始化两个指针cur = 0，dest = 0；
2.2.2
找到最后一个复写的数：
1、当cur < n的时候，一直执行下面循环：
（1）判断cur位置的元素：
1）如果是0的话，dest就往后移动两位；
2）否则，dest往后移动一位。
2.2.3
判断dest是否越界到n的位置：
1、如果越界，执行以下三步：
（1）n - 1位置的值修改成0；
（2）cur向前移动一步；
（3）dest向前移动两步。
2.2.4
从cur位置开始往前遍历原数组，依次还原出复写后的结果数组：
1、判断cur位置的值：
（1）如果是0：dest以及dest - 1位置修改成0，dest -= 2；
（2）如果非零：dest位置修改成0，dest -= 1；
2、cur--，复写下一个位置。
2.3 代码实现
代码演示：
class Solution { public: void duplicateZeros(vector<int>& arr) { //1、先找到最后一个数 int cur = 0,dest = -1,n = arr.size(); while(cur < n) { if(arr[cur]) { dest++; } else { dest += 2; } if(dest >= n - 1) break; cur++; } //2、处理边界问题 if(dest == n) { arr[n -1] = 0; cur--; dest -= 2; } //3、从后往前完成复写操作 while(cur >= 0) { if(arr[cur]) arr[dest--] = arr[cur--]; else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };时间复杂度：O(N)，空间复杂度：O(1)。
2.4 过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！
结尾
结语：本文内容到这里就结束了，大家不要忘记给博主“一键四连”哦！
