优先算法 —— 双指针系列 - 复写零

目录

1. 复写零

2. 算法原理

一般情况下

改为就地操作：从左到右（错误）

从右到左

总结一下解决方法：

如何找到最后一个复写的数

特殊情况

 完整步骤：

3. 代码

---

1. 复写零

题目链接：
1089. 复写零 - 力扣（LeetCode）https://leetcode.cn/problems/duplicate-zeros/description/

 

---

2. 算法原理

其实本题严格来说是一题半模拟半双指针的题目

一般情况下

我们可以先进行异地操作，然后再优化成为双指针下的就地操作

   

当Cur遇到非0元素的时候，直接写下来，当遇到0的时候，就需要写两遍.....

   

  

改为就地操作：从左到右（错误）

  

将两个指针定义到一个数组上

  

  

但是我们发现：当cur到达第一个0时，dest执行两次写入0，将原本2的值给覆盖掉了，那么整个数组都会出现错误，所以从左到右这个方法是不可以的

从右到左

那我们来试试从右到左能否成功

  

因为是从右到左，所以我们将dest指向最后一个数，cur指向最后一个复写的数，以示例1为例，就是指向4

  

如果cur当前指向的值不为0，那么就直接把cur指向的值写入dest，再同时--

    

如果cur当前指向的值为0，那么cur往左移动一位，dest移动2位

    

  

  

然后我们发现从右到左这种方法是可以的  

总结一下解决方法：

  

1. 先找到最后一个复写的数

  

2. 以从右到左的顺序完成复写操作

如何找到最后一个复写的数

   

双指针算法

  

1. 定义一个cur指向数组里第一个数的位置，dest指向-1的位置

   

因为要把dest定义为结果中最后一个的位置，因此我们只需要判断dest是否跑到最后一个位置就可以了

  

然后按照下面的步骤来重复进行： 

  

然后就找到最后一个复写的数了

  

特殊情况

当查找最后一个复写的数时cur为0时，我们会发现会出现访问越界的问题，会造成内存泄漏的情况

  

  

解决方法也很简单：我们直接将4这个位置也就是n-1变为0，然后再进行cur--，dest-=2

   

 完整步骤：

  

1. 先找到最后一个复写的数

  

2. 处理特殊情况  

3. 以从右到左的顺序完成复写操作

---

3. 代码

class Solution {
public:void duplicateZeros(vector<int>& arr) {//1. 先找到最后一个复写的数int cur=0,dest=-1,n=arr.size();while(cur<n){//先判断cur位置的值//不为0dest往后移动1步，为0移动2步if(arr[cur]) dest++;else dest+=2;//判断一下dest是否已经到达结束位置if(dest>=n-1) break;//n为size，在数组最后一个位置的下一个位置//cur++cur++;}    //2. 处理特殊情况 //如果dest越界if(dest==n){arr[n-1]=0;cur--;dest-=2;}//3. 以从右到左的顺序完成复写操作while(cur>=0){//如果cur当前指向的值不为0，那么就直接把cur指向的值写入dest，再同时--if(arr[cur]) arr[dest--]=arr[cur--];else{//为0要写2遍//然后cur往左移动一位，dest移动2位arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

---

未完待续~