当前位置: 首页 > news >正文

力扣1089题 复写零 双指针解法

2. 复写零

给你一个长度固定的整数数组 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]

示例 2:

输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]

算法思路

本题使用双指针算法.

如果[从前往后]进行原地复写的话, 由于0会复写两次, 导致没有被复写的数被[覆盖]掉了. 因此我们使用[从后向前]的复写策略.

算法流程

  1. 初始化两个指针cur = 0, dest = -1

  2. 先找到最后一个复写的数, 使cur指向最后一个复写的数, dest指向从后往前复写的起始位置, 应该是数组的最后一个元素的位置.

    • cur < arr.length时, 一直执行下面的循环:

      • 先判断cur位置的值

        • 如果为0, dest向后移动2步
        • 如果不是0, dest向后移动1步
      • 判断dest是否已经到达数组的最后一个元素的位置, 如果到达了, 就终止循环.

      • cur++, 继续判断

  3. 处理边界情况. 判断dest是否发生越界(dest = arr.length):

    如果发生了越界:

    • 让数组arr[arr.length - 1] = 0
    • cur--
    • dest -= 2
  4. "从后向前"完成复写操作, 只要cur >= 0

    • 判断cur位置的值
      • 如果是0: destdest - 1位置的值改为0, dest -= 2
      • 如果不是0: dest位置的值改为cur位置的值, dest--
    • cur--

Java代码

class Solution {public static void duplicateZeros(int[] arr) {int cur = 0, dest = -1;while (cur < arr.length) {if(arr[cur] == 0) {dest += 2;} else {dest++;}if(dest >= arr.length - 1) {break;}cur++;}if(dest >= arr.length) {arr[arr.length - 1] = 0;dest -= 2;cur--;}while (cur >= 0) {if(arr[cur] == 0) {arr[dest--] = 0;arr[dest--] = 0;cur--;} else {arr[dest--] = arr[cur--];}}}
}

时间复杂度: O(N) 空间复杂度O(1)

相关文章:

力扣1089题 复写零 双指针解法

2. 复写零 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改&#xff0c;不要从函数返回任何东西。 示例 1&…...

Redis基础与运用

一、redis介绍 简介 Redis 是完全开源的&#xff0c;遵守 BSD 协议&#xff0c;是一个高性能的 key-value 数据库。 Redis 与其他 key - value 缓存产品有以下三个特点&#xff1a; Redis支持数据的持久化&#xff0c;可以将内存中的数据保存在磁盘中&#xff0c;重启的时候可…...

PTA:猜帽子游戏 ,C语言

题目 宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子&#xff0c;有的是黑色的&#xff0c;有的是黄色的。每个人可以看到别人头上的帽子&#xff0c;但是看不到自己的。游戏开始后&#xff0c;每个人可以猜自己头上的帽子是什么颜色&#xff0c;或者可以弃权不猜。如…...

ESP32基于IDF框架OTA学习记录

ESP32基于IDF框架OTA学习记录 参考&#xff1a; 空中升级 (OTA) - ESP32 - — ESP-IDF 编程指南 v5.1.1 文档 (espressif.com) 目录 ESP32基于IDF框架OTA学习记录1.分区表2.native_ota_example上手2.1配置分区表2.2配置OTA的bin文件2.3修改esp32的https证书验证方法2.4修改当…...

分布式技术(一)分布式的架构的演进

&#x1f48c; 所属专栏&#xff1a;【微服务】&#x1f600; 作 者&#xff1a;长安不及十里&#x1f4bb; 工作&#xff1a;目前从事电力行业开发&#x1f308; 目标&#xff1a;全栈开发&#x1f680; 个人简介&#xff1a;一个正在努力学技术的Java工程师&#xff0c;专注基…...

webpack 打包优化

在vue.config.js中配置 下载 uglifyjs-webpack-plugin 包 const { defineConfig } require("vue/cli-service"); var path require("path");module.exports defineConfig({transpileDependencies: true,filenameHashing: false, // 去除Vue打包后.cs…...

electron windows robotjs 安装教程

Robotjs 安装 前言第一步 : 安装python第二步 : 安装Visual Studio 2022第三步 : 安装robotjs 前言 robotjs可以控制鼠标键盘&#xff0c;获取屏幕内容&#xff0c;配合electron可做很多自动化操作。windows下配置环境有很多坑&#xff0c;很多文章都太旧了。试了很多次发现了…...

IDEA解决Git冲突详解

目录 前言&#xff1a; 何为冲突 冲突演示 IDEA冲突解决 小结&#xff1a; 前言&#xff1a; 相信大家多多少少都有了解和使用过Git&#xff0c;作为Java程序员idea可谓是无敌的存在了&#xff0c;那么如何使用idea解决Git冲突呢&#xff1f;不瞒大家前段时间在公司把同事…...

Vue3使用kkFileView预览文件pdf

kkFileView - 在线文件预览kkFileView官网 - kkFileView使用Spring Boot搭建&#xff0c;易上手和部署&#xff0c;基本支持主流办公文档的在线预览&#xff0c;如doc,docx,Excel,pdf,txt,zip,rar,图片等等https://kkfileview.keking.cn/zh-cn/docs/usage.html业务场景&#xf…...

建造者模式-C语言实现

UML类图&#xff1a; 代码实现&#xff1a; #include <stdio.h> #include <stdlib.h>// 产品类 typedef struct {char* part1;char* part2;char* part3; } Product;// 抽象建造者类 typedef struct {void (*buildPart1)(void*, const char*);void (*buildPart2)(v…...

Jmeter+influxdb+grafana监控平台在windows环境的搭建

原理&#xff1a;Jmeter采集的数据存储在infuxdb数据库中&#xff0c;grafana将数据库中的数据在界面上进行展示 一、grafana下载安装 Download Grafana | Grafana Labs 直接选择zip包下载&#xff0c;下载后解压即可&#xff0c;我之前下载过比较老的版本&#xff0c;这里就…...

关注这两点 或能避开一些现货黄金交易的陷阱

在现货黄金投资中&#xff0c;交易机会是处处都有&#xff0c;但是亏损的情况也可能出现。投资者要在陷阱处处的市场中获得稳定盈利&#xff0c;就需要懂得如何规避现货黄金投资的陷阱。下面我们就来介绍两个很常用的避开陷阱的方法。 看交易的活跃度。交易越活跃&#xff0c;市…...

Python 文件读写

Python 文件读写笔记整理 参数说明 open(path, flag[, encoding][,errors]) path:要打开文件的路径 flag:打开方式 encoding:编码方式 errors:错误处理 Flag打开方式表 模式 描述 r 以只读方式打开文件。文件的指针将会放在文件的开头。这是默认模式。 rb 以二进制格…...

线性分组码的奇偶校验矩阵均匀性分析

回顾信道编解码知识&#xff0c;我们知道信道编码要求编码具有检纠错能力&#xff0c;作为FEC&#xff08;forward error correction&#xff09;前向纠错编码的一类&#xff0c;线性分组码表示校验位与信息位的关系能够线性表示。 在这篇文章中&#xff0c;并不是要讨论信道编…...

leetcode算法之链表

目录 1.两数相加2.两两交换链表中的节点3.重排链表4.合并K个升序链表5.K个一组翻转链表 1.两数相加 两数相加 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(…...

2023.11.27 滴滴P0级故障或为k8s升级造成

滴滴11.27 P0级故障|打车|宕机|网约车|出租车|滴滴出行|系统故障_网易订阅 (163.com) 如何看待滴滴11月27日故障&#xff0c;对日常生产生活有哪些影响&#xff1f; - 知乎 (zhihu.com) 最新消息滴滴P0故障原因&#xff0c;是由于k8s集群升级导致的&#xff0c;后面又进行版本…...

Ubuntu16.04.4系统本地提权实验

目录 1.介绍&#xff1a; 2.实验&#xff1a; 3.总结&#xff1a; 1.介绍&#xff1a; 1.1&#xff1a;eBPF简介&#xff1a;eBPF(extendedBerkeleyPacketFilter)是内核源自于BPF的一套包过滤机制&#xff0c;BPF可以理解成用户与内核之间的一条通道&#xff0c;有非常强大的…...

Vue中使用正则表达式进行文本匹配和处理的方法

1. 正则表达式基础 正则表达式是一种用来匹配字符串的模式。它由普通字符&#xff08;例如字符 a 到 z&#xff09;和特殊字符&#xff08;称为"元字符"&#xff09;组成。以下是一些基本的正则表达式示例&#xff1a; 匹配邮箱的正则表达式&#xff1a; /^[\w-](\…...

php许愿墙代码包括前端和后端部分

以下是一个简单的PHP许愿墙代码示例&#xff0c;包括前端和后端部分&#xff1a; 前端HTML代码&#xff08;index.html&#xff09;&#xff1a; <!DOCTYPE html> <html> <head><title>许愿墙</title> </head> <body><h1>许…...

PHP 刷新缓存区的问题!

PHP流式输出&#xff0c;在Nginx下可以正常刷新缓存区 &#xff0c; 但是在Apache下会等待循环全部执行完&#xff0c;才会刷新&#xff01;有怎么解决&#xff1f; header(X-Accel-Buffering: no); // Nginx情况下必须加这一行header(Content-type: text/event-stream);header…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...