【算法专题突破】双指针 - 复写零(2)
目录
1. 题目解析
2. 算法原理
3. 代码编写
写在最后:
1. 题目解析
题目链接:1089. 复写零 - 力扣(Leetcode)
我先来读题,
题目的意思非常的简单,其实就是,
遇到 0 就复制一个写进数组,然后右边的元素就右移一位,
看一眼例子可以很容易理解题意。
2. 算法原理
一般像这种需要移动数组的元素的题目,
也非常常用双指针算法来解题。
这道题如果不使用原地算法,会非常简单,
一个指针遍历原数组,一个指针遍历新数组,
遇到非 0 就直接写进数组,遇到 0 就写两个0进数组即可。
而如果我们想把这个算法优化成原地呢?
我们先从左往右试一下:
看起来并不太行:
会出现全部都复写成0的情况,因为原来的数被修改了,
那我们可以试试从后往前的思路:
我们让cur 指向最后一次写入的位置:
然后模拟双指针的过程:
cur遇到0就复写两次:
遇到非 0 就正常写入:
以此类推:
我们发现就成功了,
那现在问题来了,我们怎么得到cur的起始位置,
或者说我们该怎么得到最后一次写入的位置?
我们可以用 cur 和 dest 两个指针来模拟写入的过程,是的,又是双指针:
1. 判断cur位置是 0 还是 非0
2. dest根据cur位置的值决定走一步还是走两步
3. 判断dest是否已经走到结尾了
4. 如果没到结尾就cur++,如果已经走到结尾了那cur指向的位置就是最后一次写入的数
不过要小心dest的越界问题,如果走到倒数第二个数的时候,cur走到0,
dest往后走两步就会出现越界的问题。我们到时候让cur后退一步,dest后退两步就行。
3. 代码编写
class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest = -1, cur = 0, size = arr.size();// 找到最后一次写入的位置while(cur < size) {if(arr[cur]) dest++;else dest += 2;if(dest >= size - 1) break; //走完了cur++;}// 控制边界if(dest == size) { //这种就是最后一步是0,走了两步dest越界的情况arr[size - 1] = 0;dest -= 2;cur--;}// 从后往前做写入操作while(cur >= 0) {if(arr[cur]) arr[dest--] = arr[cur--];else {arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
相关文章:

【算法专题突破】双指针 - 复写零(2)
目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 1. 题目解析 题目链接:1089. 复写零 - 力扣(Leetcode) 我先来读题, 题目的意思非常的简单,其实就是, 遇到 0 就复制一个写进数组&a…...

【Java从0到1学习】11 Java集合框架
1. Collection 1.1 Java类中集合的关系图 1.2 集合类概述 在程序中可以通过数组来保存多个对象,但在某些情况下开发人员无法预先确定需要保存对象的个数,此时数组将不再适用,因为数组的长度不可变。例如,要保存一个学校的学生信…...

uniapp使用uni.chooseLocation()打开地图选择位置
使用uni.chooseLocation()打开地址选择位置: 在Uniapp源码视图进行设置 添加这个属性:"requiredPrivateInfos":["chooseLocation"] </template><view class"location_box"><view class"locatio…...

学习笔记|课后练习解答|电磁炉LED实战|逻辑运算|STC32G单片机视频开发教程(冲哥)|第八集(下):课后练习分析与解答
文章目录 课后练习解答需求分解增加KEY3控制代码如下: 第一版代码问题分析Tips:STC-ISP的设置 Tips:定时器实现完整电磁炉显示功能的代码测试流程 总结 课后练习解答 增加按键3,按下后表示启动,选择的对应的功能的LED…...

前端高频面试题 js中堆和栈的区别和浏览器的垃圾回收机制
一、 栈(stack)和 堆(heap) 栈(stack):是栈内存的简称,栈是自动分配相对固定大小的内存空间,并由系统自动释放,栈数据结构遵循FILO(first in last out)先进后出的原则,较为经典的就是乒乓球盒结…...
自然语言处理:大语言模型入门介绍
自然语言处理:大语言模型入门介绍 语言模型的历史演进大语言模型基础知识预训练Pre-traning微调Fine-Tuning指令微调Instruction Tuning对齐微调Alignment Tuning 提示Prompt上下文学习In-context Learning思维链Chain-of-thought提示开发(调用ChatGPT的…...

使用秘籍|如何实现图数据库 NebulaGraph 的高效建模、快速导入、性能优化
本文整理自 NebulaGraph PD 方扬在「NebulaGraph x KubeBlocks」meetup 上的演讲,主要包括以下内容: NebulaGraph 3.x 发展历程NebulaGraph 最佳实践 建模篇导入篇查询篇 NebulaGraph 3.x 的发展历程 NebulaGraph 自 2019 年 5 月开源发布第一个 alp…...

对于pycharm 运行的时候不在cmd中运行,而是在python控制台运行的情况,如何处理?
对于pycharm 运行的时候不在cmd中运行,而是在python控制台运行的情况,如何处理? 比如,你在运行你的代码的时候 它总在python控制台运行,十分难受 解决方法 在pycharm中设置下即可,很简单 选择运行点击…...
Spring MVC 二 :基于xml配置
创建一个基于xml配置的Spring MVC项目。 Idea创建新项目,pom文件引入依赖: <dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.2.12.RELEASE</version>…...
springboot aop方式实现接口入参校验
一、前言 在实际开发项目中,我们常常需要对接口入参进行校验,如果直接在业务代码中进行校验,则会显得代码非常冗余,也不够优雅,那么我们可以使用aop的方式校验,这样则会显得更优雅。 二、如何实现…...

解决git上传远程仓库时的大文件提交
在git中超过100M的文件会上传失败,而当一个文件超过50M时会给你警告,如下 warning: File XXXXXX is 51.42 MB; this is larger than GitHubs recommended maximum file size of 50.00 MB 解决这种问题,首先在项目的.git文件夹中找到.gitigno…...

HTML学习笔记02
HTML笔记02 页面结构分析 元素名描述header标题头部区域的内容(用于页面或页面中的一块区域)footer标记脚部区域的内容(用于整个页面或页面的一块区域)sectionWeb页面中的一块独立区域article独立的文章内容aside相关内容或应用…...

<C++> 内存管理
1.C/C内存分布 让我们先来看看下面这段代码 int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] {1, 2, 3, 4};char char2[] "abcd";char *pChar3 "abcd";int *ptr1 (int *) mal…...
【Java】ByteBuffer类的arrayOffset方法详解+示例
arrayOffset功能详解;arrayOffset在position等于0和非0两种场景下的demo。使用类java.nio.ByteBuffer中的arrayOffset()方法可以获得这个缓冲区的第一个元素在底层支持(backing)数组中的偏移量。 如果这个buffer底层是由数组支持的,那么buffer的postion p对应于数组的index…...

【C++】C++ 引用详解 ⑤ ( 函数 “ 引用类型返回值 “ 当左值被赋值 )
文章目录 一、函数返回值不能是 " 局部变量 " 的引用或指针1、函数返回值常用用法2、分析函数 " 普通返回值 " 做左值的情况3、分析函数 " 引用返回值 " 做左值的情况 函数返回值 能作为 左值 , 是很重要的概念 , 这是实现 " 链式编程 &quo…...

Git,分布式版本控制工具
1.为常用指令配置别名(可选) 打开用户目录,创建.bashrc文件 (touch ~/.bashrc) 2.往其输入内容 #用于输出git提交日志 alias git-loggit log --prettyoneline --all --graph --abbrev-commit #用于输出当前目录所有文…...
LeetCode 面试题 02.02. 返回倒数第 k 个节点
文章目录 一、题目二、C# 题解 一、题目 实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。 注意:本题相对原题稍作改动 点击此处跳转题目。 示例: 输入: 1->2->3->4->5 和 k 2 输出: 4 说…...

SpeedBI数据可视化工具:丰富图表,提高报表易读性
数据可视化工具一大作用就是能把复杂数据可视化、直观化,更容易看懂,也就更容易实现以数据驱动业务管理升级,因此一般的数据可视化工具都会提供大量图形化的数据可视化图表,以提高报表的易懂性,更好地服务企业运营决策…...

编写Dockerfile制作Web应用系统nginx镜像
文章目录 题目要求:一、创建文档,编写Dockerfile文件可以将harbor仓库去启动先起来 二、运行Dockerfile,构建nginx镜像三、推送导私有仓库,也就是我们的harbor仓库 题目要求: 编写Dockerfile制作Web应用系统nginx镜像…...
记录一次微服务连接Nacos异常-errorMsg: Illegal character in authority at index 7:
组件信息 Nacos 2.2.3 SpringCloud微服务 部署环境:centerOS 部署方式:k8s 前言 nacos开启鉴权,nacos地址通过变量方式传入服务中 PropsUtil.setProperty(props, "spring.cloud.nacos.discovery.server-addr", "${NACO…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...