Leetcode每日刷题之 1089. 复写零(C++)

embedded/2024/9/23 13:25:29/

1. 题目解析

由题目可知,我们需要将给定数组中的所有零复写一遍,并且保证不能超出数组长度,还不可以开辟新的数组,要在原数组的位置直接操作

 

2. 算法原理

1. 由题目我们可以将问题简化为找出最终复写完成数组的最后一个元素,然后从该元素由后      向前在原数组依次复写遇到的零元素即可

2. 所以我们首先的目标就是找出复写完成后的数组最后的一个元素是什么,那么我们可以使      用双指针的方法,即一个为快指针一个为慢指针, cur 从头开始作为慢指针向后遍历,          dest 作为快指针由 - 1 位置开始向后遍历,当 cur 指针遇见非零元素则两个指针都向后移      一步,如果 cur 指针遇见了零元素,那么就将 cur 元素向后移一步,将 dest 指针向后移      两步,直到 dest 指向数组的末尾,那么这时的 cur 指针指向的元素就是复写后的数组的      最后一个元素

3. 当然需要注意不可以越,界访问,即当 dest 指针指向了数组末尾的下一个位置,这时就        不能直接对 dest 指针指向的区域操作赋值,所以我们可以直接将数组末尾元素赋值为0,      然后根据 cur 指针当前指向的元素进行 dest 指针的移动即可

 

class Solution 
{
public:void duplicateZeros(vector<int>& arr) {int cur = 0;int dest = -1;int n = arr.size();//1. 找到最终数组的最后一个元素while(cur < n){if(arr[cur]){dest++;}else{dest += 2;}if(dest >= n - 1){break;}cur++;}//2. 处理越界情况if(dest == n){arr[n - 1] = 0;cur--;dest -= 2;}//3.复写零while(cur >= 0){if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

 

3. 代码实现

 


http://www.ppmy.cn/embedded/94918.html

相关文章

Linux Shell基础常用脚本命令及应用案例

文章目录 常用的 Shell 命令1. 变量2. 注释3. 输出4. 输入5. 条件判断6. 循环7. 函数8. 运算9. 流程控制10. 文件和目录操作11. 错误处理 Shell 脚本应用案例1. Hello World 脚本2. 创建系统账户及设置密码3. 日志文件备份4. 一键部署 LNMP 环境5. 检查磁盘空间6. 自动安装软件…

linux HBA驱动中scsi_host_template .shost_attrs

在Linux内核中&#xff0c;SCSI&#xff08;Small Computer System Interface&#xff09;是一种用于连接计算机和外围设备的接口。scsi_host_template是一个结构体&#xff0c;用于定义SCSI主机&#xff08;host adapter&#xff09;的属性和操作。这个模板用于初始化SCSI主机…

3. MQTT协议的架构

1 MQTT协议的层次结构 MQTT协议的架构设计简洁&#xff0c;主要由三个部分组成&#xff1a;客户端、代理和消息。理解这些组件及其交互是掌握MQTT协议的关键。 1.1 客户端&#xff08;Client&#xff09; 客户端是MQTT协议的核心组成部分&#xff0c;分为发布者和订阅者两种…

【vue3|第20期】vue3中Vue Router路由器工作模式

日期&#xff1a;2024年8月6日 作者&#xff1a;Commas 签名&#xff1a;(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释&#xff1a;如果您觉得有所帮助&#xff0c;帮忙点个赞&#xff0c;也可以关注我&#xff0c;我们一起成长&#xff1b;如果有不对的地方&#xff…

生活生鲜超市小程序系统开发方案

生活生鲜超市小程序系统是集商品浏览、在线下单、支付结算、物流配送、会员管理等功能于一体。是为了满足现代消费者对新鲜食品购买的便利性与即时性需求。 适用于&#xff1a;生鲜超市、百货、连锁、水果、批发、便民、果蔬、食品、食材、鲜果、特产、海鲜等店铺。一、目标用户…

Redis相关介绍

本文介绍了Redis&#xff0c;一种开源的内存数据结构存储系统&#xff0c;强调其高性能、多种数据结构支持、内存存储、持久化策略、发布订阅功能及工作原理。 Redis的介绍 Redis&#xff08;Remote Dictionary Server&#xff09;&#xff0c;即远程字典服务&#xff0c;是一…

vue RSA加密解密(解决加密过长,解密过长返回为null的问题)

1安装 npm i jsencrypt2.rsa.js /* 引入jsencrypt实现数据RSA加密 */ import JSEncrypt from jsencrypt // 处理长文本数据时报错 jsencrypt.js Message too long for RSA /* 引入encryptlong实现数据RSA加密 */ //import Encrypt from encryptlong // encryptlong是基于jsen…

计算机视觉入门:OpenCV 人脸检测技术简介

计算机视觉入门&#xff1a;OpenCV 人脸检测技术简介 计算机视觉是让计算机“看”并理解图像或视频内容的技术领域。它在许多应用中扮演着重要角色&#xff0c;如自动驾驶、医疗影像分析和视频监控等。在计算机视觉中&#xff0c;人脸检测是一项基础而关键的技术&#xff0c;其…