Leetcode 1089.复写零

目录

题目

思路

代码


题目

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

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

示例 1:

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

示例 2:

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

思路

题目依然是对数组元素原地进行修改,所以可以采用双指针的思路来解题,一个负责遍历一个负责更改,所以可以设立两个指针,cur和dest,cur负责遍历数组,dest负责更改数据,如果非零,dest就复写一遍,如果是0,dest就往后写入两个0。

可通过观察发现,如果从前往后进行遍历更改,就会导致数据被覆盖。从而破坏了数组的完整性。

因为在对数组进行修改时,多余的元素会从数组的队尾出,所以可以从后往前去更改数组。

所以我们可以先去找到最后一个需要复写的数,这样就可以确定数组的最后一个元素的值,从而可

以更好的控制写入时不发生溢出。

如上所示,当dest走到头时此时cur的位置就是最后一个需要复写的数。

但当以下情况出现时,dest会出现越界的情况,如果直接去访问就会导致越界问题。

所以当碰到越界以后需要进行一个特殊处理,当dest==n时说明越界了,也说明最后一个复写的元素绝对是0才会导致dest越界,所以直接把下标为n-1也就是数组最后一个元素的值修改为0然后让dest-=2,同时让cur往前移动一位。此时第一步就完成了。接下来就可以修改数组数据了。

先判断cur对应的元素是否为0,如果不为0 dest修改该位置元素然后向前移动一位,如果为0 将该位置元素改为0然后向前把前一个位置元素也改为0。

代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int cur=0,dest=-1,n=arr.size();
        while(cur<n)//找最后一个需要复写的下标
        {
            if(arr[cur]) ++dest;
            else dest+=2;
            if(dest>=n-1) break;
            cur++;
        }
        if(dest==n)
        {
            dest-=2;
            --cur;
            arr[n-1]=0;
        }
        while(cur>=0)
        {
            if(arr[cur])arr[dest--]=arr[cur];
            else 
            {
                arr[dest--]=0;
                arr[dest--]=0;
            }
            cur--;
        }
    }
};

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

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

相关文章

javascript选择器大全

目录 1.getElementsByTagName 2.getElementsByName 3.getElementById 4.getElementsByClassName 5.querySelector 6.querySelectorAll 1.getElementsByTagName 俗称标签选择器&#xff0c;可以根据标签名查找匹配到页面的元素对象&#xff0c;返回为一个数组。 <div&…

google邮箱开启两步验证

我开发的chatgpt网站&#xff1a; https://chat.xutongbao.top/

美国Mercari煤炉注册教程,还不快来Get!

想要掘金全球电商市场&#xff0c;美国的Mercari平台绝对值得关注。Mercari&#xff0c;也被称作煤炉&#xff0c;类似于我们国内的闲鱼二手交易平台&#xff0c;它同时拥有美国和日本两个市场。其中&#xff0c;美国市场的消费需求稳定且持续增长&#xff0c;成为了许多跨境电…

Gradle8之下载安装与环境变量配置及国内下资源设置

Gradle8之下载安装与环境变量配置及国内下资源设置 文章目录 Gradle8之下载安装与环境变量配置及国内下资源设置1. Gradle1. 官网2. 关于Gradle1. 构建任何内容2. 自动化一切3. 更快地交付 2. 下载与安装1. 下载2. 环境变量3.本地存储路径4. 查看Gradle版本 3. 配置国内下资源1…

GZ036 区块链技术应用赛项赛题第8套

2023年全国职业院校技能大赛 高职组 “区块链技术应用” 赛项赛卷&#xff08;8卷&#xff09; 任 务 书 参赛队编号&#xff1a; 背景描述 现实中患者私密信息泄露情况时有发生&#xff0c;医疗部门的柜式存储和纸质记录已不再是最优选择。在2015-2016年间&…

爬虫知识--01

爬虫介绍 # 爬虫的概念&#xff1a; 通过编程技术(python:request,selenium)&#xff0c;获取互联网中的数据(app&#xff0c;小程序&#xff0c;网站)&#xff0c;数据清洗(xpaht&#xff0c;lxml)后存到库中(mysql&#xff0c;redis&#xff0c;文件&#xff0c;excel&#x…

探索未来-Sora

AI如何将静态图像转化为动态、逼真的视频&#xff1f; OpenAI 的 Sora 通过时空片段&#xff08;以下统称片段&#xff09;的创新使用给出了答案。 Sora 展示与探讨 在快速发展的生成模型领域&#xff0c;OpenAI 的 Sora成为一个重要的里程碑&#xff0c;有望重塑我们对视频生…

uniapp离线打包(使用Android studio打包)

一、准备工作 安装HbuilderX&#xff0c;记住版本号下载对应HbuilderX版本的Android离线SDK&#xff0c;如我使用3.6.18版本打包&#xff0c;则对应应下载3.6.18版本的SDK&#xff08;官网不提供旧版本的SDK&#xff0c;有些需要自己找&#xff09;官网下载地址&#xff1a;ht…

亚马逊鲲鹏系统一键注册亚马逊买家号的软件

在如今的电商世界中&#xff0c;自动注册亚马逊买家号已经成为了一种必要的操作需求。为了规避关联性问题&#xff0c;许多用户选择借助专门设计的软件工具&#xff0c;其中最为流行的就是亚马逊鲲鹏系统。这款软件以其自带防指纹浏览器和全自动化操作功能而闻名。 亚马逊鲲鹏系…

《摔跤吧爸爸》19岁女星突患皮肌炎离世

从确诊到离世仅10天……罕见病“皮肌炎”&#xff01; 曾凭借在知名电影《摔跤吧&#xff01;爸爸》中饰演童年时期“小芭比塔”一角而广受喜爱的年轻演员苏哈尼巴特纳格尔不幸离世&#xff0c;年仅19岁。她的突然逝世引发了全球关注&#xff0c;据苏哈妮的家人表示&#xff0…

基于docker安装HDFS

1.docker一键安装见 docker一键安装 2.拉取镜像 sudo docker pull kiwenlau/hadoop:1.03.下载启动脚本 git clone https://github.com/kiwenlau/hadoop-cluster-docker4.创建网桥 由于 Hadoop 的 master 节点需要与 slave 节点通信&#xff0c;需要在各个主机节点配置节点…

ACE 中的Active Object模式

Active Object 设计模式&#xff1a; 1&#xff09; 根据对象被调用的方式&#xff0c;可以将对象分为两类: Passive Object和Active Object。Passive 和 Object和调用者在同一个线程中&#xff0c;这就是我们通常所用的函数调用。而Active Object和调用在不同的线程中&#xf…

漏洞挖掘 | 编辑器漏洞之kindeditor

本文由掌控安全学院 - master666 投稿 今天呢给大家复现一个kindeditor<4.1.5上传漏洞。小弟能力有限&#xff0c;还在坚持学习的路上&#xff0c;还请大佬多多指教。自我感觉编辑器漏洞很容易忽视。此文章作为记录本人学习的开始&#xff0c;丰富自己的阅历。我们共同进步…

TLS指纹校验原理和绕过

TLS指纹校验原理和绕过 1.指纹校验案例 当用浏览器访问时能够正常访问&#xff0c;而用代码请求却得不到相应结果 1.1 案例&#xff1a;ascii2d https://ascii2d.net/ 1.2 案例&#xff1a;investing https://cn.investing.com/equities/amazon-com-inc-historical-data 2.T…

【JavaScript】数组操作 遍历、修改、新增、删除等...

目录 一、数组是什么&#xff1f; 二、数组操作 2.1、遍历 2.2、数组求最大值和最小值 2.3、修改 2.4、新增 追加到数组末尾 添加到数组开头 2.5、删除 一、数组是什么&#xff1f; 数组是一种可以按顺序保存数据的数据类型。 二、数组操作 2.1、遍历 let arr [马…

14. UE5 RPG使用曲线表格设置回复血量值

之前的文章中&#xff0c;我使用的都是固定的数值来设置血量回复或者蓝量回复&#xff0c;在这篇文章里面&#xff0c;介绍一下使用曲线表格。通过曲线表格我们可以设置多个数值&#xff0c;然后通过去通过修改索引对应的数值去修改回复的血量或者蓝量。 创建曲线表格 首先创…

【Unity】【VRTK】【VR开发】同时保持高效打包和调试的VRTK项目设置方式

【背景】 开发功能时希望能够快速调试&#xff0c;在Preview和开发编辑器间流畅切换。后期又希望快速打包到目标安卓平台&#xff0c;感受头盔内部的画面和操作效果。麻烦在于&#xff0c;这两者往往不是明确区分的&#xff0c;很可能一会儿只是想快速验证一下某些功能动作&am…

安全名词解析-攻防演练

为方便您的阅读&#xff0c;可点击下方蓝色字体&#xff0c;进行跳转↓↓↓ 01 攻防演练 01 攻防演练 《网络安全法》中明确提出&#xff0c;“定期组织关键信息基础设施的运营者进行网络安全应急演练&#xff0c;提高应对网络安全事件的水平和协同配合能力。”攻防演练目前已经…

机器视觉【3】非线性求解相机几何参数

线性求解相机几何参数的缺点 上一章节介绍学习了&#xff08;DLT&#xff09;线性求解相机几何参数&#xff0c;了解到线性求解法当中比较明显的缺点&#xff1a; 没有考虑到镜头畸变的影响不能引入更多的约束条件融入到DLT算法当中优化最关键的是&#xff0c;代数距离并不是…

OpenCV中inRange函数

在OpenCV中&#xff0c;inRange函数用于根据颜色范围从图像中提取特定的颜色区域。这个函数检查输入图像中的每个像素&#xff0c;如果像素值位于指定的范围内&#xff0c;则在输出图像&#xff08;或掩码&#xff09;中对应位置的像素被设置为白色&#xff08;或者说是255&…