(C++)复写零--双指针法

简介: (C++)复写零--双指针法

个人主页:Lei宝啊

愿所有美好如期而遇


算法原理

双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针,这道题目我们仍然定义cur以及dest,当我们将cur和dest都定义在数组开始时,按照逻辑执行下去,那么遇到0时,后面的部分值会被覆盖,所以我们不能从左向右走,而是从右向左走,但是这样的话我们又怎么知道cur和dest的位置呢?我们看图示

图示

正常从左向右走,图示:

2就被覆盖了,但是我们先走下去(不考虑覆盖),看看cur和dest的最终位置:

当dest到达右边界时停止。

也就是说,我们可以先遍历找到指针位置,再倒过来复写,图示:

我们还有一种特殊情况,就是dest越过边界,到了size,那么我们就要先将数组下标为size-1的位置置0,因为size位置不能置0,是越界的,然后我们dest -= 2,cur--,接下来正常走就好。

代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        while(cur < n)
        {
            if(arr[cur] != 0)
            {
                dest++;
            }
            else
            {
                dest += 2;
            }           
            if(dest >= n - 1)
            {
                break;
            }
            cur++;
        }
        if(dest > n - 1)
        {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }
        while(cur >= 0)
        {        
            if(arr[cur] != 0)
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }             
        }     
    }
};


目录
相关文章
|
11月前
|
人工智能 弹性计算 Serverless
触手可及,函数计算玩转 AI 大模型 | 简单几步,轻松实现AI绘图
本文介绍了零售业中“人—货—场”三要素的变化,指出传统营销方式已难以吸引消费者。现代消费者更注重个性化体验,因此需要提供超出预期的内容。文章还介绍了阿里云基于函数计算的AI大模型,特别是Stable Diffusion WebUI,帮助非专业人士轻松制作高质量的促销海报。通过详细的部署步骤和实践经验,展示了该方案在实际生产环境中的应用价值。
321 6
触手可及,函数计算玩转 AI 大模型 | 简单几步,轻松实现AI绘图
|
移动开发 应用服务中间件 Android开发
踩坑记录:请求接口status返回0
踩坑记录:请求接口status返回0
踩坑记录:请求接口status返回0
|
12月前
|
容器
【LVGL快速入门】LVGL开源框架入门教程之框架使用(二)
【LVGL快速入门】LVGL开源框架入门教程之框架使用(二)
674 1
|
Java Serverless 应用服务中间件
Serverless 应用引擎操作报错合集之部署python项目时,构建过程报错,怎么解决
Serverless 应用引擎(SAE)是阿里云提供的Serverless PaaS平台,支持Spring Cloud、Dubbo、HSF等主流微服务框架,简化应用的部署、运维和弹性伸缩。在使用SAE过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
130 5
DeprecationWarning:current URL string parser is deprecated, and will be removed in a future version.
DeprecationWarning:current URL string parser is deprecated, and will be removed in a future version.
|
Python
python如何安装numpy模块?
python安装numpy模块 python numpy安装思路 第一次安装时的思路 第一次安装时遇到的坑 第二次安装的思路(快速安装避免踩坑)
752 0
python如何安装numpy模块?
|
Java 数据库
详述 PO VO BO DTO DAO 和 POJO 的概念及区别
详述 PO VO BO DTO DAO 和 POJO 的概念及区别
320 0
|
前端开发 Java API
详解Spring Framework提供的扩展点:ApplicationContextInitializer应用上下文初始化器,以及它在SpringBoot中的应用【享学Spring】(上)
详解Spring Framework提供的扩展点:ApplicationContextInitializer应用上下文初始化器,以及它在SpringBoot中的应用【享学Spring】(上)
详解Spring Framework提供的扩展点:ApplicationContextInitializer应用上下文初始化器,以及它在SpringBoot中的应用【享学Spring】(上)
|
SQL 数据采集 自然语言处理
Lucene就是这么简单(一)
Lucene是apache软件基金会发布的一个开放源代码的全文检索引擎工具包,由资深全文检索专家Doug Cutting所撰写,它是一个全文检索引擎的架构,提供了完整的创建索引和查询索引,以及部分文本分析的引擎,Lucene的目的是为软件开发人员提供一个简单易用的工具包,以方便在目标系统中实现全文检索的功能,或者是以此为基础建立起完整的全文检索引擎,Lucene在全文检索领域是一个经典的祖先,现在很多检索引擎都是在其基础上创建的,思想是相通的。
205 0
Lucene就是这么简单(一)