当前位置: 首页 > news >正文

算法随笔_36: 复写零

上一篇:算法随笔_35: 每日温度-CSDN博客

=====

题目描述如下:

给你一个长度固定的整数数组 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]

=====

算法思路:

这道题如果没有后边的条件(需要原地修改数组) ,比较容易解决。我们可以新开辟一段同样长度的数组res,然后定义两个指针p1,  p2,p1指向原数组首元素,p2指向res数组首元素。然后从右往左枚举原数组arr。如果访问到的arr[p1]不为0,那么把arr[p1]赋值给res[j],然后j向右移动一格。如果访问到的arr[p1]为0,那么连续j向右移动两格,每个格都赋值为0。以此类推,直到p2到达数组res末尾。

但如果需要原地修改数组,就需要多想想,再仔细分析一下这道题。

我们发现,还用上面的方法,直接在原数组修改,当遇到0的时候,p2指针会覆盖两个格子的元素。碰到越多0,覆盖的原值就越多。由于p2指针走的快,导致,当p1访问的时候,一些原值已经不复存在。这个问题如何解决呢?

我们发现,由于p2比p1走的快,当p2到达数组末尾时,p1还未到达末尾。也就是说p1到p2这段的元素是不需要p1访问的,最终的结果数组,也用不到这些元素。所以我们可以考虑从右往左修改数组。具体的操作如下:

1.  设结尾索引end_ind。我们从左往右枚举数组arr,索引值存于变量i。碰到值为非0的元素,end_ind加1。碰到值为0的元素,end_ind加2。直到end_ind大于等于数组长度退出。此时变量i就是需要保留的所有元素的最大索引。

2.  设变量j为数组的最后一个索引。

3. 我们从索引i处,从右往左枚举数组arr。如果arr[i]不为0,我们把arr[i]赋值给arr[j],然后j左移一格。如果arr[i]为0,我们把j连续向左移动两格,每个格都赋值为0。同时i也左移一格。当i小于0时,退出枚举,程序完成。

这里有个细节,需要补充一下,有可能end_ind大于数组长度。比如arr=[1,0],end_ind=3。由于长度肯定不能超过原数组长度。因此,在步骤2的时候,我们需要先判断一下,如果end_ind大于数组长度,需要把最后一个元素设为0。i,j各自减1,然后再运行步骤3。

此算法时间复杂度为O(n) 。下面是代码实现:

class Solution:def duplicateZeros(self, arr):arr_len= len(arr)end_ind=0i=0while i < arr_len:num=arr[i]if num==0:end_ind+=2else:end_ind+=1if end_ind>=arr_len:breaki+=1j=arr_len-1if end_ind>arr_len:arr[j]=0j-=1i-=1while i >=0:arr[j]=arr[i]j-=1if arr[i]==0:arr[j]=0j-=1i-=1   

相关文章:

算法随笔_36: 复写零

上一篇:算法随笔_35: 每日温度-CSDN博客 题目描述如下: 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改…...

MoonBit 编译器(留档学习)

MoonBit 编译器 MoonBit 是一个用户友好&#xff0c;构建快&#xff0c;产出质量高的编程语言。 MoonBit | Documentation | Tour | Core This is the source code repository for MoonBit, a programming language that is user-friendly, builds fast, and produces high q…...

使用 DeepSeek-R1 与 AnythingLLM 搭建本地知识库

一、下载地址Download Ollama on macOS 官方网站&#xff1a;Ollama 官方模型库&#xff1a;library 二、模型库搜索 deepseek r1 deepseek-r1:1.5b 私有化部署deepseek&#xff0c;模型库搜索 deepseek r1 运行cmd复制命令&#xff1a;ollama run deepseek-r1:1.5b 私有化…...

网络工程师 (13)时间管理

一、定义与重要性 项目时间管理是指为确保项目按时完成而采取的一系列规划、安排和控制活动。它始于项目启动阶段&#xff0c;贯穿整个项目生命周期&#xff0c;直至项目结束。时间管理对于项目的成功至关重要&#xff0c;它有助于项目团队明确工作目标和时间节点&#xff0c;增…...

【xdoj-离散线上练习】T251(C++)

解题反思&#xff1a; 开始敲代码前想清楚整个思路比什么都重要嘤嘤嘤&#xff01;看到输入m, n和矩阵&#xff0c;注意不能想当然地认为就是高m&#xff0c;宽n的矩阵&#xff0c;细看含义 比如本题给出了树的邻接矩阵&#xff0c;就是n*n的&#xff0c;代码实现中没有用到m这…...

定时器按键tim_key模版

低优先级放在高优先级内势必是程序卡死 把高优先级放到低优先级内&#xff0c;会使程序卡死 可修改 Debuger调试方法 Pwm rcc #include "my_main.h" uint8_t led_sta0x10; char text[30]; void LED_Disp(uint8_t dsLED) {HAL_GPIO_WritePin(GPIOC,GPIO_PIN_All,GPI…...

Kanass快速安装配置教程(入门级)

Kanass是一款国产开源免费的项目管理工具&#xff0c;工具简洁易用、开源免费&#xff0c;本文将介绍如何快速安装配置kanass&#xff0c;以快速上手。&#xfeff; 1、快速安装 1.1 Linux 安装 点击官网 -> 演示与下载 ->下载&#xff0c;下载Linux安装包&#xff0c;…...

无用知识之:std::initializer_list的秘密

先说结论&#xff0c;用std::initializer_list初始化vector&#xff0c;内部逻辑是先生成了一个临时数组&#xff0c;进行了拷贝构造&#xff0c;然后用这个数组的起终指针初始化initializer_list。然后再用initializer_list对vector进行初始化&#xff0c;这个动作又触发了拷贝…...

论文阅读笔记 —— 英文论文常见缩写及含义

正文 缩写全称含义Reference发音w.r.twith reference to关于, 根据WRT - Wikiet al.拉丁语et alia的缩写等等Et Al. | Meaning & Use in APA, MLA & Chicago–etc拉丁语et cetera的缩写等等ETC - Cambridge DictionaryWhat’s ‘etc.’ an abbreviation of (and what …...

实验9 JSP访问数据库(二)

实验9 JSP访问数据库&#xff08;二&#xff09; 目的&#xff1a; 1、熟悉JDBC的数据库访问模式。 2、掌握预处理语句的使用 实验要求&#xff1a; 1、使用Tomcat作为Web服务器 2、通过JDBC访问数据库&#xff0c;实现增删改查功能的实现 3、要求提交实验报告&#xff0c;将代…...

[c语言日寄]C语言类型转换规则详解

【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋&#xff1a;这是一个专注于C语言刷题的专栏&#xff0c;精选题目&#xff0c;搭配详细题解、拓展算法。从基础语法到复杂算法&#xff0c;题目涉及的知识点全面覆盖&#xff0c;助力你系统提升。无论你是初学者&#xff0c;还是…...

Airflow:选择合适执行器扩展任务执行

Apache Airflow是面向开发人员使用的&#xff0c;以编程方式编写、调度和监控的数据流程平台。可伸缩性是其关键特性之一&#xff0c;Airflow支持使用不同的执行器来执行任务。在本文中&#xff0c;我们将深入探讨如何利用这些执行器在Airflow中有效地扩展任务执行。 理解Airfl…...

使用冒泡排序模拟实现qsort函数

1.冒泡排序 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int arr[] { 0,2,5,3,4,8,9,7,6,1 };int sz sizeof(arr) / sizeof(arr[0]);//冒泡排序一共排序 sz-1 趟for (int i 0; i < sz - 1; i){//标志位&#xff0c;如果有序&#xff0c;直接…...

AI大模型开发原理篇-4:神经概率语言模型NPLM

神经概率语言模型&#xff08;NPLM&#xff09;概述 神经概率语言模型&#xff08;Neural Probabilistic Language Model, NPLM&#xff09; 是一种基于神经网络的语言建模方法&#xff0c;它将传统的语言模型和神经网络结合在一起&#xff0c;能够更好地捕捉语言中的复杂规律…...

Eigen::Tensor使用帮助

0 引言 用python实现了某些算法之后&#xff0c;想转成C来获取更高的性能。但是python数组的操作太灵活了&#xff0c;尤其是3维、4维、5维等高维数组&#xff0c;以及它们的广播、数组坐标、切片等机制。还有numpy的pad、where等操作更是给C转换带来了更多的麻烦。 查阅了相…...

git基础使用--3---git安装和基本使用

文章目录 git基础使用--3--git-安装和基本使用1. git工具安装1.1 git1.2 TortoiseGit1.3 远程仓2. git本地仓库版本管理2.1 git常用命令2.2 git基本操作2.2.1 设置用户名和邮箱 2.2 git基本操作2.2.1 初始化本地仓 git init2.2.2 查看本地库状态 git status2.2.3 添加暂缓区2.2…...

html的字符实体和颜色表示

在HTML中&#xff0c;颜色可以通过以下几种方式表示&#xff0c;以下是具体的示例&#xff1a; 1. 十六进制颜色代码 十六进制颜色代码以#开头&#xff0c;后面跟随6个字符&#xff0c;每两个字符分别表示红色、绿色和蓝色的强度。例如&#xff1a; • #FF0000&#xff1a;纯红…...

OpenAI发布o3-mini:免费推理模型,DeepSeek引发的反思

引言 在人工智能领域&#xff0c;OpenAI再次引领潮流&#xff0c;推出了全新的推理模型系列——o3-mini。这一系列包括low、medium和high三个版本&#xff0c;旨在进一步推动低成本推理的发展。与此同时&#xff0c;OpenAI的CEO奥特曼也在Reddit的“有问必答”活动中罕见地公开…...

Zemax 中带有体素探测器的激光谐振腔

激光谐振腔是激光系统的基本组成部分&#xff0c;在光的放大和相干激光辐射的产生中起着至关重要的作用。 激光腔由两个放置在光学谐振器两端的镜子组成。一个镜子反射率高&#xff08;后镜&#xff09;&#xff0c;而另一个镜子部分透明&#xff08;输出耦合器&#xff09;。…...

大模型训练(5):Zero Redundancy Optimizer(ZeRO零冗余优化器)

0 英文缩写 Large Language Model&#xff08;LLM&#xff09;大型语言模型Data Parallelism&#xff08;DP&#xff09;数据并行Distributed Data Parallelism&#xff08;DDP&#xff09;分布式数据并行Zero Redundancy Optimizer&#xff08;ZeRO&#xff09;零冗余优化器 …...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...