C++ 优先算法——复写零（双指针）

题目：复写零

1. 题目解析

2. 算法原理

一. 先找到最后一个“复写”数

处理边界情况

二. 复写操作

3. 代码实现

题目：复写零

1. 题目解析

题目截图：

该题目要求的与移动零相似，都要在一个数组上进行操作，它还要要求的是，这个数组长度大小不会被改变，在原有的数组上遇到0就复写一遍，遇到非零就不用复写。

这道题直接上来就在一个数组上考虑情况稍微会困难一些，可以假设让它可以开辟额外一个数组（两个数组）来考虑，最后在结合双指针到一个数组上会好解答。

题目大致情况双数组的话是上图所示，接下来转化到一个数组上双指针操作。

2. 算法原理

上述的介绍，这道题也是用双指针算法，不过这种双指针算法是先根据“异地“操作（也就是在额外开辟的数组操作），然后优化成双指针下的”就地“操作（在当前数组操作，不额外开辟数组）。

融入一个数组上就是：

但是这出现了一个问题，下面cur就指向0了，遇0是要复写一遍的（也就是要写两遍）

此时，就造成数据被覆盖导致丢失数据了，所以顺序遍历数组操作还是有问题的，要解决此问题，可以考虑尝试逆序操作。

然后按照上面逻辑，遇到0就抄写两遍，遇到非零直接抄写一遍即可，再统一向后移动1位。

这样可以避免出现顺序时候后面未被复写的数据被覆盖的情况了。

大致思路如上面图所示，归纳一下：

一. 先找到最后一个“复写”数

这个也要用双指针算法来去寻找它，我们把dest定义为最后需要复写的位置（结果中数组最后一个位置），因此刚开始时，并不知道最后位置在哪，让dest指向-1；cur的作用：从前往后遍历数组，决定dest走1步还是2步。所以可以仅需要判断dest是否走向最后位置来判断是否找到最后要复写的数。

// 先找到最后一个要复写的数
int dest = -1; // 复写位置
int cur = 0;   // 遍历数组
while (cur < arr.size()) {if (arr[cur] == 0) {  //遇到0，dest移动两位dest += 2;}else {++dest;}if (dest >= arr.size() - 1) {  //判断dest是否走向结尾break;}++cur;
}

处理边界情况

也就是说，因为遇到0，dest要加2，这样的话会导致上图情况。越界时，一定是cur等于0导致的，所以就可以单独处理它。

//单独处理边界情况--cur走到最后要复写的数为0,dest复写就导致越界访问的情况
if (dest == arr.size()) {arr[arr.size() - 1] = 0;--cur;dest -= 2;
}

总结：

先判断cur的值（是0或非0元素）
根据cur的值决定dest向后移动1步或2步。
先判断dest是否已经走到结束的位置
判断后，若没有结束，cur再向后移动1位

特殊情况，cur走到最后要复写的数为0，单独处理越界情况。

二. 复写操作

既然是逆序，那么就是要从后向前完成复写操作

注意：遇到0要多写一遍0

//从后向前复写while (dest >= 0) {if (arr[cur] == 0) {// 遇到0要记得复写两遍0arr[dest--] = 0;}arr[dest--] = arr[cur--];}

3. 代码实现

题目链接

class Solution {
public:void duplicateZeros(vector<int>& arr) {// 先找到最后一个要复写的数int dest = -1; // 复写位置int cur = 0;   // 遍历数组while (cur < arr.size()) {if (arr[cur] == 0) {dest += 2;} else {++dest;}if (dest >= arr.size() - 1) {break;}++cur;}// 从后往前复写// 还要单独处理边界情况--cur走到最后要复写的数为0,dest复写导致越界访问的情况if (dest == arr.size()) {arr[arr.size() - 1] = 0;--cur;dest -= 2;}while (dest >= 0) {if (arr[cur] == 0) {// 遇到0要记得复写两遍0arr[dest--] = 0;}arr[dest--] = arr[cur--];}}
};

提交记录：