一.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--;}}}
};