Ciallo～(∠・ω< )⌒☆ ~ 今天，我将和大家一起做一道双指针算法题--复写零~
目录
一 题目
二 算法解析
2.1 算法思路
2.2 算法流程
三 编写算法
一 题目
1089. 复写零 - 力扣（LeetCode）
二 算法解析
2.1 算法思路
此题依旧使用双指针算法，先根据异地操作，优化成双指针就地操作。
如果从前向后进⾏原地复写操作，由于 0 会复写两次，导致没有复写的数被覆盖。
因此我们选择从后往前的复写策略。但是从后向前复写的时候，我们需要找到最后⼀个复写的数，因此我们的⼤体流程分两步：
- 先找到最后⼀个复写的数。
- 从后向前进⾏复写操作。
2.2 算法流程
0.初始化
- cur = 0, dest = -1
1. 找到最后⼀个复写的数（也使用双指针算法）
- 判断cur位置的值是否==0
- ==0 dest指针向后走两步，!=0 dest指针向后走一步
- 判断dest是否到末位置
- cur++
1.5. 判断dest是否会越界
- n-1 位置赋为0
- cur -= 1 dest -= 2
2. 从后往前，完成复写操作
（i）判断 cur 位置的值：
- 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；
- 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；
（ii）cur-- ，复写下⼀个位置。
三 编写算法
class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1, n = arr.size();// 找到最后⼀个复写的数while(cur < n){if(arr[cur] == 0)dest += 2;elsedest++;if(dest >= n - 1)break;cur++;}// 判断dest边界情况if(dest == n){arr[n-1] = 0;cur--;dest -= 2;}// 从后往前，完成复写操作while(cur >= 0){if(arr[cur] == 0){arr[dest] = 0;arr[--dest] = 0;dest--;cur--;}else{arr[dest] = arr[cur];dest--;cur--;}}}
};精简版~：
class Solution
{
public:void duplicateZeros(vector<int>& arr){// 1. 先找到最后⼀个数int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur]) dest++;else dest += 2;if (dest >= n - 1) break;cur++;}// 2. 处理⼀下边界情况if (dest == n){arr[n - 1] = 0;cur--; dest -= 2;}// 3. 从后向前完成复写操作while (cur >= 0){if (arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};