LeetCode每日一题之 移动0

前言:

  我的每日一题专栏正式开始更新,我会分享关于我在LeetCode上刷题时的经验,将经典题型拿出来详细讲解,来提升自己及大家的算法能力,希望这篇博客对大家有帮助。

题目介绍: 

题目链接:. - 力扣(LeetCode)

算法原理:

  很明显这是一类数组划分的题目,那么这类题目常用解法,可以使用双指针法,注意这里提到的双指针是下标(索引),不是c语言中的指针。

  总所周知,两个指针会将整个数组分为3个区域,如下图:

 如果我们我们能将数组的元素,按如下图划分:

 也就是dest指向已处理的非0元素的最后一个,cur指向未处理元素的第一个,按照这样的规则走下去,当cur走到数组末端的时候,整个数组就变成了我们想要的样子。

那么如何遵循这样的规则往下走了,就是我们的算法体现了,看下面这个例子:

两个指针初始状态:

dest   -1  (dest指向已处理的最后一个元素,现在没有已处理的元素,所以指向-1)

cur  0 (cur要遍历整个数组,所以从0开始)

 下面介绍每个指针的行动规则:

cur:cur遇到0,cur++

dest:cur遇到非0,++dest,然后交换dest和cur对应的值,交换完后cur++

下面用上面的例子走一遍:

cur遇到第一个元素0,cur++:

cur遇到第二个元素1,非0, ++dest,然后交换dest和cur对应的值再cur++:

其实不难看出这已经到了我们上面的理想状态了,区域1是已处理的元素,区域2是0,区域3是未处理的,且dest指向已处理元素的最后一个,cur指向未处理元素的第一个。

继续, cur遇到第三个元素0,cur++:

 

cur遇到第四个元素3,非0, ++dest,然后交换dest和cur对应的值再cur++: 

 

cur遇到第五个元素0,cur++: 

cur遇到第六个元素12,非0, ++dest,然后交换dest和cur对应的值再cur++:  

此时cur走到数组末端,结束,该数组也被我们处理完毕。 

代码实现:

 c语言:

void swap(int* a,int* b)//交换函数
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void moveZeroes(int* nums, int numsSize) {
    int dest=-1,cur=0;//两个指针的初始位置
    while(cur<numsSize)
    {
        if(nums[cur]!=0)//遇到非0时
        {
            ++dest;
            swap(&nums[dest],&nums[cur]);
        }
        cur++;//无论怎样cur都需要++,所以可以直接写在这
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/425713.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

23端口登录的Telnet命令+传输协议FTP命令

一、23端口登录的Telnet命令 Telnet是传输控制协议/互联网协议&#xff08;TCP/IP&#xff09;网络&#xff08;如Internet&#xff09;的登录和仿真程序&#xff0c;主要用于Internet会话。基本功能是允许用户登录进入远程主机程序。 常用的Telnet命令 Telnet命令的格式为&…

图文详解:在虚拟机上安装Win7,超详细!!!

一.准备 1.虚拟机&#xff1a; https://pan.xunlei.com/s/VNpZ_9c2AdrnUW1YWNdhBLW-A1?pwdyp6b# 2.win7的iOS&#xff1a; https://pan.xunlei.com/s/VNpZd61K6a7cDG3YkI_3oVbUA1?pwdyrfp# 二.安装配置 三.配置Win7 1.记得输入原先下载的镜像文件 2.那我们选择自定义 3…

亚信安慧AntDB:打破数据孤岛,实现实时处理

AntDB数据库以其独特的创新能力在分布式数据库领域引领潮流。其中&#xff0c;融合统一与实时处理是其两大核心创新能力&#xff0c;为其赢得广泛关注与赞誉。融合统一意味着AntDB能够将多种不同类型的数据库融合为一体&#xff0c;实现数据的统一管理与处理&#xff0c;极大地…

3.3作业

1、图片拷贝 #include <stdio.h> #include <sys/types.h> #include <unistd.h> #include <stdlib.h> #include <pthread.h> #include <sys/stat.h> #include <fcntl.h>typedef struct xccpy {int num;off_t size;int fd_r;int fd_w…

CSS锥形渐变:conic-gradient()

画一个扇形图&#xff0c;使用常规方法可能很难画&#xff0c;但是用锥形渐变的话非常好画 <style>.pattern{width: 100px; height: 100px;border-radius: 50%;background: conic-gradient(yellow 30deg , black 30deg , black 90deg , yellow 90deg ,yellow 150d…

MongoDB 使用教程

座右铭&#xff1a;怎么简单怎么来&#xff0c;以实现功能为主。 欢迎大家关注公众号与我交流 使用方法&#xff1a; 1、MongoDB 帮助 ------- db.help() 2、Mongodb 统计信息 ------ db.stats() 刚安装上的MongoDB &#xff0c;默认默认的数据库为test&#xff0c;这个时候…

两天学会微服务网关Gateway-Gateway工作原理

锋哥原创的微服务网关Gateway视频教程&#xff1a; Gateway微服务网关视频教程&#xff08;无废话版&#xff09;_哔哩哔哩_bilibiliGateway微服务网关视频教程&#xff08;无废话版&#xff09;共计17条视频&#xff0c;包括&#xff1a;1_Gateway简介、2_Gateway工作原理、3…

uniapp 微信小程序使用高德地图Vue3不兼容Vue2问题

1. uniapp 微信小程序使用高德地图Vue3不兼容Vue2问题 1.1. 问题 uniapp Vue3项目引用高德地图报错 import amapPlugin from ‘…/…/…/js_sdk/js_amap/amap-wx.130’; "default" is not exported by "../../../MyProject/Base/Szy/js_sdk/js_amap/amap-wx.1…

3.2日-线性模型,基础优化方法,线性回归从零开始实现

3.2日-线性模型&#xff0c;基础优化方法&#xff0c;线性回归从零开始实现 1线性模型衡量预估质量训练数据总结2基础优化方法3 线性回归从零开始实现 1线性模型 衡量预估质量 训练数据 总结 2基础优化方法 梯度下降是一种优化算法&#xff0c;常用于机器学习和深度学习中&…

#WEB前端(浮动与定位)

1.实验&#xff1a; 2.IDE&#xff1a;VSCODE 3.记录&#xff1a; float、position 没有应用浮动前 应用左浮动和右浮动后 应用定位 4.代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><me…

基于ZYNQ的PCIE高速数据采集卡的设计(一)

作为信息处理的第一步&#xff0c;数据采集的作用越来越重要。目前&#xff0c;数据采集已经在航 空、民用、军事、医疗等领域得到广泛应用。随着相关技术的不断发展&#xff0c;信号频率越 来高&#xff0c;带宽越来越大&#xff0c;使得数据采集技术逐渐向高速大数据的方向…

位运算---求n的二进制表示中第k位是1还是0 (lowbit)

操作&#xff1a; 先把第k位移到最后一位&#xff08;右边第一位&#xff09; 看个位是1还是0 lowbit(x)&#xff1a;返回x的最右边的1。 原理&#xff1a; 其中 &#xff0c;意思是 是 的补码。 就可以求出最右边的一位1。 应用&#xff1a; 当中 的个数。 int re…

【创作回顾】17个月峥嵘创作史

#里程碑专区#、#创作者纪念日# 还记得 2022 年 10 月 05 日&#xff0c;我在CSDN撰写了第 1 篇博客——《关于测试工程师瓶颈和突围的一个思考》&#xff0c;也是我在全网发布的第一篇技术文章。 回想当时&#xff0c;这一篇的诞生过程并不轻松&#xff0c;不像是一篇网络文章…

昇腾ACL应用开发之硬件编解码dvpp

1.前言 在我们进行实际的应用开发时&#xff0c;都会随着对一款产品或者AI芯片的了解加深&#xff0c;大家都会想到有什么可以加速预处理啊或者后处理的手段&#xff1f;常见的不同厂家对于应用开发的时候&#xff0c;都会提供一个硬件解码和硬件编码的能力&#xff0c;这也是抛…

JetBrains Gateway Github Copilot 客户端插件和主机插件

JetBrains Gateway可以通过插件支持Github Copilot&#xff08;需另行注册&#xff09;。 需要安装插件 客户端&#xff0c;而非插件 主机&#xff0c;如图所示&#xff1a; 大概是因为代码显示在客户端&#xff08;运行在本地的IDE&#xff09;&#xff1f;

新王炸:文生视频Sora模型发布,能否引爆AI芯片热潮

前言 前方高能预警&#xff0c;Sora来袭&#xff01; 浅析Sora的技术亮点 语言模型中构建关键词联系 视频素材分解为时空碎片 扩散模型DiT Not for play, But change world! OpenAI的宏大目标 未来已来&#xff0c;只是尚未流行 Sora的成本与OpenAI的7万亿美金豪赌 算…

基于阿里云OSS上传图片实战案例

一、案例描述 基于Springboot框架实现一个上传图片到阿里云服务端保存的小案例。 二、准备工作 基于Springboot免费搭载轻量级阿里云OSS数据存储库&#xff08;将本地文本、照片、视频、音频等上传云服务保存&#xff09;-CSDN博客 三、代码 新建这两个类&#xff1a;一个…

Qt开发 显示类控件

Label QLabel 可以用来显示文本和图片 核心属性如下 属性说明textQLabel 中的文本textFormat文本的格式&#xff1a;Qt::PlainText 纯文本Qt::RichText 富文本(支持 html 标签)Qt::MarkdownText markdown 格式Qt::AutoText 根据文本内容自动决定文本格式.pixmapQLabel 内部包…

贪心算法(区间问题)

452. 用最少数量的箭引爆气球 题目(求无重复区间) 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points &#xff0c;其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着…

【保姆级教程】如何订阅patreon?patreon订阅需要银行卡?patreon虚拟信用卡购买支付教程

1. 引言 什么是Patreon&#xff1a; Patreon是一个在线平台&#xff0c;允许内容创作者通过订阅服务的模式从他们的粉丝那里直接获得资金或者打赏。 这个平台支持各种创作者&#xff0c;包括艺术家、音乐家、作家、视频制作人等。 他们通过定期发布独家内容&#xff0c;然后粉丝…