LeetCode —— 复写零(双指针)-Toy模板网

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

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

LeetCode —— 复写零(双指针),算法练习,leetcode,算法

题目解析

将数组中出现的每个零复写一遍，然后将其他元素向右平移，数组长度不能改变。

法一：使用额外空间的做法

LeetCode —— 复写零(双指针),算法练习,leetcode,算法

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 定义一个额外的vector
        vector<int> v;
        // 遍历数组
        for(auto&e:arr)
        {
            // 如果该元素不为0，则向新数组中插入一个该元素
            if(e) v.push_back(e);
            // 如果该元素为0，则向新数组中插入两个该元素
            else
            {
                v.push_back(0);
                v.push_back(0);
            }
        }
        // 改变新数组的大小为老数组大小
        v.resize(arr.size());
        // 将老数组赋值给新数组
        arr=v;
    }
};

法二：原地修改的做法

LeetCode —— 复写零(双指针),算法练习,leetcode,算法

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int n=arr.size();
        int cur=0,dest=-1;
        // 找最后一个复写的元素
        while(cur<n)
        {
            if(arr[cur]==0) dest+=2;
            else dest++;
            if(dest>=n-1) break;
            cur++;
        }
        // 处理边界情况
        if(dest==n)
        {
            arr[n-1]=0;
            cur--;
            dest-=2;
        }
        // 覆盖
        while(cur>=0)
        {
            if(arr[cur]==0)
            {
                arr[dest--]=arr[cur];
                arr[dest--]=arr[cur--];
            }
            else
            {
                arr[dest--]=arr[cur--];
            }
        }
    }
};

文章来源地址https://www.toymoban.com/news/detail-696079.html

到了这里，关于LeetCode —— 复写零(双指针)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！