【双指针】:Leetcode283.移动零

朋友们、伙计们,我们又见面了,本专栏是关于各种算法的解析,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

C 语 言 专 栏:C语言:从入门到精通

数据结构专栏:数据结构

个  人  主  页 :stackY、

C + + 专 栏   :C++

Linux 专 栏  :Linux

目录

1. 双指针思想

2. 移动零

2.1 题目解析

2.2 算法思路

2.3 代码实现


1. 双指针思想

常见的双指针有两种形式:一种是对撞指针、一种是快慢指针

1. 对撞指针:一般位于顺序结构中,也被称为左右指针。

  • 对撞指针从两端向中间移动,⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终⽌条件⼀般是两个指针相撞或者错开(也可能在循环内部找到结果直接跳出循环),也就是:

                left==right(两个指针相撞)

                left>rigth(两个指针错开)

2. 快慢指针:⼜称为⻳兔赛跑算法,其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

  • 这种⽅法对于处理环形链表或数组以及循环往复的问题⾮常有⽤。
  • 快慢指针的实现⽅式有很多种,最常⽤的⼀种就是:
  • 在⼀次循环中,每次让慢的指针向后移动⼀位,⽽快的指针往后移动两位,实现⼀快⼀慢。

2. 移动零

Leetcode283.移动零:https://leetcode.cn/problems/move-zeroes/

题目描述:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]输出: [0]

2.1 题目解析

根据题目描述,通过区间的划分对数组进行操作,可以简单的理解为将整个数组划分为两块,「数组分两块」是⾮常常⻅的⼀种题型,主要就是根据⼀种划分⽅式,将数组的内容分成左右两部分。这种类型的题,⼀般就是使⽤「双指针」来解决。

2.2 算法思路

解决本题使用的是双指针算法:

在这里为了方便,可以直接使用数组的下标来进行指针的模拟,要想对数组进行分块,首先设置一个指针(cur)对数组进行遍历,要将非0放到左边还需要一个指针(dest)来对数组进行区域划分,那么这两个指针的作用分别是:

cur:从左向右扫描,遍历整个数组。

dest:已处理区间内,非0元素的最后一个位置。

在遍历的整个过程中这两个指针会将数组分为三个区间:

如何实现呢?

首先让cur和dest都指向数组的起始位置(或者让dest指向-1的位置),然后让cur指针向后遍历,这时cur指针会遇到两种情况:

1. 遇到0时,直接++cur,继续向后面走。

2. 遇到非0时,需要交换dest位置与cur位置的元素,然后再将dest和cur加1。

结束的条件cur遍历完整个数组。

2.3 代码实现

使用最简单的循环语句即可完成遍历和判断:

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        int cur = 0, dest = 0;
        for(;cur < nums.size(); cur++)
        {
            if(nums[cur])  //非0再交换
                swap(nums[dest++], nums[cur]);  //后置++,使用完了再++进行迭代
            //为0就继续向后面迭代
        }
    }
};

算法小总结:

数组分块,区间划分是在快速排序算法 中也有提到的,快速排序算法的关键就是进行区间的划分。

朋友们、伙计们,美好的时光总是短暂的,我们本期算法的分享就到此结束,欲知后事如何,请听下回分解~,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!  

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

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

相关文章

[数据结构]—带头双向循环链表——超详解

&#x1f493;作者简介&#x1f389;&#xff1a;在校大二迷茫大学生 &#x1f496;个人主页&#x1f389;&#xff1a;小李很执着 &#x1f497;系列专栏&#x1f389;&#xff1a;数据结构 每日分享✨&#xff1a;旅行是为了迷路&#xff0c;迷路是为了遇上美好❣️❣️❣️ …

Git的基本操作以及原理介绍

文章目录 基本操作创建git仓库配置name和email .git目录的结构git add & git commit.git目录结构的变化 git追踪管理的数据git的版本回退回退的原理回退的三种情况 版本库中文件的删除git分支管理分支的删除合并分支时的冲突分支的合并模式分支策略git stash不要在master分…

数据结构-时间复杂度与空间复杂度详解

文章目录 算法效率时间复杂度概念计算例1例2例3补充例4 空间复杂度例1例2 算法效率 算法效率分析分为两种:第一种是时间效率&#xff0c;第二种是空间效率。时间效率被称为时间复杂度&#xff0c;而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度&#…

Delicious Retouch5 for mac(PS磨皮插件DR5白金版)

Delicious Retouch5是一款强大的Photoshop插件&#xff0c;专为专业摄影师和摄影爱好者设计&#xff0c;提供一系列高级修图工具&#xff0c;帮助用户更快速、更有效地进行照片修饰和美化。其主要功能包括皮肤美容、人像润色、头发修饰、修复工具等&#xff0c;并配备定制化画笔…

海外邮件接收延迟、接收不到怎么办?U-Mail邮件网关来了

随着经济全球化的发展&#xff0c;很多国内企业开始踏足海外市场&#xff0c;电子邮件就成为了国内企业与海外客户沟通交流的主要渠道。然而海外邮件接收延迟、接收不到等问题成为了困扰企业与海外客户沟通的一大阻碍&#xff0c;导致客户邮件回复不及时&#xff0c;询盘邮件接…

新版本!飞凌嵌入式RK3568系列开发板全面支持Debian 11系统

飞凌嵌入式OK3568-C/OK3568J-C开发板现已全面支持Debian 11系统&#xff0c;新系统的加持能为用户提供主控新选择&#xff0c;并为开发者带来更多开发便利&#xff01; Debian系统作为一种广受欢迎和信赖的开源操作系统&#xff0c;以其稳定性、可靠性和开放性而闻名&#xff0…

2013年5月23日 Go生态洞察:高级Go并发模式分析

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

OpenELA 正式公开 Enterprise Linux 源代码

导读近日消息&#xff0c;在红帽&#xff08;Red Hat&#xff09;宣布不再对外公开 Red Hat Enterprise Linux&#xff08;RHEL&#xff09;源代码之后&#xff0c;同属 Linux 领域的甲骨文、SUSE 及 CIQ 宣布成立了 Open Enterprise Linux Association&#xff08;OpenELA&…

xstream实现xml和java bean 互相转换

目录 pom引用java bean 类XML 转换工具类测试类执行结果注意问题 Java中实现XML和Bean的转换的方式或插件有以下几种&#xff1a; JAXB&#xff08;Java Architecture for XML Binding&#xff09;&#xff1a;JAXB是Java SE的一部分&#xff0c;可以将Java对象与XML文档相互转…

Linux 图形界面配置RAID

目录 RAID 1 配置 RAID 5配置 , RAID 配置起来要比 LVM 方便&#xff0c;因为它不像 LVM 那样分了物理卷、卷组和逻辑卷三层&#xff0c;而且每层都需要配置。我们在图形安装界面中配置 RAID 1和 RAID 5&#xff0c;先来看看 RAID 1 的配置方法。 RAID 1 配置 配置 RAID 1…

开源项目datavines内存泄漏问题分析

应用程序开启JMX java -Dspring.profiles.activemysql -Dcom.sun.management.jmxremote.port1099 -Dcom.sun.management.jmxremote.sslfalse -Dcom.sun.management.jmxremote.authenticatefalse -Djava.rmi.server.hostname127.0.0.1 -jar dataVines.jar 通过jdk自带工具&…

数据结构第四课 -----线性表之队列

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…

使用geek卸载windows软件,干净彻底

我们在电脑上安装软件&#xff0c;以及在使用软件的过程中&#xff0c;会产生一些程序文件、注册表项和临时文件等&#xff0c;用来支持软件的正常使用&#xff0c;都是正常现象。 但是&#xff0c;在卸载软件时&#xff0c;很多软件的卸载程序&#xff0c;并不能完全清除软件…

excel中正态分布函数NORM.DIST和NORMDIST,以及它们之间的区别

NORM.DIST和NORMDIST的区别 NORM.DIST和NORMDIST函数都可以返回正态分布的概率密度、或者正态累积分布。 根据微软官网上的说法&#xff0c;NORMDIST函数已经不建议使用了&#xff0c;它已经被一个或者几个新的函数代替&#xff08;例如NORM.DIST&#xff09;&#xff0c;这些…

RabbitMQ-高级篇-黑马程序员

代码&#xff1a; 链接&#xff1a; https://pan.baidu.com/s/1nQBIgB_SbzoKu_XMWZ3JoA?pwdaeoe 提取码&#xff1a;aeoe 在昨天的练习作业中&#xff0c;我们改造了余额支付功能&#xff0c;在支付成功后利用RabbitMQ通知交易服务&#xff0c;更新业务订单状态为已支付。 但…

Python数据结构:集合(set)详解

1.集合的概念 在Python中&#xff0c;集合&#xff08;Set&#xff09;是一种无序、不重复的数据类型&#xff0c;它的实现基于哈希表&#xff0c;是由唯一元素组成的。集合中不允许有重复的元素&#xff0c;即相同元素只能出现一次。Python中的集合类似于数学中的集合&#xf…

你是想被ChatGPT改变,还是改变软件开发的未来?丨IDCF

人工智能技术的发展&#xff0c;正在深刻地改变着我们的生活和工作方式。在软件工程领域&#xff0c;ChatGPT作为一种新兴的人工智能技术&#xff0c;正在逐渐地被应用到软件开发的各个环节中。那么&#xff0c;ChatGPT对每个人的影响是什么呢&#xff1f; 一、对软件开发人员…

LockBit3.0的字符串解密方法

LockBit 与大多数勒索黑客团体一样以勒索软件即服务 (RaaS) 模式运行,该组织于 2019 年 9 月首次被观察到,此后发展为了今年最主要的勒索软件团伙,甚至超过了Conti、Hive等其他知名团体。据泄露数据站点的数据统计表明,LockBit占2022年第一季度所有与勒索软件相关的泄露事件…

使用Pandas进行数据读写的简易教程

Pandas是一个功能强大且广泛使用的Python库。它提供了一种简单而灵活的方式来读取和写入各种数据格式&#xff0c;包括CSV、Excel、SQL数据库等。本文将介绍如何使用Pandas进行数据的读取和写入操作&#xff0c;帮助你快速上手并高效地处理数据。 一、安装和导入pandas 首先&…