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