【算法|双指针系列No.2】leetcode1089. 复写零-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法|双指针系列No.2】leetcode1089. 复写零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人主页：平行线也会相交
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由平行线也会相交原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

示例一：

输入：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]

示例二：

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

2️⃣算法分析

解题思路：

1.先找到最后一个复写的数
以[1,0,2,3,0,4,5,0]为例进行演示：
寻找最后一个复写的数依然是使用的双指针算法，具体步骤如下：

1.先判断cur的值，
2.根据cur的值来判断dest向后移动一步或者两步
3.判断dest是否到结束位置
4.cur++
此过程结束后cur指的值就是最后一个要复写的数，而dest指向的就是倒数第一个位置（这里先不考虑边界情况）

第一步结束之后结果如下图所示：
【算法|双指针系列No.2】leetcode1089. 复写零,LeetCode,手撕算法系列专栏,算法,c++

2.处理边界情况

这里有一个特殊例子，即[1,0,2,3,0,4]，请看：
【算法|双指针系列No.2】leetcode1089. 复写零,LeetCode,手撕算法系列专栏,算法,c++

我们会发现如果不考虑边界问题的话，很有可能导致dest越界。所以我们需要对边界问题进行特殊处理。
之所以会越界就是因为上图红色标记的位置是0导致的。

处理边界代码如下：

 if(dest == n)
{
    arr[n-1] = 0;
    cur--;dest -= 2;
}

3.从后往前进行复写
之所以从后往前进行复写是因为如果从前往后复写的话会覆盖后面的数据。因此这里需要从后往前进行复写。

3️⃣代码编写

整个代码编写如下：

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