算法随笔_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 ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改…...
MoonBit 编译器(留档学习)
MoonBit 编译器 MoonBit 是一个用户友好,构建快,产出质量高的编程语言。 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 官方网站:Ollama 官方模型库:library 二、模型库搜索 deepseek r1 deepseek-r1:1.5b 私有化部署deepseek,模型库搜索 deepseek r1 运行cmd复制命令:ollama run deepseek-r1:1.5b 私有化…...
网络工程师 (13)时间管理
一、定义与重要性 项目时间管理是指为确保项目按时完成而采取的一系列规划、安排和控制活动。它始于项目启动阶段,贯穿整个项目生命周期,直至项目结束。时间管理对于项目的成功至关重要,它有助于项目团队明确工作目标和时间节点,增…...
【xdoj-离散线上练习】T251(C++)
解题反思: 开始敲代码前想清楚整个思路比什么都重要嘤嘤嘤!看到输入m, n和矩阵,注意不能想当然地认为就是高m,宽n的矩阵,细看含义 比如本题给出了树的邻接矩阵,就是n*n的,代码实现中没有用到m这…...
定时器按键tim_key模版
低优先级放在高优先级内势必是程序卡死 把高优先级放到低优先级内,会使程序卡死 可修改 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是一款国产开源免费的项目管理工具,工具简洁易用、开源免费,本文将介绍如何快速安装配置kanass,以快速上手。 1、快速安装 1.1 Linux 安装 点击官网 -> 演示与下载 ->下载,下载Linux安装包,…...
无用知识之:std::initializer_list的秘密
先说结论,用std::initializer_list初始化vector,内部逻辑是先生成了一个临时数组,进行了拷贝构造,然后用这个数组的起终指针初始化initializer_list。然后再用initializer_list对vector进行初始化,这个动作又触发了拷贝…...
论文阅读笔记 —— 英文论文常见缩写及含义
正文 缩写全称含义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访问数据库(二) 目的: 1、熟悉JDBC的数据库访问模式。 2、掌握预处理语句的使用 实验要求: 1、使用Tomcat作为Web服务器 2、通过JDBC访问数据库,实现增删改查功能的实现 3、要求提交实验报告,将代…...
[c语言日寄]C语言类型转换规则详解
【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋:这是一个专注于C语言刷题的专栏,精选题目,搭配详细题解、拓展算法。从基础语法到复杂算法,题目涉及的知识点全面覆盖,助力你系统提升。无论你是初学者,还是…...
Airflow:选择合适执行器扩展任务执行
Apache Airflow是面向开发人员使用的,以编程方式编写、调度和监控的数据流程平台。可伸缩性是其关键特性之一,Airflow支持使用不同的执行器来执行任务。在本文中,我们将深入探讨如何利用这些执行器在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){//标志位,如果有序,直接…...
AI大模型开发原理篇-4:神经概率语言模型NPLM
神经概率语言模型(NPLM)概述 神经概率语言模型(Neural Probabilistic Language Model, NPLM) 是一种基于神经网络的语言建模方法,它将传统的语言模型和神经网络结合在一起,能够更好地捕捉语言中的复杂规律…...
Eigen::Tensor使用帮助
0 引言 用python实现了某些算法之后,想转成C来获取更高的性能。但是python数组的操作太灵活了,尤其是3维、4维、5维等高维数组,以及它们的广播、数组坐标、切片等机制。还有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中,颜色可以通过以下几种方式表示,以下是具体的示例: 1. 十六进制颜色代码 十六进制颜色代码以#开头,后面跟随6个字符,每两个字符分别表示红色、绿色和蓝色的强度。例如: • #FF0000:纯红…...
OpenAI发布o3-mini:免费推理模型,DeepSeek引发的反思
引言 在人工智能领域,OpenAI再次引领潮流,推出了全新的推理模型系列——o3-mini。这一系列包括low、medium和high三个版本,旨在进一步推动低成本推理的发展。与此同时,OpenAI的CEO奥特曼也在Reddit的“有问必答”活动中罕见地公开…...
Zemax 中带有体素探测器的激光谐振腔
激光谐振腔是激光系统的基本组成部分,在光的放大和相干激光辐射的产生中起着至关重要的作用。 激光腔由两个放置在光学谐振器两端的镜子组成。一个镜子反射率高(后镜),而另一个镜子部分透明(输出耦合器)。…...
大模型训练(5):Zero Redundancy Optimizer(ZeRO零冗余优化器)
0 英文缩写 Large Language Model(LLM)大型语言模型Data Parallelism(DP)数据并行Distributed Data Parallelism(DDP)分布式数据并行Zero Redundancy Optimizer(ZeRO)零冗余优化器 …...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
CTF show 数学不及格
拿到题目先查一下壳,看一下信息 发现是一个ELF文件,64位的 用IDA Pro 64 打开这个文件 然后点击F5进行伪代码转换 可以看到有五个if判断,第一个argc ! 5这个判断并没有起太大作用,主要是下面四个if判断 根据题目…...
第22节 Node.js JXcore 打包
Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本,基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...
【大厂机试题解法笔记】矩阵匹配
题目 从一个 N * M(N ≤ M)的矩阵中选出 N 个数,任意两个数字不能在同一行或同一列,求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求:1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...
Heygem50系显卡合成的视频声音杂音模糊解决方案
如果你在使用50系显卡有杂音的情况,可能还是官方适配问题,可以使用以下方案进行解决: 方案一:剪映替换音色(简单适合普通玩家) 使用剪映换音色即可,口型还是对上的,没有剪映vip的&…...
