当前位置: 首页 > 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;零冗余优化器 …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...