L28.【LeetCode笔记】移动零(三种解法)
目录
1.题目
2.向前覆盖法
分析
代码
提交结果
3.优解:双指针
代码
提交结果
4.其他不符合题意的方法:使用队列
代码
提交结果
1.题目
https://leetcode.cn/problems/move-zeroes/description/
给定一个数组
nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]示例 2:
输入: nums =[0]输出:[0]提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1进阶:你能尽量减少完成的操作次数吗?
2.向前覆盖法
分析
设一指针ptr,从头到尾遍历数组,发现num[ptr]==0时,执行向前覆盖,尾部填充一个0,但如果只这样写会有问题!
例如测试数据[0,0,1,0]

移动一次后发现1前面的元素nums[ptr-1]==0,即没有完全移动好1,那么这种情况出现时ptr要--
写成下面这样可以吗?
if (nums[ptr-1]==0)ptr--;
不行会有潜在的越界风险! ptr-1可能会<0,因此要写成
if (ptr>=1&&nums[ptr-1]==0)ptr--;
代码
void moveZeroes(int* nums, int numsSize)
{int ptr=0;while(ptr<=numsSize-1){if (ptr>=1&&nums[ptr-1]==0)ptr--;if (0==nums[ptr]){ for (int i=ptr;i<numsSize-1;i++){nums[i]=nums[i+1];}nums[numsSize-1]=0;numsSize--;} ptr++;}
}
提交结果

3.优解:双指针
LeetCode官方题解的双指针有点不好理解,其实可以直接分类讨论指针所指向的值:设两个指针prev和cur,当初始prev==0,cur==1时(先排除数组元素只有一个的情况),它们指向元素的情况无非就四种
1.nums[prev]==0,nums[cur]==0
2.nums[prev]!=0,nums[cur]==0
3.nums[prev]!=0,nums[cur]!=0
4.nums[prev]==0,nums[cur]!=0
首先看4:这种情况最好处理,nums[prev]交换nums[cur]就能将0向后移动
剩下情况1,情况2,情况3都要遵循一个原则:想方设法转换为情况4
情况1:nums[prev]==0,nums[cur]==0 --转换--> nums[prev]==0,nums[cur]!=0 :cur++寻找nums[cur]!=0
情况2:nums[prev]!=0,nums[cur]==0 --转换--> nums[prev]==0,nums[cur]!=0 :prev和cur都++
情况3:nums[prev]!=0,nums[cur]!=0 --转换--> nums[prev]==0,nums[cur]!=0 :附近没有0,prev和cur都++
代码
void moveZeroes(int* nums, int numsSize)
{if(numsSize==1)return;int prev=0;int cur=1;while (cur<numsSize){if (nums[prev]==0&&nums[cur]!=0){int tmp=nums[prev];nums[prev]=nums[cur];nums[cur]=tmp;}if (nums[prev]!=0&&nums[cur]!=0){prev++;}if (nums[prev]!=0&&nums[cur]==0){prev++;}cur++;}
}
提交结果

4.其他不符合题意的方法:使用队列
虽然使用队列并没有原地对数组操作,但可以锻炼对队列的使用(其实直接开辟一个临时数组就行)
思想:将非0数字依次入队,遍历完一遍数组后再依次出队,原数组末尾补0
有关队列的文章参见:98.【C语言】数据结构之队列
代码
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL)pq->tail = NULL;pq->size--;
}bool QueueEmpty(Queue* pq)
{return pq->size == 0;
}QDataType QueueFront(Queue* pq)
{return pq->head->data;
}void moveZeroes(int* nums, int numsSize)
{Queue q;QueueInit(&q);for (int i=0;i<numsSize;i++){if (nums[i]!=0){QueuePush(&q,nums[i]);}}int j=0;while(!QueueEmpty(&q)){nums[j]=QueueFront(&q);QueuePop(&q);j++;}for (;j<numsSize;j++){nums[j]=0;}QueueDestroy(&q);
}
提交结果

相关文章:
L28.【LeetCode笔记】移动零(三种解法)
目录 1.题目 2.向前覆盖法 分析 代码 提交结果 3.优解:双指针 代码 提交结果 4.其他不符合题意的方法:使用队列 代码 提交结果 1.题目 https://leetcode.cn/problems/move-zeroes/description/ 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾…...
jenkins入门10--自动化构建
build periodically:设定类似cron周期性时间触发构建 * * * * * (五颗星,中间用空格隔开) 第一颗表示分钟,取值0~59 第二颗表示小时,取值0~23 第三颗表示一个月的第几天,取值1~31 第四颗表示第几月…...
el-table拖拽表格
1、拖拽插件安装 npm i -S vuedraggable // vuedraggable依赖Sortable.js,我们可以直接引入Sortable使用Sortable的特性。 // vuedraggable是Sortable的一种加强,实现组件化的思想,可以结合Vue,使用起来更方便。 2、引入拖拽函数…...
如何轻松反转C# List<T>中的元素顺序
在C#中,有多种方法可以反转 List<T> 的元素顺序。以下是几种常见的方法: 方法一:使用 List<T>.Reverse 方法 List<T> 类提供了一个内置的 Reverse 方法,可以就地反转列表中的元素顺序。 using System; using…...
Transformer中Self-Attention以及Multi-Head Attention模块详解(附pytorch实现)
写在前面 最近在项目中需要使用Transformer模型来处理图像任务,所以稍微补充一下这部分的知识,本篇主要了解一下Self-Attention以及Multi-Head Attention模块。 原论文链接:https://arxiv.org/pdf/1706.03762 原文代码:tensor2…...
在Nvidia Jetson ADX Orin中使用TensorRT-LLM运行llama3-8b
目录 背景:步骤 1.获取模型权重第 2 步:准备第 3 步:构建 TensorRT-LLM 引擎 背景: 大型语言模型 (LLM) 推理的关键瓶颈在于 GPU 内存资源短缺。因此,各种加速框架主要强调减少峰值 GPU 内存使…...
六十一:HTTP/2的问题及HTTP/3的意义
随着互联网的快速发展,网络协议的升级成为优化用户体验和提升网络效率的重要手段。HTTP/2 于 2015 年发布,标志着超文本传输协议的重大改进。然而,尽管 HTTP/2 带来了许多新特性,它也存在一定的问题。在此背景下,HTTP/…...
IOS开发如何从入门进阶到高级
针对iOS开发的学习,不同阶段应采取不同的学习方式,以实现高效提升.本文将iOS开发的学习分为入门、实战、进阶三个阶段,下面分别详细介绍. 一、学习社区 iOS开源中国社区 这个社区专注于iOS开发的开源项目分享与协作,汇集了大量开…...
非一般的小数:小数的概念新解、小数分类、浮点数的存储
非一般的小数:小数的概念新解、小数分类、浮点数的存储 一、小数的概念二、小数的分类1.有限小数、无限循环小数、无限不循环小数2.纯小数、带小数3.定点数、浮点数 三、浮点数的存储 一、小数的概念 这还用解释吗?小…...
关于游戏销量的思考
1、黑神话达到2300万套,分析师上调预期到超过100亿营收。 以往的我的世界、小鸟、超级食肉男孩等游戏也都是几千万,上亿的销量。 也改变了相关开发者的命运。 一个开发者,卖出一个30万,或100万销量的作品,就足够改变…...
JuiceFS 详解:一款为云原生设计的高性能分布式文件系统
JuiceFS 详解:一款为云原生设计的高性能分布式文件系统 1. 什么是 JuiceFS? JuiceFS(Juiced File System)是一款高性能、POSIX 兼容的云原生分布式文件系统。它采用对象存储作为底层存储,支持多种元数据引擎…...
百度Android面试题及参考答案 (下)
Executorservice 和 Executor 有什么区别? Executor 接口 Executor 是一个简单的接口,它定义了一个方法execute(Runnable command)。这个接口的主要目的是将任务的提交和任务的执行分离,它提供了一种通用的方式来执行一个Runnable任务,但是它没有提供更多高级的功能,比如任…...
RK3588+FPGA全国产异步LED显示屏控制卡/屏幕拼接解决方案
RK3588FPGA核心板采用Rockchip RK3588新一代旗舰 级八核64位处理器,支持8K视频编解码,多屏4K输出,可实现12屏联屏拼接、同显、异显,适配多种操作系统,广泛适用于展览展示、广告内容投放、新零售、商超等领域实现各种媒…...
Elasticsearch:Query rules 疑难解答
作者:来自 Elastic Kathleen_DeRusso 查询规则(Query rules)为用户提供了一种对特定查询进行细粒度控制的方法。目前,查询规则的功能允许你将你选择的搜索结果固定在结果集的顶部,和/或根据上下文查询数据从结果集中排…...
四、VSCODE 使用GIT插件
VSCODE 使用GIT插件 一下载git插件与git Graph插件二、git插件使用三、文件提交到远程仓库四、git Graph插件 一下载git插件与git Graph插件 二、git插件使用 git插件一般VSCode自带了git,就是左边栏目的图标 在下载git软件后vscode的git插件会自动识别当前项目 …...
键盘鼠标共享工具Barrier(kail与windows操作系统)
键鼠共享工具Barrier(kail与windows操作系统)_barrier软件-CSDN博客 sudo apt install barrier...
QTcpSocket 中设置接收缓冲区大小
在 QTcpSocket 中设置接收缓冲区大小 使用setSocketOption方法 在QTcpSocket类中,可以使用setSocketOption函数来设置接收缓冲区大小。具体来说,对于 TCP 套接字,你可以使用QAbstractSocket::ReceiveBufferSizeSocketOption选项。以下是一个简…...
Arduino IDE刷微控制器并下载对应固件的原由
在使用Arduino IDE刷写某个微控制器时,下载对应的固件通常是为了确保微控制器能够正确识别和执行Arduino IDE中编写的代码。以下是对这一过程的详细解释: 一、固件的作用 固件是微控制器或嵌入式设备上运行的软件,它负责控制硬件设备的操作…...
Jurgen提出的Highway Networks:LSTM时间维方法应用到深度维
Jurgen提出的Highway Networks:LSTM时间维方法应用到深度维 具体实例与推演 假设我们有一个离散型随机变量 X X X,它表示掷一枚骰子得到的点数,求 X X X 的期望。 步骤: 列出 X X X 的所有可能取值 x i x_i xi(…...
Netron可视化深度学习的模型框架,大大降低了大模型的学习门槛
深度学习是机器学习的一个子领域,灵感来源于人脑的神经网络。深度学习通过多层神经网络自动提取数据中的高级特征,能够处理复杂和大量的数据,尤其在图像、语音、自然语言处理等任务中表现出色。常见的深度学习模型: 卷积神经网络…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
