2024年10月25日练习（双指针算法）
一.283. 移动零 - 力扣（LeetCode）
1.题目描述：
这里题目要求了说必须在不复制数组的情况下对数组进行原地操作，所以说不能来用暴力的解法来
实现。
2.算法原理：
这个题目就是经典的数组划分，数组分块问题，就是将数组划成两个部分，拿这个题目来说，一
个划成非0元素部分，一个划分成0元素的部分。
这里虽然叫双指针算法，但是这里在数组里，所以我们用数组下标代表这“双指针”，而不是真的去
创建两个指针。
这里我们来演示一下这两个指针在走的过程中是怎么划分数组的：
这里两个指针将整个数组划分为三个区间，那么这两个指针代表的是什么呢？
首先cur指针代表的是从左往右扫描数组，也就是遍历数组的作用。
dest指针代表的是已处理区间，非零元素的最后一个位置。
因为这两个指针走的时候肯定是错开走的，所以会划分成三个不同的区间：
在处理过的区间题目的要求是，非0元素全部在右边，0元素全部在左边，然后dest这个指针的作用
就非常明显了，这个处理过的区间又细分为非0元素区间和0元素区间。
这就是划分出来的三个区间。
当cur指针走到最后时：
这时候你再看，待处理区间已经没有了，就剩下dest指针划分出来的两个区间了，也就是非0元素
区间和0元素的区间，这时也就完成了题目的要求，完成了数组的划分。
那么现在就拿一个例子来看看：
上面也已经说过了cur指针和dest的指针的作用是什么，这里dest指的是非0元素的最后一个位置，
所以有可能像上面这种情况首元素就是非0元素，所以dest所在的位置就是数组下标为-1的位置即
可。
那么遍历的过程是如何的呢？
这里就一直遵循这三个区间即可，一直保持着这三个区间走就行：
首先遇到0，cur++即可，dest不动。现在cur指针指向1：
因为遇到了非0元素，所以先让dest+1，然后再与cur去交换，完成后，cur再++，上面就是完成该
操作的情况，此时再看也是遵循那个三个区间的要求。
这里cur指针又指向了0，所以只有cur++即可：
这里cur又碰到了非0元素，所以先让dest+1，再与cur指针指向的值完成交换，完成交换cur再++：
然后cur又碰到了非0元素，所以继续上述步骤，dest+1，然后与cur交换，cur再++：
此时再看，cur也已经完成了遍历数组的任务，此时dest正好将数组划分为两个区间，左边非0元素
区间，右边0元素的区间。
这就是这个题目的整个算法原理。
3.代码实现：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur=0;
int dest=-1;
for(cur=0;cur<nums.size();cur++){
if(nums[cur]!=0){//处理非0元素
swap(nums[++dest],nums[cur]);
}
}
}
};这就是利用双指针算法解决这个问题的所有思路。
二.1089. 复写零 - 力扣（LeetCode）
1.题目描述：
这道题也是原地操作，并且不能越界
2.算法原理：
这里的解法还是双指针算法，这里题目让我们的是就地操作，而双指针算法的情况下我们先“异
地”操作，然后优化成双指针下的“就地”操作，这里随便拿一个题目中的例子来分析一下：
这里cur就指向原数组来遍历一下，然后dest指向另一数组，如果cur遇到的是非0元素，就复制到
dest指向的位置，如果cur遇到的是0元素，就复写两次到dest的数组中。
第一次cur指向的元素是1，所以dest直接复制下来，然后cur，dest都加加，现在，cur指向的元素
是0，所以dest复写两次：
复写完成后cur++，dest++，然后再次去判断cur指向的是非0元素，先复制，再cur++，dest++：
然后继续上述操作：
此时cur又遇到了0元素，dest继续复写，复写完成后，dest++，cur++：
此时又是非0元素，直接复制，然后cur++，dest++：
此时dest越界，此时也完成了，题目要求的复写任务。
这是异地操作，那我们能否改为就地操作：
这里我们直接将cur，dest指向同一数组，然后来操作一下我们上面写的复写过程：
此时遇到的是非0元素，所以直接让cur++，dest++：
此时cur遇到了0元素，此时就要复写了，那么dest+1，然后复写0：
此时已经出错了，因为原来位置的值是2，而这里已经被覆盖了，所以这个肯定不对了。
而我们这里既然从前往后会导致数据覆盖，那么我们就换一种思路，我们就从后向前走，看看能不
能解决覆盖问题：
这里dest指向数组最后一个元素的位置，然后cur指向最后一个复写的数，上面的操作我们知道
了，最后一个复写的数是4，所以这里我们直接指向4，如果cur和dest指向同一位置，是肯定不行
的，然后此时来从后向前来完成复写操作：
此时cur指向的是4，那么直接复制给dest指向的位置，然后cur--，dest--：
此时遇到0，那么dest直接往前复写两个0，然后dest--，cur--：
此时cur遇到非0元素，那么直接复制给dest，然后dest--，cur--：
此时cur又遇到非0元素，继续复制给dest，然后dest--，cur--：
我们之所以可以直接修改，因为我们发现这里3已经被复写过了，就不会发生覆盖了，所以可以直
接复写就行了。
这里cur遇到了0元素，那么dest复写两次，然后cur--，dest--：
，这是cur遇到了非零元素，直接复制就好了，然后dest--，cur--：
此时这时就完成了复写操作，比较一下，复写的没毛病，所以双指针从后向前走就可以完成这个操
作。
总结一下：1.首先cur指向的是最后一个复写的数，因为上面我们可以很直观的看到最后一个复写
的数，所以我们在这里首先要找到最后一个需要复写的数。
2.我们要从后向前完成复写操作。
那么第一步我们怎么找到最后一个复写的数呢？
其实还是一个双指针算法，定义一个cur指针指向数组头元素，然后dest指针指向-1的位置：
cur的作用还是遍历数组，而dest的定义是最后一个需要复写的位置，因为一开始我们并不知道，
最后一个需要复写的位置在哪里，所以我们先定义到-1这个位置。
首先先判断cur指向的元素是否为非0元素，如果不是dest走一步，然后再判断dest是否走到了最
后。如果是非0元素，dest就走两步，因为要复写0，然后再判断dest'是否走到了最后。这就是
判断的顺序。
现在cur位置的值是非零元素，所以dest向后走一步，dest并没有到结束位置，然后cur++：
此时cur指向的是0元素，所以dest向后移动两步，dest并没有结束，所以cur++：
此时cur指向非0元素的值，所以dest向后移动一步，dest并没有结束，所以cur++：
跟上面遇到2的情况一样，继续：
此时cur遇到了0，那么dest就走两步，此时dest还没有到结束的位置，所以cur++：
此时cur指向的是非零元素，所以dest向后移动一步，移动一步之后，我们发现已经到了数组的末
尾所以终止接下来的操作，所以cur不加加：
此时我们发现cur正好是指向我们最后一个复写的数，而且此时dest正好是我们要从后向前完成复
写操作的位置，所以后续可以直接开始就行了。
但是还有特殊情况：
就是这个例子，当我们去找最后一个复写的数时，就是按照上面的思路去走，这里就不详细写了，
直接快进到最后的位置：
此时我们发现，dest直接越界了，如果我们此时按照这个位置直接去完成从前向后复写的操作，编
译器是会直接报错的：
所以我们要处理一下边界情况，这里dest出边界一定是复写的最后一个数是0导致的，所以我们要
单独处理一下这种情况：
因为最后一个复写的数是0，所以我们直接将n-1的位置改为0，然后让dest向前移动两步，dest向
前移动一步，此时再从后向前完成复写就不会出错了：
这就是处理后的位置。
总结一下整个算法原理我们在做什么：
3.代码实现：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0;
int dest=-1;
//先找到最后一个复写的数
int num=arr.size();
while(cur<num){
if(arr[cur]!=0){
dest++;
}else{
dest+=2;
}
if(dest>=num-1){
break;
}
cur++;
}
//处理边界情况
if(dest==num){
arr[num-1]=0;
dest-=2;
cur--;
}
//从后向前完成复写操作：
while(cur>=0){
if(arr[cur]!=0){
arr[dest--]=arr[cur--];
}else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};