专题一_双指针_复写零

 一：题目解析

总结：

①：遇见0 则写入两次 遇见非0 则只写入一次

②：数组就地操作(不能创建新数组)

③：不能越距写入元素

二：算法原理

这道题如果允许数组异地操作，那将毫无挑战性，直接一个指针进行判断第一个数组，一个指针进行写入第二个数组即可

但是现在只能就地，我们的双指针，不论是从左面向右面复写，还是从右面向左面复写，只要出现一个0，则会将下一个未判断的元素变成0，所以这是行不通的

但如果现在告诉你了最后一个判断复写的位置，那就简单多了！

例子：

我们知道在对原数组的4进行判断复写后，此时将4写入数组，就已经填满数组了，所以4就是最后一个判断复写的位置，那如果事先现在告诉你4的下标，我们就可以直接从4开始逐步向前判断，进行反向的复写即可：

那现在问题就转换为了如何找到最后一个判断复写的位置！

找到最后一个判断复写的位置：

依旧是双指针，但我们只判断然后移动双指针，而不进行数组值的修改，cur负责判断，dest模拟复写！所以我们cur为0 dest为-1 开始进行判断模拟 ，当cur的值为非0，则dest++，反之dest+=2，然后cur再++进行判断!

例子如下：

解释：最后cur成功停留在了我们最后一个复写的位置，且dest停留在了可以直接开始复写的位置

整个代码逻辑如下：

            while(1){if(arr[cur]!=0){dest++;}else{dest+=2;}if(dest>=n-1) {break;}cur++;}

解释：while直接给条件1，代表我们无论是什么情况，最后dest都会出现>=n-1的时候，像上一个例子，就是dest==n-1了，所以跳出循环，而我们的cur也来到了最后一个判断复写的位置

但是呢，也会有一种dest ==n再跳出循环的情况，且这个情况不能直接进行反向的复写，因为dest==n，则代表dest已经越距！此时需要额外处理一下，如数组[1,2,3,0]：

此时我们，不能直接进行反向判断复写，尽管cur已经停留在了正确的的位置上，因为dest已经越距了，会直接报错，所以针对这种原数组最后一个是0的情况，我们直接额外处理一下！

额外处理：

直接让arr[n-1]=0；cur--；dest-=2；也就是我们直接把cur指向的元素进行了判断复写，因为这种情况cur肯定指向0，且我们dest复写的时候，只能写入一个0，就无法写入了，所以我们只需将数组的最后一个元素变为0，然后cur--，dest-=2即可！

代码逻辑如下：

        //特殊情况的处理if(dest==n){arr[n-1] = 0;cur--;dest-=2;}

做出这一步额外处理之后，后面的就能进行常规的反向判断复写操作了！

Q：为什么一开始dest = -1，而不是和cur一样 = 0？

A：dest = -1 是为了从“虚拟位置 -1”开始计数，确保零的复写（+2）和非零的移动（+1）能正确映射到实际下标。例如：

解释：此时就出错了！ 

三：代码编写

1：可读性版本

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0;int dest = -1;int n = arr.size();//让cur值为最后一个判断复写的元素下标while(1){if(arr[cur]!=0){dest++;//走一步}else{dest+=2;//走两步}if(dest>=n-1) //先判断 为假 则代表复写已经结束 所以不用再cur++进行判断{break;}cur++;}//特殊情况的处理//最后一个复写判断元素为0的情况//会让dest==nif(dest==n){arr[n-1] = 0;cur--;dest-=2;}//开始从后面往前复写while(cur>=0){   //非0if(arr[cur]!=0){//则赋值后双双-1arr[dest] = arr[cur];cur--;dest--;}//为0else{//则dest连续向前写两个0//dest-=1 cur--arr[dest--] = 0;arr[dest--] = 0;cur--;}   } }
};

 

2：精简版本

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0,dest = -1,n = arr.size();while(1){if(arr[cur]!=0) dest++;else dest+=2;if(dest>=n-1) break;cur++;}if(dest==n){arr[n-1] = 0;cur--;dest-=2;}while(cur>=0){if(arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--]=0;arr[dest--]=0;cur--;}}  }
};

解释：只有一条语句的if 直接写在了if后面即可