力扣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会复写两次, 导致没有被复写的数被[覆盖]掉了. 因此我们使用[从后向前]的复写策略.
算法流程
-
初始化两个指针
cur = 0,dest = -1 -
先找到最后一个复写的数, 使
cur指向最后一个复写的数,dest指向从后往前复写的起始位置, 应该是数组的最后一个元素的位置.-
当
cur < arr.length时, 一直执行下面的循环:-
先判断
cur位置的值- 如果为
0,dest向后移动2步 - 如果不是
0,dest向后移动1步
- 如果为
-
判断
dest是否已经到达数组的最后一个元素的位置, 如果到达了, 就终止循环. -
cur++, 继续判断
-
-
-
处理边界情况. 判断
dest是否发生越界(dest = arr.length):如果发生了越界:
- 让数组
arr[arr.length - 1] = 0 cur--dest -= 2
- 让数组
-
"从后向前"完成复写操作, 只要
cur >= 0- 判断
cur位置的值- 如果是
0:dest和dest - 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 ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。 示例 1&…...
Redis基础与运用
一、redis介绍 简介 Redis 是完全开源的,遵守 BSD 协议,是一个高性能的 key-value 数据库。 Redis 与其他 key - value 缓存产品有以下三个特点: Redis支持数据的持久化,可以将内存中的数据保存在磁盘中,重启的时候可…...
PTA:猜帽子游戏 ,C语言
题目 宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子,有的是黑色的,有的是黄色的。每个人可以看到别人头上的帽子,但是看不到自己的。游戏开始后,每个人可以猜自己头上的帽子是什么颜色,或者可以弃权不猜。如…...
ESP32基于IDF框架OTA学习记录
ESP32基于IDF框架OTA学习记录 参考: 空中升级 (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修改当…...
分布式技术(一)分布式的架构的演进
💌 所属专栏:【微服务】😀 作 者:长安不及十里💻 工作:目前从事电力行业开发🌈 目标:全栈开发🚀 个人简介:一个正在努力学技术的Java工程师,专注基…...
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可以控制鼠标键盘,获取屏幕内容,配合electron可做很多自动化操作。windows下配置环境有很多坑,很多文章都太旧了。试了很多次发现了…...
IDEA解决Git冲突详解
目录 前言: 何为冲突 冲突演示 IDEA冲突解决 小结: 前言: 相信大家多多少少都有了解和使用过Git,作为Java程序员idea可谓是无敌的存在了,那么如何使用idea解决Git冲突呢?不瞒大家前段时间在公司把同事…...
Vue3使用kkFileView预览文件pdf
kkFileView - 在线文件预览kkFileView官网 - kkFileView使用Spring Boot搭建,易上手和部署,基本支持主流办公文档的在线预览,如doc,docx,Excel,pdf,txt,zip,rar,图片等等https://kkfileview.keking.cn/zh-cn/docs/usage.html业务场景…...
建造者模式-C语言实现
UML类图: 代码实现: #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环境的搭建
原理:Jmeter采集的数据存储在infuxdb数据库中,grafana将数据库中的数据在界面上进行展示 一、grafana下载安装 Download Grafana | Grafana Labs 直接选择zip包下载,下载后解压即可,我之前下载过比较老的版本,这里就…...
关注这两点 或能避开一些现货黄金交易的陷阱
在现货黄金投资中,交易机会是处处都有,但是亏损的情况也可能出现。投资者要在陷阱处处的市场中获得稳定盈利,就需要懂得如何规避现货黄金投资的陷阱。下面我们就来介绍两个很常用的避开陷阱的方法。 看交易的活跃度。交易越活跃,市…...
Python 文件读写
Python 文件读写笔记整理 参数说明 open(path, flag[, encoding][,errors]) path:要打开文件的路径 flag:打开方式 encoding:编码方式 errors:错误处理 Flag打开方式表 模式 描述 r 以只读方式打开文件。文件的指针将会放在文件的开头。这是默认模式。 rb 以二进制格…...
线性分组码的奇偶校验矩阵均匀性分析
回顾信道编解码知识,我们知道信道编码要求编码具有检纠错能力,作为FEC(forward error correction)前向纠错编码的一类,线性分组码表示校验位与信息位的关系能够线性表示。 在这篇文章中,并不是要讨论信道编…...
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日故障,对日常生产生活有哪些影响? - 知乎 (zhihu.com) 最新消息滴滴P0故障原因,是由于k8s集群升级导致的,后面又进行版本…...
Ubuntu16.04.4系统本地提权实验
目录 1.介绍: 2.实验: 3.总结: 1.介绍: 1.1:eBPF简介:eBPF(extendedBerkeleyPacketFilter)是内核源自于BPF的一套包过滤机制,BPF可以理解成用户与内核之间的一条通道,有非常强大的…...
Vue中使用正则表达式进行文本匹配和处理的方法
1. 正则表达式基础 正则表达式是一种用来匹配字符串的模式。它由普通字符(例如字符 a 到 z)和特殊字符(称为"元字符")组成。以下是一些基本的正则表达式示例: 匹配邮箱的正则表达式: /^[\w-](\…...
php许愿墙代码包括前端和后端部分
以下是一个简单的PHP许愿墙代码示例,包括前端和后端部分: 前端HTML代码(index.html): <!DOCTYPE html> <html> <head><title>许愿墙</title> </head> <body><h1>许…...
PHP 刷新缓存区的问题!
PHP流式输出,在Nginx下可以正常刷新缓存区 , 但是在Apache下会等待循环全部执行完,才会刷新!有怎么解决? header(X-Accel-Buffering: no); // Nginx情况下必须加这一行header(Content-type: text/event-stream);header…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
