【优选算法】复写零

链接:1089. 复写零 - 力扣(LeetCode)

算法原理:

解法:双指针算法

根据“异地”操作,然后优化成双指针下的“就地”操作

1.先找到最后一个“复写”的数

        1.先判断 cur 位置的值

        2.决定 dest 向后移动一步或者两步

        3.判断一下 dest 是否已经到结束为止

        4.cur++;

        5.处理一下边界情况: n-1 = 0;

                                            cur--;

                                            dest -= 2;

2.“从后向前”完成复写操作

代码如下:

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, n = arr.length;
        //1.先找到最后一个需要复写的数
        while(cur < n){
            if(arr[cur] == 0){
                dest += 2;
            }else{
                dest += 1;
            }
            if(dest >= n-1){
                break;
            }
            cur++;
        }
        //2.处理一下边界情况
        if(dest == n){
            arr[n-1] = 0;
            cur--;
            dest -=2;
        }
        //3.从后向前完成复写
        while(cur >= 0){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}

复杂度分析:

  • 时间复杂度:O(n),虽然是两个while循环,但是常数部分可以忽略不计,相当于遍历一遍数组就完成了
  • 空间复杂度:O(1)

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

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

相关文章

moviepy将图片序列制作成视频并加载字幕 - python 实现

DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 需要更多数据资源和技术解决方案&#xff0c;知识星球&#xff1a; “DataBall - X 数据球(free)” -------------------------------------------------------------…

ubuntu20.04安装imwheel实现鼠标滚轮调速

ubuntu20.04安装imwheel实现鼠标滚轮调速 Ubuntu 系统自带的设置中仅具备调节鼠标速度的功能&#xff0c;而无调节鼠标滚轮速度的功能。其默认的鼠标滚轮速度较为缓慢&#xff0c;在查看文档时影响尚可接受&#xff0c;但在快速浏览网页时&#xff0c;滚轮速度过慢会给用户带来…

ubuntu开机进入initramfs状态

虚拟机卡死成功起后进入了initramfs状态&#xff0c;可能是跟文件系统有问题或者检索不到根文件系统&#xff0c;或者是配置错误&#xff0c;系统磁盘等硬件问题导致 开机后进入如下图的界面&#xff0c; 文中有一条提示 要手动fsck 命令修复 /dev/sda1 命令如下 fsck /de…

STL格式转换为OBJ格式

STL格式与OBJ格式简介 STL格式 STL&#xff08;Stereo Lithography&#xff09;文件是一种用于3D打印和计算机辅助制造&#xff08;CAM&#xff09;的文件格式。它最初由3D Systems公司开发&#xff0c;主要用于立体光刻技术。STL文件通常分为二进制和ASCII两种格式&#xff…

git命令恢复/还原某个文件、删除远程仓库中的文件

有时刚创建的远程仓库&#xff0c;可能无意中把一些没用的文件上传到仓库&#xff0c;本文介绍一下怎么删除这些文件。 一、git命令恢复某个文件 第一步&#xff1a;拉取最新代码 git pull 第二步&#xff1a; 查看git 修改的文件状态 git status 第三步&#xff1a;查看…

Chapter 3-1. Detecting Congestion in Fibre Channel Fabrics

Chapter 3. Detecting Congestion in Fibre Channel Fabrics This chapter covers the following topics: 本章包括以下主题: Congestion detection workflow. Congestion detection metrics. Congestion detection metrics and commands on Cisco MDS switches. Automatic A…

音视频入门基础:MPEG2-TS专题(20)——ES流简介

《T-REC-H.222.0-202106-S!!PDF-E.pdf》第27页对ES进行了定义。ES流是PES packets&#xff08;PES包&#xff09;中编码的视频、编码的音频或其他编码的比特流。一个ES流&#xff08;elementary stream&#xff09;在具有且只有一个stream_id的PES packets序列中携带&#xff1…

python+opencv+棋盘格实现相机标定及相对位姿估计

pythonopencv棋盘格实现相机标定及相对位姿估计 引言1&#xff0c;使用相机采集含棋盘格图像14张2&#xff0c;进行相机标定&#xff08;1&#xff09;测试软件1标定结果&#xff08;内参及畸变系数&#xff09;&#xff08;2&#xff09;测试软件2标定结果&#xff08;内参及畸…

【笔记】学校教的SSH:远程连接到另一个电脑 并对其进行操作

前言&#xff1a;我开了两台虚拟机做这个实验 一台是主机A ubuntu 一台是主机B centos7 &#xff08;一&#xff09;这里是在ubuntu进行的操作 1.安装ssh sudo apt install ssh 2.确认ssh激活了 systemctl status ssh 然后如图 这里是在主机B操作 就是如此简单 远程连接…

(九)腾讯cloudstudio(ubuntu)+akiaaa大神 Stable Diffusion整合包 AI绘画教程

一、说明 在网上转了一圈&#xff0c;发现确实akiaaa大神的整合包不错&#xff0c;看看这界面就比我前面的流弊多了&#xff0c;后面我们就要把这个界面一步一步干出来 二、环境准备 这里和前面的一样 &#xff08;七&#xff09;腾讯cloudstudioStable-Diffusion-webui AI绘…

6UCPCI板卡设计方案:8-基于双TMS320C6678 + XC7K420T的6U CPCI Express高速数据处理平台

基于双TMS320C6678 XC7K420T的6U CPCI Express高速数据处理平台 1、板卡概述 板卡由我公司自主研发&#xff0c;基于6UCPCI架构&#xff0c;处理板包含双片TI DSP TMS320C6678芯片&#xff1b;一片Xilinx公司FPGA XC7K420T-1FFG1156 芯片&#xff1b;六个千兆网口&#xff…

【专题】2024年悦己生活消费洞察报告汇总PDF洞察(附原数据表)

原文链接&#xff1a; https://tecdat.cn/?p38654 在当今时代背景下&#xff0c;社会发展日新月异&#xff0c;人们的生活方式与消费观念正经历深刻变革。MoonFox 月狐数据的《2024 年悦己生活消费洞察报告》聚焦于这一充满活力与变化的消费领域。随着就业、婚姻等社会压力的…

路由器的原理

✍作者&#xff1a;柒烨带你飞 &#x1f4aa;格言&#xff1a;生活的情况越艰难&#xff0c;我越感到自己更坚强&#xff1b;我这个人走得很慢&#xff0c;但我从不后退。 &#x1f4dc;系列专栏&#xff1a;网路安全入门系列 目录 路由器的原理一&#xff0c;路由器基础及相关…

Elasticsearch-分词器详解

什么是分词器 1、分词器介绍 对文本进行分析处理的一种手段&#xff0c;基本处理逻辑为按照预先制定的分词规则&#xff0c;把原始文档分割成若干更小粒度的词项&#xff0c;粒度大小取决于分词器规则。 常用的中文分词器有ik按照切词的粒度粗细又分为:ik_max_word和ik_smart&…

怿星科技联合赛力斯举办workshop活动,进一步推动双方合作

12月18日&#xff0c;由怿星科技与赛力斯汽车联合举办的workshop活动在赛力斯五云湖总部展开&#xff0c;双方嘉宾围绕智能汽车发展趋势、行业前沿技术、汽车电子网络与功能测试等核心议题展开了深度对话与交流&#xff0c;并现场参观演示了多套前沿产品。怿星科技CEO潘凯、汽车…

tomato靶场攻略

前提&#xff1a;kali和tomato的连接方式都为net模式 tomato的默认网络连接方式为桥接模式&#xff0c;导入前注意修改&#xff0c;将tomato.ova的镜像导入虚拟机中 出现此页面则表示导入成功&#xff0c;打开kali虚拟机终端&#xff0c;切换为root权限 arp-scan -l 浏览器访…

深度学习中,用损失的均值或者总和反向传播的区别

如深度学习中代码&#xff1a; def train_epoch_ch3(net, train_iter, loss, updater):"""The training loop defined in Chapter 3."""# Set the model to training modeif isinstance(net, torch.nn.Module):net.train()# Sum of training lo…

K8S Ingress 服务配置步骤说明

部署Pod服务 分别使用kubectl run和kubectl apply 部署nginx和tomcat服务 # 快速启动一个nginx服务 kubectl run my-nginx --imagenginx --port80# 使用yaml创建tomcat服务 kubectl apply -f my-tomcat.yamlmy-tomcat.yaml apiVersion: apps/v1 kind: Deployment metadata:n…

基于DockerCompose搭建Redis主从哨兵模式

linux目录结构 内网配置 哨兵配置文件如下&#xff0c;创建3个哨兵配置文件 # sentinel26379.conf sentinel26380.conf sentinel26381.conf 内容如下 protected-mode no sentinel monitor mymaster redis-master 6379 2 sentinel down-after-milliseconds mymaster 60000 s…

将java项目部署到linux

命令解析 Dockerfile: Dockerfile 是一个文本文件&#xff0c;包含了所有必要的指令来组装&#xff08;build&#xff09;一个 Docker 镜像。 docker build: 根据 Dockerfile 或标准指令来构建一个新的镜像。 docker save: 将本地镜像保存为一个 tar 文件。 docker load: 从…