【Leetcode每日一题】 分治 - 颜色分类(难度⭐⭐)(57)

1. 题目解析

题目链接:75. 颜色分类

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

算法思路解析

本算法采用三指针法,将数组划分为三个区域,分别用于存放值为0、1和2的元素。通过精心设计的指针移动策略,算法能够在单次遍历中完成数组的重新排序。

定义与初始化

  • nums:待排序的数组,长度为n
  • left:指向0序列的末尾,初始化为-1。
  • cur:当前扫描的数组位置,初始化为0。
  • right:指向2序列的起始位置,初始化为n

区间保证

在算法执行过程中,始终保证以下区间划分:

  • [0, left]:存放值为0的元素。
  • [left + 1, cur - 1]:存放值为1的元素。
  • [cur, right - 1]:待处理的元素区间。
  • [right, n - 1]:存放值为2的元素。

算法流程

  1. 初始化指针:设置cur = 0left = -1right = n

  2. 遍历数组:当cur < right时,循环执行以下步骤:

    a. 处理值为0的元素

    • nums[cur] == 0,则将nums[cur]nums[left + 1]交换,使0元素移至正确位置。
    • 更新left指针,left++
    • 更新cur指针,cur++

    b. 处理值为1的元素

    • nums[cur] == 1,则无需交换,直接更新cur指针,cur++

    c. 处理值为2的元素

    • nums[cur] == 2,则将nums[cur]nums[right - 1]交换,使2元素移至右侧区域。
    • 更新right指针,right--
    • 注意此时不更新cur指针,因为交换过来的元素尚未处理。
  3. 循环结束后的区间

    • [0, left]区间存放了所有值为0的元素。
    • [left + 1, right - 1]区间存放了所有值为1的元素。
    • [right, n - 1]区间存放了所有值为2的元素。

3.代码编写

class Solution 
{
public:
    void sortColors(vector<int>& nums) 
    {
        int left = -1, right = nums.size(), i = 0;
        while(i < right)
        {
            if(nums[i] == 0)
            {
                swap(nums[++left], nums[i++]);
            }
            else if(nums[i] == 1)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
    }
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

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

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

相关文章

CentOS 7安装Zookeeper

说明&#xff1a;本文介绍如何在CentOS 7操作系统下使用Zookeeper 下载安装 首先&#xff0c;去官网下载所需要安装的版本&#xff0c;我这里下载3.4.9版本&#xff1b; 上传到云服务器上&#xff0c;解压 tar -xvf zookeeper-3.4.9.tar.gz修改配置 进入Zookeeper目录下的co…

3. 安装arrach结构的Mysql

提示&#xff1a;arm的centos上面安装arrach结构的Mysql 文章目录 前言一、查看已经安装过的并卸载mysql二、创建mysql用户组1.设置用户组2. 安装3.设置启动4.查看密码5.修改登录密码6.授权7.修改连接8.设置参数 常见问题排查1. 启动失败查看&#xff1a;2. 用户操作3. 踩坑解决…

【已开源】​基于stm32f103的爬墙小车

​基于stm32f103的遥控器无线控制爬墙小车&#xff0c;实现功能为可平衡在竖直墙面上&#xff0c;并进行移动和转向&#xff0c;具有超声波防撞功能。 直接上&#xff1a; 演示视频如&#xff1a;哔哩哔哩】 https://b23.tv/BzVTymO 项目说明&#xff1a; 在这个项目中&…

Unity 2D让相机跟随角色移动

相机跟随移动 最简单的方式通过插件Cinemachine 在窗口/包管理器选择全部找到Cinemachine&#xff0c;导入。然后在游戏对象/Cinemachine创建2D Camera。此时层级中创建一个2D相机。选中人物拖入检查器Follow。此时相机跟随人物移动。 修改相机视口距离 在检查器中Lens下调正…

linux学习:文件属性

在操作文件的时候&#xff0c;经常需要获取文件的属性&#xff0c;比如类型、权限、大小、所有者等等&#xff0c; 这些信息对于比如文件的传输、管理等是必不可少的&#xff0c;而这些信息 这三个函数的功能完全一样&#xff0c;区别是&#xff1a;stat( )参数是一个文件的名字…

UI设计/交互设计/视觉设计项目汇报/作品集Figma/PPT模板

作为UI设计/交互设计/视觉设计师&#xff0c;创建作品集对于向潜在客户或雇主展示您的技能、创造力和风格至关重要。以下分步指南可帮助您创建令人印象深刻的作品集&#xff1a; 选择您的最佳作品&#xff1a;选择您最强大且最相关的设计项目&#xff0c;将其纳入您的作品集。…

Java应用中文件上传安全性分析与安全实践

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一. 文件上传的风险 二. 使用合适的框架和库 1. Spr…

CCF区块链论文录用资讯--ICDE 2024

ICDE是CCF A类会议 (数据库&#xff0f;数据挖掘&#xff0f;内容检索) 其2024录用了8篇区块链论文 Database technology for Blockchains I Efficient Partial Order Based Transaction Processing for Permissioned Blockchains &#xff08;针对许可区块链的高效的基于偏序…

Niobe开发板OpenHarmony内核编程开发——事件标志

本示例将演示如何在Niobe Wifi IoT开发板上使用cmsis 2.0 接口使用事件标志同步线程 EventFlags API分析 osEventFlagsNew() /// Create and Initialize an Event Flags object./// \param[in] attr event flags attributes; NULL: default values./// \return e…

openstack安装dashboard后登录网页显示404错误

1. 2.进入该目录vim /etc/httpd/conf.d/openstack-dashboard.conf 增加这一行 WSGIApplicationGroup %{GLOBAL} 重启httpd后就可以访问了

Devin AI: The World’s First AI Software Engineer

Devin AI是Cognition AI团队推出的一款名为Devin的人工智能软件工程师&#xff0c;它被誉为世界上第一个完全自主的AI软件工程师。Devin AI在2024年3月12日发布&#xff0c;并在SWE-bench编码基准测试中设立了新的技术标杆。 Devin AI具备多项强大的能力&#xff0c;包括学习如…

数据结构与算法——20.B-树

这篇文章我们来讲解一下数据结构中非常重要的B-树。 目录 1.B树的相关介绍 1.1、B树的介绍 1.2、B树的特点 2.B树的节点类 3.小结 1.B树的相关介绍 1.1、B树的介绍 在介绍B树之前&#xff0c;我们回顾一下我们学的树。 首先是二叉树&#xff0c;这个不用多说&#xff…

【5G PHY】5G无线链路监测原理简述

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…

网络篇11 | 网络层 ICMP

网络篇11 | 网络层 ICMP 01 简介02 报文格式1&#xff09;Type(类型)2&#xff09;Code(代码)3&#xff09;Checksum(校验和)4&#xff09;ICMP数据部分 03 ICMP数据抓包1&#xff09;类型 8&#xff1a;回显请求&#xff08;Echo Request&#xff09;2&#xff09;类型 13&…

产生死锁的四个必要条件

产生死锁的四个必要条件 互斥使用: 一个资源每次只能被一个线程使用。这意味着如果一个线程已经获取了某个资源&#xff08;比如锁&#xff09;&#xff0c;那么其他线程就必须等待&#xff0c;直到该线程释放资源。 不可抢占: 已经获得资源的线程在释放资源之前&#xff0c;不…

MySQL优化表,表的碎片整理和空间回收,清理空间

1.sql -- 查看表占用空间大小。简单查询可以用show table status like blog_visit; select data_length, index_length, data_free, o.* from information_schema.tables o where table_schema in (lishuoboy-navigation) and table_nameblog_visit order by data_length des…

车载电子电器架构 —— 平行开发策略

车载电子电器架构 —— 平行开发策略 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己…

常见的垃圾回收算法

文章目录 1. 标记清除算法2. 复制算法3. 标记整理算法4. 分代垃圾回收算法 1. 标记清除算法 核心思想&#xff1a; 标记阶段&#xff0c;将所有存活的对象进行标记。Java中使用可达性分析算法&#xff0c;从GC Root开始通过引用链遍历出所有存活对象。清除阶段&#xff0c;从…

攻防世界13-simple_php

13-simple_php <?php show_source(*__FILE__*);//高亮文件 include("config.php");//文件包含在内 $a$_GET[a];//获得a $b$_GET[b];//获得b if($a0 and $a){ //判断a是否满足条件echo $flag1; //满足就输出flag1 } if(is_numeric($b)){ //判断b的条件&#x…

ASP.NET基于Ajax+Lucene构建搜索引擎的设计和实现

摘 要 通过搜索引擎从互联网上获取有用信息已经成为人们生活的重要组成部分&#xff0c;Lucene是构建搜索引擎的其中一种方式。搜索引擎系统是在.Net平台上用C#开发的&#xff0c;数据库是MSSQL Server 2000。主要完成的功能有&#xff1a;用爬虫抓取网页&#xff1b;获取有效…