【算法专题突破】双指针 - 复写零(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…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...

【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...