优选算法——双指针专题 1.移动零 2.复写零
优选算法——双指针专题 1.移动零 2.复写零
一.移动零
[题目传送门](283. 移动零 - 力扣（LeetCode）)
1.题目描述
2.算法原理
数组划分 数组分块
什么意思呢？就是把数组按要求划分模块
比如这道题，就是把数组划分成两个模块，前边是非0，后边是0
两个指针dest cur 将数组划分为三部分
两指针作用:
cur:从左向右扫描数组，遍历数组,cur左边就是处理过的，右边就是未处理的
dest:已处理的区间内，最后一个非0的位置
从而可以分为三个区间
当cur到n时，最后一个区间不见了，只剩下前两个区间，并且前边是非0，后边是0
cur指向第一个元素。dest因为还没有确定最后一个非0元素的位置，所以先指向-1
cur移动时会遇见两种情况
1.遇到0时，cur++,从而保证[dest+1,cur-1]这个区间是0
代码就是cur++
2.遇到非0时，要让这个 值加入到第一个区间，也就是[0.dest]这个区间，所以要dest移动到下一个位置从而扩大这个区间，并且dest移动到0，再交换此时dest和cur的位置
代码就是
swap(dest+1,cur)
dest++,cur++
3.代码实现
classSolution{public:voidmoveZeroes(vector<int>& nums){for(int dest=-1,cur=0;cur<nums.size();cur++){//cur每轮都++,所以不用单独写cur遇到0的情况if(nums[cur])//遇到非0元素时swap(nums[++dest],nums[cur]);}}};二.复写零
[题目传送门](1089. 复写零 - 力扣（LeetCode）)
1.题目描述
2.算法原理
双指针法，先根据“异地”操作，然后优化到“就地”操作
问题难点：直接在原数组上操作会覆盖后续元素
解决方案：分两步操作
第一步：定位最后一个需要复写的元素
使用双指针模拟复写过程：
cur：遍历原数组dest：跟踪在新数组中的位置
特殊规则：
- 遇到非零元素：
dest移动1位 - 遇到零元素：
dest移动2位（因为零需要被复写）
当dest达到或超过数组末尾时，停止遍历，此时的cur就是最后一个需要复写的元素。
第二步：从后向前复写
从cur位置开始向前遍历：
- 遇到非零元素：直接复制到
dest位置 - 遇到零元素：在
dest位置写入两个零
边界情况处理：
如果最后一个零恰好使dest超出数组边界，需要特殊处理：
- 在数组末尾写入一个零
- 将
cur和dest指针相应调整
3.代码实现
classSolution{public:voidduplicateZeros(vector<int>& arr){int cur=0,dest=-1,n=arr.size();//1.找最后一个数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--;}}}};
