【LeetCode刷题】：双指针篇（移动零、复写零）

一、移动零

1. 题目解析

题目：移动零【点击跳转题目】

大致题意就是将数组中所有为0的元素往后移，移到数组的末尾，但是所有的非零元素的顺序不能发生改变。例如：假设非零元素是1，2，3，4。那么移动完后的顺序依旧是1，2，3，4。

另外还有一个要求：那就是移动操作是要在原数组上进行操作，不能复制数组进行操作。

2. 算法原理

这种题目可以归为一类题：那就是 “数组划分/ 数组分块”，这类题就是给定一个数组，让我们按照某种要求或则特性对数组内的元素划分成几个区间。

对于这道题，就是将数组划分成两个区间，左边为非零元素，右边为零的元素。

解决这类题一般有一个经典的算法，那就是 《双指针算法》。这里的指针并非是真的指针，数组中我们通常使用下标来充当指针。

定义两个指针cur和dest：
cur：从左往右扫描数组，遍历数组。
dest：已处理的区间内，非零元素的最后一个位置。

所以只要cur遍历完数组后，就说明待处理的区间已经结束，而dest已经将数组划分为两个部分，一部分是非零元素，另一个区间的元素全是零，及完成题目要求。

第一步：定义两个 “指针” cur和dest。
因为dest是非零元素的最后一个位置，而在扫描前是没有非零元素的，所以最开始dest初始化为 -1，cur是遍历数组，所以要从数组的第一个元素开始，即初始化为 0。

第二步：cur遍历数组。cur遍历数组时会遇到两种情况：

• 第一种就是遇到零，不做处理，让cur继续加一。
• 第二种就是cur为非零元素，因为dest是指向最后一个非零元素，所以先让dest加一，再交换cur和dest下标对应的值，这样dest所指向的就一定是一个非零元素。

一直重复这个过程，等cur遍历完数组后，得到的数组即为题目要求的数组。

3. 代码编写

C语言代码：

void moveZeroes(int* nums, int numsSize) {int cur = 0, dest = -1;  // 定义双指针while(cur < numsSize){if(nums[cur] == 0)cur++;  // 遇到0，cur++else  // 遇到非0{++dest;int tmp = nums[dest];nums[dest] = nums[cur];nums[cur] = tmp;cur++;}}
}

C++代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); cur++)  // 定义双指针{if(nums[cur])  // 判断nums[cur]是否为0swap(nums[++dest], nums[cur]);  // 不为0先dest++， 在交换值}}
};

Python代码：

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""dest = -1  # 定义双指针for cur in range(0, len(nums)):if nums[cur]:  # 判断nums[cur]是否为0dest += 1  # 不为0，先让dest加1nums[dest], nums[cur] = nums[cur], nums[dest]  # 交换值

二、复写零

1. 题目解析

题目：复写零【点击跳转题目】

大致题意就是给定一个数组，将数组中为零的元素都复写一遍，复写后其他元素向右移。但是不能在超过数组长度的位置写入元素，切要在原数组上进行修改，不能拷贝数组进行操作。

例如：输入：arr = [1,0,2,3,0,4,5,0]，输出：[1,0,0,2,3,0,0,4]，解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]。

2. 算法原理

这个题可以先根据 “异地” 操作，然后优化成双指针的 “就地” 操作。怎么进行 “异地” 操作呢？
我们可以先开辟一个和数组arr一样大的空数组，然后用两个指针cur和dest，cur指向原数组arr的第一个元素，dest指向新开辟的数组的第一个位置，然后进行操作。当cur指向的值不为零时，将这个值拷贝给新数组，然后cur和dest都加一，当cur指向的值为零时，将零拷贝给新数组，然后dest加一，在写一个零，最后cur和dest都加一。一直重复这个操作，结束条件为dest大于或等于数组的大小。

可以看到，通过 “异地” 操作可以完成题意，接下来就是将 “异地” 操作优化为双指针的 “就地” 操作。
我们可以先试试将cur和dest都指向原数组的第一个元素，然后模拟 “异地” 操作。

模拟到这就没必要模拟了，因为后面的结果都是错的，之后cur会一直是0，因为dest将原本数组里的值覆盖成了0。从前往后不行的话就可以试试从后往前进行模拟。从后往前模拟我们只需要提前知道最后一个要复写的数是哪个就行了。

按照示例一：最后一个要复写的数是4，那就只需要将cur指向4，dest指向数组的最后一个元素，然后从后往前进行复写操作，cur的值不为0，将dest的值修改成cur的值，cur和dest都想前移动一位。cur的值为0，将dest的值修改为cur的值后，dest向前移动一位，然后再将dest指向的值修改为0，最后cur和dest向前移动一位。知道cur小于0结束。

我们发现 “从后往前” 复写是可以完成题目要求的，现在最后的问题是如何找到最后一个要复写的数。要找到最后一个要复写的数，我们也可以运用双指针来找。定义cur和dest两个 “指针”，cur指向数组的第一个位置，即初始化为0，dest指向第一个元素的前一个位置，即初始化为-1。然后当cur的值不为1时，dest向前前进一步，cur向前前进一步，当cur的值等于0时，cur前进一步，dest前进两步，当dest指向数组的最后一个元素时，cur指向的值就是最后一个要复写的元素。

注意：有些情况会导致dest越界，这种情况需要特殊处理。

因为要复写的最后一个数是0，所以只要数组越界，就只要将n - 1位置的数据修改成0（n为数组大小），然后cur减一，dest减二即可。
另外，在判断一个数是否是最后一个要复写的数的时候，一定要先判断dest是否是结束位置，不是结束位置cur才可以加一。

3. 代码编写

C语言代码：

void duplicateZeros(int* arr, int arrSize) {int cur = 0, dest = -1;  // 定义双指针while(cur < arrSize){if(arr[cur])  dest++;  // 不等于0else dest += 2;  // 等于0if(dest >= arrSize - 1)  break;  // 判断dest是否到结束位置cur++;}// 处理边界情况if(dest == arrSize){arr[arrSize - 1] = 0;cur--, dest -= 2;}// 从后往前进行复写while(cur >= 0){if(arr[cur])  // arr[cur]不等于0arr[dest--] = arr[cur--];else  // arr[cur]等于0{arr[dest--] = 0;arr[dest--] = 0;cur--;}}
}

C++代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1, n = arr.size();// 找到最后一个复写的数while (cur < n) {if (arr[cur])dest++;elsedest += 2;if (dest < n - 1)cur++;elsebreak;}// 处理边界情况if (dest == n) {arr[n - 1] = 0;cur--, dest -= 2;}// 从后向前进行复写while (cur >= 0) {if (arr[cur] != 0) {arr[dest] = arr[cur];cur--, dest--;} else {arr[dest] = 0;arr[--dest] = 0;cur--, dest--;}}}
};

Python代码：

class Solution:def duplicateZeros(self, arr: List[int], cur = 0, dest = -1) -> None:"""Do not return anything, modify arr in-place instead."""n = len(arr)# 找到最后一个要复写的数while cur < n:if arr[cur] != 0:dest += 1else:dest += 2if dest >= n - 1:breakcur += 1# 处理边界情况if dest == n:arr[n - 1] = 0dest -= 2cur -= 1# 从后往前复写while cur >= 0:if arr[cur] != 0:arr[dest] = arr[cur]dest -= 1cur -= 1else:arr[dest] = 0dest -= 1arr[dest] = 0dest -= 1cur -= 1