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

个人主页:Lei宝啊 

愿所有美好如期而遇


力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/duplicate-zeros/

算法原理

双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针,这道题目我们仍然定义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--;
            }             
        }     
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/202373.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C/C++内存管理(含C++中new和delete的使用)

文章目录 C/C内存管理&#xff08;含C中new和delete的使用&#xff09;1、C/C内存分布2、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free3、C动态内存管理3.1、new/delete操作内置类型3.2、new/delete操作自定义类型 4、operator new与operator delete函数5、…

立刻解决缺少msvcp140_1.dll解决方法,msvcp140_1.dll修复指南

在日常使用电脑的过程中&#xff0c;我们有时会遇到由于某些重要的DLL文件缺失而导致的程序无法正常启动的问题。很多用户可能都经历过由于缺少msvcp140_1.dll导致应用程序无法运行的情况。本文将为你提供解决msvcp140_1.dll缺失问题的详尽方法&#xff0c;附带对每种方法优点和…

景联文科技加入中国人工智能产业联盟(AIIA)数据委员会

近日&#xff0c;景联文科技加入中国人工智能产业联盟&#xff08;AIIA&#xff09;数据委员会&#xff0c;成为委员会成员单位。 中国人工智能产业发展联盟&#xff08;简称AIIA&#xff09;是在国家发改委、科技部、工信部、网信办指导下&#xff0c;由中国信息通信研究院等单…

Kafka 分布式消息系统

文章目录 消息中间件对比Kafka概述kafka安装和配置kafka入门生产者发送消息消费者接收消息 Kafka高可用设计集群备份机制(Replication&#xff09;备份机制(Replication)-同步方式 kafka生产者详解同步发送异步发送参数详解(ack)参数详解(retries)参数详解-消息压缩 kafka消费者…

Day45力扣打卡

打卡记录 无矛盾的最佳球队&#xff08;线性DP&#xff09; class Solution:def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:n len(scores) nums sorted(zip(scores, ages))f sorted(scores)for i in range(n):for j in range(0, i):if nu…

P8A012-A016组策略安全

账户策略 【预备知识】 组策略&#xff08;Group Policy&#xff09;是Microsoft Windows系统管理员为用户和计算机定义并控制程序、网络资源及操作系统行为的主要工具。通过使用组策略可以设置各种软件、计算机和用户策略。 【实验步骤】 网络拓扑&#xff1a;server2008A…

【开发实践】使用jstree实现文件结构目录树

一、需求分析 因开发系统的需要&#xff0c;维护服务端导出文件的目录结构。因此&#xff0c;需要利用jstree&#xff0c;实现前端对文件结构目录的展示。 【预期效果】&#xff1a; 二、需求实现 【项目准备】&#xff1a; jstree在线文档&#xff1a;jstree在线文档地址 …

(C++)移动零--双指针法

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://le…

ZooKeeper的分布式锁---客户端命令行测试(实操课程)

本系列是zookeeper相关的实操课程&#xff0c;课程测试环环相扣&#xff0c;请按照顺序阅读测试来学习zookeeper。阅读本文之前&#xff0c;请先阅读----​​​​​​zookeeper 单机伪集群搭建简单记录&#xff08;实操课程系列&#xff09;。 阅读本文之前&#xff0c;请先阅读…

【Vue3】源码解析-虚拟DOM

【Vue3】源码解析 系列文章什么是虚拟DOMVue 3虚拟DOM获取<template>内容生成AST语法树生成render方法字符串得到最终VNode对象 系列文章 【Vue3】源码解析-前置 【Vue3】源码解析-响应式原理 【Vue3】源码解析-虚拟DOM 什么是虚拟DOM 在浏览器中&#xff0c;HTML页面…

基于asp.net 消防安全宣传网站设计与实现

目 录 1 绪论 1 1.&#xff11;课题背景 1 1.2 目的和意义 1 1.3主要研究内容 1 1.4 组织结构 2 2 可行性分析 3 2.1技术可行性 3 2.2经济可行性 3 2.3操作可行性 3 2.4系统开发环境 4 3 需求分析 7 3.1性能分析 7 3.2业务流程分析 7 3.3数据流程分析 9 4 系统设计 11 4.1系统…

创建SpringBoot流程

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么&#xff1f;二、操作步骤总结 前言 我使用的是jdk1.8版本的&#xff0c;idea社区版的&#xff08;专业版的应该也差不多吧&#xff09; 提示…

Leetcode算法之哈希表

目录 1.两数之和2.判定是否互为字符重排3.存在重复元素I4.存在重复元素II5.字母异位词分组 1.两数之和 两数之和 class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;for(int i0;i<nums.si…

数据结构---二叉树

二叉树的概念及结构 1.概念 一棵二叉树是结点的一个有限集合&#xff0c;该集合: 或者为空 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出&#xff1a; 二叉树不存在度大于2的结点 二叉树的子树有左右之分&#xff0c;次序不能颠倒&#xff0c;因此…

某60物联网安全之IoT漏洞利用实操2学习记录

物联网安全 文章目录 物联网安全IoT漏洞利用实操2&#xff08;内存破坏漏洞&#xff09;实验目的实验环境实验工具实验原理实验内容实验步骤ARM ROP构造与调试MIPS栈溢出漏洞逆向分析 IoT漏洞利用实操2&#xff08;内存破坏漏洞&#xff09; 实验目的 学会ARM栈溢出漏洞的原理…

Unity C++交互

一、设置Dll输出。 两种方式&#xff1a; 第一&#xff1a;直接创建动态链接库工程第二&#xff1a;创建的是可执行程序&#xff0c;在visual studio&#xff0c;右键项目->属性(由exe改成dll) 二、生成Dll 根据选项Release或Debug&#xff0c;运行完上面的生成解决方案后…

FPGA设计时序约束十、others类约束之Set_Disable_Timing

目录 一、序言 二、Set Disable Timing 2.1 基本概念 2.2 设置界面 2.3 命令语法 2.4 命令示例 三、工程示例 四、参考资料 一、序言 在Vivado的时序约束窗口中&#xff0c;存在一类特殊的约束&#xff0c;划分在others目录下&#xff0c;可用于设置忽略或修改默认的时…

7.浮点数转为整数【2023.11.29】

1.问题描述 给出一个浮点数&#xff0c;请将这个浮点数转换成整数。 2.解决思路 输入一个浮点数。 输出程序将浮点数转换为整数并输出。 3.代码实现 numfloat(input("请输入一个浮点数")) num1int(num) print(num1)4.运行结果

智能优化算法应用:基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.萤火虫算法4.实验参数设定5.算法结果6.参考文献7.…

机关单位档案分类及整理方法

机关单位档案主要包含文书档案、干部职工档案&#xff08;人事档案&#xff09;、会计档案、科技档案&#xff08;科学研究、基本建设、设备仪器、产品&#xff09;、诉讼档案、音像档案、照片档案、电子档案等等&#xff0c;这其中&#xff0c;不同种类&#xff0c;不同载体的…