【双指针】专题:LeetCode 1089题解——复写零
复写零
- 一、题目链接
- 二、题目
- 三、算法原理
- 1、先找到最后一个要复写的数——双指针算法
- 1.5、处理一下边界情况
- 2、“从后向前”完成复写操作
- 四、编写代码
- 五、时间复杂度和空间复杂度
一、题目链接
复写零
二、题目
三、算法原理
解法:双指针算法
先根据“异地”操作,然后优化成双指针下的“就地”操作。
异地操作完成复写零:定义两个指针,一个指针cur指向原来的数组,一个指针dest指向新开辟的数组。两个指针从左往右操作。当cur指向非零,抄一遍;当cur指向零,抄两遍。当dest越界复写结束。
就地操作模拟异地操作:cur、dest都会指向原始数组。
我们发现会将非0元素覆盖为0,所以从前往后操作在本题行不通。
但是“删除数组中值为val的元素”这一题必须从前往后,同样先根据异地操作总结模拟规律,后就地根据双指针完成,因为是删除,所以dest肯定在cur前面,因此肯定不能覆盖那些未操作的数。
那么在本题“复写零”中从前往后不行,那么试试从后往前呢?两个指针初始位置怎么确定?抄写元素肯定要抄写到最后一位,所以dest在最后一个位置,那么cur指向最后一个要复写的数。
还是用示例1分析,dest指向数组最后一个位置,cur指向最后一个要复写的元素4,让复写操作从后往前进行。dest往前走的过程中,dest要修改的数已经复写过了就可以大胆地覆盖:
1、先找到最后一个要复写的数——双指针算法
我们发现从后往前走确实可行,但是要先找到最后一个要复写的数——双指针算法:
dest:始终指向完成复写的位置,所以初始位置在下标-1处。过程中判断dest是否到数组最后一个位置。
cur:从前向后遍历数组,决定dest向后移动1步或2步。所以初始位置在下标0处。
步骤:
- 判断cur指向的值
- cur的值决定dest是向后移动1步(cur为非0)或2步(cur为0)
- 判断dest是否到数组中的最后一个位置(若到最后,终止操作)
- 若dest没到最后,++cur
到最后,cur指向最后一个要复写的数;dest指向数组中的最后一个位置,也就是将“最后一个复写的数”写到的位置。这个位置就是cur、dest从后向前操作的起始位置。
1.5、处理一下边界情况
但是这样“找”在提交代码时还是会有问题的,特殊示例:
只会在最后一个要复写的数为0时dest才会越界,dest完成“从后向前”会对数组越界访问,在LeetCode上越界访问会报错。
若dest越界了:
- 数组下标n - 1处的值改为0
- cur- -、dest - = 2
2、“从后向前”完成复写操作
前面有复写操作的图片,这里就拿过来啦
四、编写代码
class Solution {
public:void duplicateZeros(vector<int>& arr) {// 1.先找到最后一个要复写的数--双指针算法int cur = 0, dest = -1, n = arr.size();while (dest < n){// 判断cur指向的值,决定dest走1步或2步if (arr[cur]) dest++;else dest += 2;// dest到最后了,cur所指就是最后复写的数if (dest >= n - 1) break;// dest没到最后++cur;}// 处理边界情况if (dest == n){arr[n - 1] = 0;--cur; dest -= 2;}// 2."从后向前"完成复写操作while (cur >= 0 && dest >= 0){if (arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;--cur;}}}
};
五、时间复杂度和空间复杂度
虽然是两个while循环,但是常数级别的时间是可以忽略的,因此时间复杂度是O(n),整体的时间复杂度就相当于遍历一遍数组就可以完成“复写”的操作。
空间复杂度只有限的使用到了3个变量,所以空间复杂度是O(1)。
相关文章:
【双指针】专题:LeetCode 1089题解——复写零
复写零 一、题目链接二、题目三、算法原理1、先找到最后一个要复写的数——双指针算法1.5、处理一下边界情况2、“从后向前”完成复写操作 四、编写代码五、时间复杂度和空间复杂度 一、题目链接 复写零 二、题目 三、算法原理 解法:双指针算法 先根据“异地”操…...
Foxmail邮件客户端跨站脚本攻击漏洞(CNVD-2025-06036)技术分析
Foxmail邮件客户端跨站脚本攻击漏洞(CNVD-2025-06036)技术分析 漏洞背景 漏洞编号:CNVD-2025-06036 CVE编号:待分配 厂商:腾讯Foxmail 影响版本:Foxmail < 7.2.25 漏洞类型&#x…...
39.[前端开发-JavaScript高级]Day04-函数增强-argument-额外知识-对象增强
JavaScript函数的增强知识 1 函数属性和arguments 函数对象的属性 认识arguments arguments转Array 箭头函数不绑定arguments 函数的剩余(rest)参数 2 纯函数的理解和应用 理解JavaScript纯函数 副作用概念的理解 纯函数的案例 判断下面函数是否是纯…...
0x05.为什么 Redis 设计为单线程?6.0 版本为何引入多线程?
回答重点 单线程设计原因: Redis 的操作是基于内存的,其大多数操作的性能瓶颈主要不是 CPU 导致的使用单线程模型,代码简便的同时也减少了线程上下文切换带来的性能开销Redis 在单线程的情况下,使用 I/O 多路复用模型就可以提高 Redis 的 I/O 利用率了6.0 版本引入多线程的…...
CST1019.基于Spring Boot+Vue智能洗车管理系统
计算机/JAVA毕业设计 【CST1019.基于Spring BootVue智能洗车管理系统】 【项目介绍】 智能洗车管理系统,基于 Spring Boot Vue 实现,功能丰富、界面精美 【业务模块】 系统共有三类用户,分别是:管理员用户、普通用户、工人用户&…...
CST1018.基于Spring Boot+Vue滑雪场管理系统
计算机/JAVA毕业设计 【CST1018.基于Spring BootVue滑雪场管理系统】 【项目介绍】 滑雪场管理系统,基于 Spring Boot Vue 实现,功能丰富、界面精美 【业务模块】 系统共有两类用户,分别是管理员和普通用户,管理员负责维护后台数…...
剖析 Rust 与 C++:性能、安全及实践对比
1 性能对比:底层控制与运行时开销 1.1 C 的性能优势 C 给予开发者极高的底层控制能力,允许直接操作内存、使用指针进行精细的资源管理。这使得 C 在对性能要求极高的场景下,如游戏引擎开发、实时系统等,能够发挥出极致的性能。以…...
SDHC接口协议底层传输数据是安全的
SDHC(Secure Digital High Capacity)接口协议在底层数据传输过程中确实包含校验机制,以确保数据的完整性和可靠性。以下是关键点的详细说明: 物理层与数据链路层的校验机制 物理层(Electrical Layer)&…...
Gateway-网关-分布式服务部署
前言 什么是API⽹关 API⽹关(简称⽹关)也是⼀个服务, 通常是后端服务的唯⼀⼊⼝. 它的定义类似设计模式中的Facade模式(⻔⾯模式, 也称外观模式). 它就类似整个微服务架构的⻔⾯, 所有的外部客⼾端访问, 都需要经过它来进⾏调度和过滤. 常⻅⽹关实现 Spring Cloud Gateway&a…...
c++STL——string学习的模拟实现
文章目录 string的介绍学习的意义auto关键字和范围forstring中的常用接口构造和析构对string得容量进行操作string的访问迭代器(Iterators):运算符[ ]重载 string类的修改操作非成员函数 string的模拟实现不同平台下的实现注意事项模拟实现部分所有的模拟实现函数预…...
【寻找Linux的奥秘】第四章:基础开发工具(下)
请君浏览 前言1. 自动化构建1.1 背景1.2 基本语法1.3 make的运行原理1.4通用的makefile 2. 牛刀小试--Linux第一个小程序2.1 回车与换行2.2 行缓冲区2.3 倒计时小程序2.4 进度条小程序原理代码 3. 版本控制器git3.1 认识3.2 git的使用三板斧 3.3 其他 4. 调试器gdb/cgdb4.1 了解…...
RK3588上Linux系统编译C/C++ Demo时出现BUG:The C/CXX compiler identification is unknown
BUG的解决思路 BUG描述:解决方法:首先最重要的一步:第二步:正确设置gcc和g的路径方法一:使用本地系统中安装的 aarch64-linux-gnu-gcc 和 aarch64-linux-gnu-g方法二:下载使用官方指定的交叉编译工具方法三…...
记录一次/usr/bin/ld: 找不到 -lOpenSSL::SSL
1、cmake 报错内容如下: /usr/bin/ld: 找不到 -lOpenSSL::SSL /usr/bin/ld: 找不到 -lOpenSSL::Crypto2、一开始以为库没有正确安装 sudo yum install openssl-devel然后查看openssl 结果还是报错! 3、尝试卸载安装都不管用,网上搜了好多…...
[16届蓝桥杯 2025 c++省 B] 水质检测
思路:分类讨论,从左到右枚举,判断当前的河床和下一个河床的距离是第一行更近还是第二行更近还是都一样近,分成三类编写代码即可 #include<iostream> using namespace std; int main(){string s1,s2;cin>>s1>>…...
基于PySide6与pycatia的CATIA绘图比例智能调节工具开发全解析
引言:工程图纸自动化处理的技术革新 在机械设计领域,CATIA图纸的比例调整是高频且重复性极强的操作。传统手动调整方式效率低下且易出错。本文基于PySide6pycatia技术栈,提出一种支持智能比例匹配、实时视图控制、异常自处理的图纸批处理方案…...
四、Appium Inspector
一、介绍 Appium Inspector 是一个用于移动应用自动化测试的图形化工具,主要用于检查和交互应用的 UI 元素,帮助生成和调试自动化测试脚本。类似于浏览器的F12(开发者工具),Appium Inspector 的主要作用包括: 1.检查 UI 元素 …...
玩转Docker | 使用Docker部署MicroBin粘贴板
玩转Docker | 使用Docker部署MicroBin粘贴板 前言一、MicroBin介绍MicroBin 简介主要特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署MicroBin服务下载镜像创建容器检查容器状态检查服务端口安全设置四、访问MicroBin服务访问MicroBin首页登录管理后台…...
BGP分解实验·23——BGP选路原则之路由器标识
在选路原则需要用到Router-ID做选路决策时,其对等体Router-ID较小的路由将被优选;其中,当路由被反射时,包含起源器ID属性时,该属性将代替router-id做比较。 实验拓扑如下: 实验通过调整路由器R1和R2的rout…...
MQTT:单片机中MQTTClient-C移植定时器功能
接下来我们完善MQTTTimer.c和MQTTTimer.h两个功能 MQTTTimer.h void TimerInit(Timer* timer); 功能:此函数用于对 Timer 结构体进行初始化。在 MQTT 客户端里,定时器被用于追踪各种操作的时间,像连接超时、心跳包发送间隔等。初始化操作会…...
可拖动的关系图谱原型案例
关系图谱是一种以图结构形式组织和呈现实体间复杂关联关系的可视化数据模型。它通过节点和线构建多维度网络,能直观揭示隐藏的群体特征和传播路径。在社交网络分析、智能推荐系统、知识图谱构建等领域广泛应用。 软件版本:Axure RP 9 作品类型…...
CST1016.基于Spring Boot+Vue高校竞赛管理系统
计算机/JAVA毕业设计 【CST1016.基于Spring BootVue高校竞赛管理系统】 【项目介绍】 高校竞赛管理系统,基于 DeepSeek Spring AI Spring Boot Vue 实现,功能丰富、界面精美 【业务模块】 系统共有两类用户,分别是学生用户和管理员用户&a…...
从三次方程到复平面:复数概念的奇妙演进(二)
注:本文为 “复数 | 历史 / 演进” 相关文章合辑。 因 csdn 篇幅限制分篇连载,此为第二篇。 生料,不同的文章不同的点。 机翻,未校。 History of Complex Numbers 复数的历史 The problem of complex numbers dates back to …...
PCL 点云投影至指定平面
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 之前的文章中介绍过一个点在平面上的投影坐标,其主要的思路就是利用投影垂线与平面法向量平行的特性,通过推导出的投影公式可以很容易的计算出在某点在某一平面内的投影点。因此只需要重复该过程就可以将整个点云…...
批量将文件名称、文件路径、文件扩展名提取到 Excel 清单
在数字化时代,文件的高效管理至关重要。当我们想要对磁盘中的文件进行整理,想要获取多个文件夹中的文件和路径信息,就需要现将这些文件的名称及路径信息提取出来。本文将介绍一种实用的批量提取技术,帮助用户优化文件管理流程&…...
KWDB创作者计划—KWDB场景创新:多模态数据融合与边缘智能的产业实践
引言:AIoT时代的数据基座重构 在工业物联网设备数量突破千亿、边缘计算节点覆盖率达75%的2025年,传统数据库面临多模态数据处理效率低下、边缘端算力利用率不足、跨域数据协同困难等核心挑战。KWDB(KaiwuDB Community Edition)通过…...
计算机系统概论
1. 计算机系统的基本组成 计算机系统由 硬件系统 和 软件系统 两大部分协同工作: 硬件系统: 基于冯诺依曼体系结构(存储程序原理),包含五大核心部件: 运算器(ALU):执行算…...
Android Cmake构建的项目,需不需要配置指定ndk及版本
在 CMake 构建的 Android 项目中,是否需要显式配置 NDK 及其版本,取决于项目的具体需求和环境。以下是详细分析和建议: 1. 是否需要显式配置 NDK 及版本? 情况 1:Android Studio 自动管理 NDK(推荐&#x…...
国内AI大模型卷到什么程度了?
目录 1.开源大模型更有前景吗? 2.参数越大真的越牛逼吗? 3.榜单排名有意义吗? 大家好这里是AIWritePaper官方账号,官网👉AIWritePaper~ 大模型开源更有前景? 参数越大真的越牛逼吗? 榜单排…...
【HDFS入门】Hadoop 2.0+ HDFS核心架构深度解析:高可用设计揭秘
目录 1 HDFS核心架构概述 2 高可用设计背景 3HDFS核心组件 3.1 Active与Standby NameNode 3.2 JournalNode 3.3 ZKFailoverController(ZKFC) 3.4 DataNode 4 高可用设计的工作流程 写入阶段: 元数据同步: 健康监测&…...
RabbitMQ安装
RabbitMQ安装 Ubuntu环境安装 一、安装Erlang #更新软件包 sudo apt-get update #安装erlang sudo apt-get install erlang 二、安装RabbitMQ #更新软件包 sudo apt-get update #安装rabbitmq sudo apt-get install rabbitmq-server #确认安装结果 systemctl status rabbitmq-…...
2022 CCPC Henan Provincial Collegiate Programming Contest K 复合函数
补题链接 看网上题解很少,来写一份,这题个人觉得思维难度不是特别大,难度主要在于代码准确度,首先将问题转化成 x x x 向 f ( x ) f(x) f(x) 连边,这一步转化应该是比较容易想到的,通过手模样例,会有类…...
Linux : 多线程互斥
目录 一 前言 二 线程互斥 三 Mutex互斥量 1. 定义一个锁(造锁) 2. 初始化锁 3. 上锁 4. 解锁 5. 摧毁锁 四 锁的使用 五 锁的宏初始化 六 锁的原理 1.如何看待锁? 2. 如何理解加锁和解锁的本质 七 c封装互斥锁 八 可重入…...
【数学建模】佳点集(Good Point Set)在智能优化算法中的应用与实现
佳点集(Good Point Set)在智能优化算法中的应用与实现 文章目录 佳点集(Good Point Set)在智能优化算法中的应用与实现1. 佳点集概述2. 佳点集的数学原理3. 佳点集在智能优化算法中的应用3.1 改进麻雀搜索算法(SSA)3.2 改进量子粒子群优化算法(QPSO)3.3 自适应分组差分变异狼群…...
redis linux 安装简单教程(redis 3.0.4)
redis.3.0.4.tar.gz 下载地址 链接: https://pan.baidu.com/s/19VAcrA6XS4mIesH6e5Jftg 提取码: bn2r (1)以安装目录:/home/zsl (2)将redis-3.0.4.tar.gz 拷贝到/home/zsl (3)tar xzvf redis-3.…...
探秘 Python 网络编程:构建简单聊天服务器
在计算机网络的世界里,网络编程是实现不同设备之间通信的关键技术。Python 凭借其简洁的语法和强大的库支持,在网络编程领域有着广泛的应用。无论是构建简单的聊天服务器,还是开发复杂的网络应用,Python 都能轻松胜任。 1 理论基础…...
debian转移根目录
如何在 BIOS 启动的 Debian 虚拟机中将根目录转移到 /dev/sda 设备上?本文将从硬盘分区,根目录复制,重新启动等几个方面介绍。 硬盘分区 1.检查磁盘:查看当前的磁盘和分区情况,确认新添加的磁盘设备名称。 parted -…...
vue3 element-plus表单验证
第一准备一个表单 form.vue <template><div><el-form><el-form-item label"姓名" prop"name"><el-input v-model"data.name" placeholder"请输入姓名"></el-input></el-form-item></e…...
Deepseek IP-Adapter与InstantID的区别
IP-Adapter与InstantID均为基于扩散模型的图像生成控制技术,但两者的算法设计目标、核心模块及应用场景存在显著差异。以下从技术架构、特征处理、条件控制等维度对比两者的差异: 1. 核心设计目标 IP-Adapter 由腾讯团队提出(2023年8月&…...
OSI 七层模型与 TCP/IP 协议栈详解
OSI 七层模型与 TCP/IP 协议栈详解 网络协议模型是理解计算机网络和通信的基础,而 OSI 七层模型和 TCP/IP 协议栈是最常见的两种网络通信模型。虽然这两者有些不同,但它们都提供了一种分层的结构,帮助我们理解和设计网络通信。本文将详细介绍…...
synchronize 或者lock 锁常见的使用场景
在 Java 多线程编程中,synchronized 和 Lock(如 ReentrantLock)是两种常见的线程同步机制。以下是它们的核心区别和典型使用场景,结合代码示例说明: 一、synchronized 的常见场景 1. 简单的临界区保护 public class …...
Redis之缓存更新策略
缓存更新策略 文章目录 缓存更新策略一、策略对比二、常见的缓存更新策略三、如何选择策略四、实际应用示例五、使用 Cache-Aside TTL 的方式,实现缓存商铺信息详情1.引入StringRedisTemplate2.将查询商铺信息加入缓存3.更新商铺信息时移除缓存总结 六、注意事项 一…...
【操作系统学习篇-Linux】进程
1. 什么是进程 课本概念:程序的一个执行实例,正在执行的程序等 内核观点:担当分配系统资源(CPU时间,内存)的实体。 如果你就看这个来理解进程,那么恭喜你,作为初学者,你…...
Docker 前瞻
一、namespace 指令 1.1 dd 命令 dd 命令用于读取、转换并输出数据。 dd 命令可从标准输入或文件中读取数据,根据指定的格式来转换数据,再输出到文件、设备或标准输出。 语法 dd option if 文件名:输入文件名,默认为标准输入…...
【maxENT】最大熵模型(Maximum Entropy Model)R语言实现
文章目录 一、相关package介绍1.1 dismo 包1.2 raster包1.3 常见问题与解决 二、代码示例 🟢🟠先看:【maxENT】最大熵模型(Maximum Entropy Model)介绍与使用(maxENT软件) ASCII文件太大&#…...
高负载WEB服务器--Tomcat
高负载WEB服务器–Tomcat Tomcat介绍 Tomcat 是一个开源的轻量级应用服务器,在 Java Web 应用开发中被广泛使用。 发展历程:Tomcat 最初由 Sun Microsystems 开发,后来成为 Apache 软件基金会的一个项目。它的发展与 Java 技术的发展密切相…...
分页查询列表每页1000条的优化
项目中有一个客户列表,要求每页显示1000条,并且字段很多,接口返回大概要10秒钟,进行优化. 原本逻辑:使用mybatisplus构建查询条件,分页查询客户表,查出数据库DO对象,然后for循环转化成回显的VO对象.在转化的过程中出现了查库代码,导致当每页条数1000时,每一个客户转化都需要查询…...
深入浅出一下Python面向对象编程的核心概念与实践应用
本篇技术博文摘要 🌟 本文系统讲解了Python面向对象编程的核心概念与实践应用。通过电商系统用户订单模拟、动态权限账户系统等案例,深入剖析了类与对象、属性方法、实例方法等基础要素。重点解析了__init__构造方法、__str__对象描述、__lt__比较运算符…...
2025阿里云AI 应用-AI Agent 开发新范式-MCP最佳实践-78页.pptx
2025阿里云AI 应用-AI Agent 开发新范式-MCP最佳实践,包含以下内容: 1、AI 应用架构新范式 2、云原生API网关介绍 3、云原生API网关底座核心优势 4、流量网关最佳实践 5、AI 网关代理 LLM 最佳实践 6、MCP网关最佳实践 7、MSE Nacos MCP Server 注册中心…...
github进阶使用教程
目录索引 一、基本内容 repository fork star codespaces issue 在一个仓库创建话题讨论,可以由仓库主人选择开始和结束话题的讨论 pull request(也称 pr) 协同其他仓库开发,请求仓库主人拉取自己的代码合并到仓库的主分支&…...
【C++】 —— 笔试刷题day_16
刷题_day16,继续加油啊 一、字符串替换 题目解析 这道题是一道简单的字符题目,题目给我们一个字符串A,和n表示A字符串的长度,再给出一个字符数组arg,m表示arg中是数据个数。 然我们在字符串A中找到%s然后替换成arg中的…...