LeetCode每日一题之专题一:双指针 ——移动零

移动零OJ链接:283. 移动零 - 力扣(LeetCode)

题目:

解法(快排的思想:数组划分区间-数组分两块):
算法思路:

在本题中,我们可以用一个 dest 指针来扫描整个数组,另一个 src 指针用来记录非零数序列
的最后一个位置。根据 dest 在扫描的过程中,遇到的不同情况,分类处理,实现数组的划分。
在 dest 遍历期间,使 [0, src] 的元素全部都是非零元素, [src + 1, dest - 1] 的元素全是零。

 

算法流程:
a. 初始化dest=0(用来遍历数组), src = -1 (指向非零元素序列的最后⼀个位置。
因为刚开始我们不知道最后一个非零元素在什么位置,因此初始化为 -1 )
b. cur 依次往后遍历每个元素,遍历到的元素会有下面两种情况:
i. 遇到的元素是 0 , dest 直接 ++ 。因为我们的目标是让 [src + 1, dest - 1] 内的元素全都是零,因此当 dest 遇到 0 的时候,直接 ++ ,就可以让 0 在 dest - 1的位置上,从而在 [src + 1, dest - 1] 内;
ii. 遇到的元素不是 0 , src++ ,并且交换 dest 位置和 src 位置的元素,之后让 dest++ ,扫描下一个元素。
• 因为 src 指向的位置是非零元素区间的最后一个位置,如果扫描到一个新的非零元素,那么它的位置应该在 src + 1 的位置上,因此 src 先自增 1 ;
• src++ 之后,指向的元素就是 0 元素(因为非零元素区间末尾的后一个元素就是0 ),因此可以交换到 dest 所处的位置上,实现 [0, src] 的元素全部都是非零元素, [src + 1, dest - 1] 的元素全是零。

 

 

C++:

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int dest=0,src=-1;dest<nums.size();dest++)
        {
            if(nums[dest])
            {
                swap(nums[++src],nums[dest]);
            }
        }
    }
};

运行结果: 

复杂度分析: 

时间复杂度:O(N)

空间复杂度:O(1)

PS:看到这里了,码字不易,给个一键三连鼓励一下吧!有不足或者错误之处欢迎在评论区指出! 

 

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

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

相关文章

应用方案 | 内置ALC的音频前置放大器D2538A和D3308芯片

一、应用领域 D2538A和D3308是芯谷科技推出的两款内置ALC&#xff08;音频限幅器&#xff09;的前置音频放大器芯片&#xff0c;其中D2538A为单通道&#xff0c;D3308为双通道&#xff0c;它特别适用于胎心仪、个人医疗防护、立体声收录机、盒式录音机等涉及音频放大与限幅的产…

Java游戏开发基础:从零开始搭建自己的游戏之《人生重开模拟器》简易版

一、引言 人生重开模拟器游戏是一种虚拟角色扮演游戏&#xff0c;玩家通过控制一个虚构的角色&#xff0c;体验与现实生活中不同的选择和结果。玩家的决策将影响角色的生活轨迹&#xff0c;包括他们的职业生涯、社交关系、健康和财富等方面。 游戏的乐趣在于提供了一个虚拟的沙…

1.JavaEE进阶篇 - 为什么要学习SpringBoot呢?

文章目录 1.为什么要学框架&#xff1f;2.框架的优点展示(SpringBoot VS Servlet)2.1 Servlet 项⽬开发2.1.1 创建项⽬2.1.2 添加引⽤2.1.3 添加业务代码2.1.4 运⾏项⽬(配置tomcat)2.1.5 Maven配置2.1.5.1修改本地Maven仓库地址2.1.5.2 配置settings.xml文件2.1.5.3项目 本地仓…

LeetCode 19.删除链表的倒数第N个结点

给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 示例 2&#xff1a; 输入&#xff1a;head [1], n 1 输出&#xff1a;[] 示例 3&#x…

大数据实验一,Hadoop安装及使用

目录 一&#xff0e;实验内容 二&#xff0e;实验目的 三&#xff0e;实验过程截图及说明 1、安装SSH&#xff0c;并配置SSH无密码登录 2、配置java环境 3.Hadoop的安装与配置 4、修改四个配置文件&#xff1a; 5、格式化HDFS的NameNode&#xff1a; 6、启动Hadoop 7、…

Polardb MySQL 产品架构及特性

一、产品概述; 1、产品族 参考&#xff1a;https://edu.aliyun.com/course/3121700/lesson/341900000?spma2cwt.28120015.3121700.6.166d71c1wwp2px 2、polardb mysql架构优势 1&#xff09;大容量高弹性&#xff1a;最大支持存储100T&#xff0c;最高超1000核CPU&#xff0…

PEFT-LISA

LISA是LoRA的简化版&#xff0c;但其抓住了LoRA微调的核心&#xff0c;即LoRA侧重更新LLM的底层embedding和顶层head。 根据上述现象&#xff0c;LISA提出两点改进&#xff1a; 始终更新LLM的底层embedding和顶层head随机更新中间层的hidden state 实验结果 显存占用 毕竟模型…

游戏引擎之高级动画技术

一、动画混合 当我们拥有各类动画素材&#xff08;clips&#xff09;时&#xff0c;要将它们融合起来成为一套完整的动画。 最经典的例子就是从走的动画自然的过渡到跑的动画。 1.1 线性插值 不同于上节课的LERP&#xff08;同一个clip内不同pose之间&#xff09;&#xff…

STM32学习和实践笔记(4):分析和理解GPIO_InitTypeDef GPIO_InitStructure (c)

第二个成员变量是GPIOSpeed_TypeDef GPIO_Speed&#xff1b;也与int a一样同理。 GPIOSpeed_TypeDef是一个枚举类型&#xff0c;其定义如下&#xff1a; typedef enum { GPIO_Speed_10MHz 1, GPIO_Speed_2MHz, GPIO_Speed_50MHz }GPIOSpeed_TypeDef; #define IS_GPI…

STM32-03基于HAL库(CubeMX+MDK+Proteus)输入检测案例(按键控制LED)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的按键检测代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 搭建完成开发STM32开发环境之后&#xff0c;开始GPIO…

vue结合Elempent-Plus/UI穿梭框更改宽度以及悬浮文本显示

由于分辨率不同会导致文本内容显示不全&#xff0c;如下所示&#xff1a; 因此需要 1、悬浮到对应行上出现悬浮信息 实现代码如下所示&#xff1a; 这里只演示Vue3版本代码&#xff0c;Vue2版本不再演示 区别就在插槽使用上Vue3使用&#xff1a;#default“”&#xff1b;Vu…

R统计实战:详解机器学习Adaboost的操作步骤与应用

一、引言 机器学习是人工智能的核心领域之一&#xff0c;其重要性体现在其能够从数据中自动学习并改进的能力上。在实际问题中&#xff0c;机器学习已经被广泛应用于各个领域&#xff0c;包括但不限于金融、医疗、电子商务、社交网络等。例如&#xff0c;在金融领域&#xff0c…

spark shuffle 补充概念

spark shuffle 我们在前面的文章说过&#xff0c;所谓shuffle&#xff0c;就是spark RDD的一种宽依赖关系&#xff0c;父RDD的数据会发送给多个子RDD spark中Map和Reduce概念 在Shuffle过程中.提供数据的称之为Map端(Shuffle Write)接收数据的称之为Reduce端(Shuffle Read)&…

使用Excel连接Azure DevOps自动退出的问题

Azure DevOps Server (原名TFS)是微软公司的软件开发管理平台&#xff0c;也是著名的软件开发过程管理工具&#xff1b;系统中记录了软件开发过程中的需求、问题、缺陷和迭代计划等各种软件开发工作项数据。 对于工作项数据的批量操作(例如新增和编辑)&#xff0c;Excel是一个非…

springcloud基本使用五(Gateway服务网关)

为什么使用网关&#xff1f; 权限控制&#xff1a;网关作为微服务入口&#xff0c;需要校验用户是是否有请求资格&#xff0c;如果没有则进行拦截。 路由和负载均衡&#xff1a;一切请求都必须先经过gateway&#xff0c;但网关不处理业务&#xff0c;而是根据某种规则&#xff…

【Python面试题收录】Python的可变对象与不可变对象

一、可变对象与不可变对象的定义 在Python中&#xff0c;对象的可变性是指对象的内部状态&#xff08;值&#xff09;是否允许在对象创建后发生改变。根据这一特性&#xff0c;Python的数据类型可以分为两大类&#xff1a;可变对象&#xff08;mutable objects&#xff09;和不…

某音乐平台歌曲信息逆向之webpack扣取

逆向网址 aHR0cHM6Ly95LnFxLmNvbS8 逆向链接 aHR0cHM6Ly95LnFxLmNvbS9uL3J5cXEvc29uZ0RldGFpbC8wMDJkdzRndjFabWlHdA 逆向接口 aHR0cHM6Ly91Ni55LnFxLmNvbS9jZ2ktYmluL211c2ljcy5mY2c 逆向过程 请求方式&#xff1a;POST 逆向参数 sign zzbd8c72309rdslvlnjwk8pthj2lw462f12…

Linux系统---进程间通信与管道入门

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、进程间通信 1.进程间通信的目的 1.数据传输&#xff1a;一个进程需要把他的数据传给另外一个进程。 2.资源共享&…

el-table实现表格内部横向拖拽效果

2024.4.2今天我学习了如何对el-table表格组件实现内部横向拖拽的效果&#xff0c;效果&#xff1a; 代码如下&#xff1a; 一、创建utils/底下文件 const crosswise_drag_table function (Vue){// 全局添加table左右拖动效果的指令Vue.directive(tableMove, {bind: function…

IMU参数辨识及标定

IMU参数辨识及标定 一、标定参数分析 标定的本质是参数辨识。首先明确哪些参数可辨识&#xff0c;其次弄清怎样辨识。 参数包括陀螺仪和加速度计各自的零偏、标度因数、安装误差。 IMU需要标定的参数主要是确定性误差和随机误差&#xff0c;确定性误差主要标定bias&#xff0…