【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的元素。
算法流程
-
初始化指针:设置
cur = 0
,left = -1
,right = n
。 -
遍历数组:当
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
指针,因为交换过来的元素尚未处理。
- 若
-
循环结束后的区间:
[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
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~
相关文章:
【Leetcode每日一题】 分治 - 颜色分类(难度⭐⭐)(57)
1. 题目解析 题目链接:75. 颜色分类 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 算法思路解析 本算法采用三指针法,将数组划分为三个区域,分别用于存放值为0、1和2的元素。通过…...
微信登录功能-保姆级教学
目录 一、使用组件 二、登录功能 2.1 步骤 2.2 首先找到网页权限 复制demo 代码 这里我们需要修改两个参数 三、前端代码 3.1 api 里weiXinApi.ts 3.2 api里的 index.ts 3.3 pinia.ts 3.4 My.vue 四、后端代码 4.1 WeiXinController 4.2 Access_Token.Java 4.3 We…...
嵌入式MCU BootLoader开发配置详细笔记教程
目录 一、BootLoader基础 二、BootLoader原理及配置 三、BootLoader程序 bootloader.h bootloader.c 四、Application1 用户程序 application1.h application1.c 五、Application2 用户程序 application2.h 六、程序运行效果 七、工程文件Demo 一、BootLoader基础 …...
Unity 中消息提醒框
Tooltip 用于ui布局 using System.Collections; using System.Collections.Generic; using UnityEngine; using TMPro; using UnityEngine.UI;[ExecuteInEditMode()] // 可以在编辑模式下运行public class Tooltip : MonoBehaviour {public TMP_Text header; // 头部文本publi…...
好数(蓝桥杯)
文章目录 好数题目描述暴力方法一暴力方法二(超时) 好数 题目描述 【问题描述】 一个整数如果按从低位到高位的顺序,奇数位(个位、百位、万位 )上的数字是奇数,偶数位(十位、千位、十万位 …...
自动化收集Unity版本更新日志
自动化收集Unity版本更新日志 🍥功能介绍🥪食用手册填写配置开始搜集 🍨数据展示 🍥功能介绍 💡获取指定年份中所有的Unity版本更新日志。 💡根据指定字符串过滤。 💡.收集后自动保存成markdow…...
【CSS】CSS水平居中方案
CSS水平居中方案 1. 行内元素水平居中 设置父元素的text-align:center .box {width: 300px;height: 300px;margin: 100px auto;text-align: center;background-color: pink; }2. 块级元素水平居中 当块级元素设置了明确的宽度数值时,可以使用margin: 0 auto 3.…...
SQL注入sqli_labs靶场第二题
解题思路与第一题相同 ?id1 and 11 和?id1 and 12进行测试如果11页面显示正常和原页面一样,并且12页面报错或者页面部分数据显示不正常,那么可以确定此处为数字型注入。 联合查询: 猜解列名数量:3 ?id1 order by 4 判断回显…...
基于机器学习的人脸发型推荐算法研究与应用实现
1.摘要 本文主要研究内容是开发一种发型推荐系统,旨在识别用户的面部形状,并根据此形状推荐最适合的发型。首先,收集具有各种面部形状的用户照片,并标记它们的脸型,如长形、圆形、椭圆形、心形或方形。接着构建一个面部…...
【服务器部署篇】Linux下Nginx的安装和配置
作者介绍:本人笔名姑苏老陈,从事JAVA开发工作十多年了,带过刚毕业的实习生,也带过技术团队。最近有个朋友的表弟,马上要大学毕业了,想从事JAVA开发工作,但不知道从何处入手。于是,产…...
React搭建一个文章后台管理系统
1、项目准备 本篇文章讲解的是一个简单的文章后台管理系统,系统的功能很简单,如下:登录、退出;首页;内容(文章)管理:文章列表、发布文章、修改文章。 1)React官方脚手架:create-rea…...
Elasticsearch 支持的插件 —— 筑梦之路
Analysis 插件: 1、IK Analyzer:适用于中文分词的插件,提供了针对中文文本的分析器。 2、Smart Chinese Analysis:另一个中文分词插件,支持中文智能分词。 集群管理插件: 1、Kibana:Elasticsear…...
HTML:链接
目录 一、超链接 二、 外联元素 一、<a>超链接 <a> 标签用于定义超链接,超链接可以让用户从一个网页跳转到另一个网页。 常用属性: href指定链接的目标地址。download表示链接是一个下载链接,指定下载的文件名。target 指定在…...
vscode远程连接centos
文章目录 vacode连接linux1. 安装插件2. 查看配置3. 打开ssh4. 远程连接 vacode连接linux 1. 安装插件 在扩展栏搜索remote ,找到Remote Development插件,进行安装: 2. 查看配置 打开自己的linux终端,输入ifconfig,…...
scala---面向对象(类,对象,继承,抽象类,特质)
一、类(class)和 对象(object) 1、类 类就是对客观的一类事物的抽象。用一个class关键字来描述和Java一样,在这个类中可以拥有这一类事物的属性,行为等等。 2、为什么要有对象 在java中的一个class既可…...
【机器学习300问】68、随机初始化神经网络权重的好处?
一、固定的初始化神经网络权重可能带来的问题 在训练神经网络的时候,初始化权重如果全部设置为0或某个过大值/过小值。会导致一些问题: 对称权重问题:全为0的初始化权重会导致神经网络在前向传播时接收到的信号输入相同。每个神经网络节点中…...
数据结构与算法——20.B-树
这篇文章我们来讲解一下数据结构中非常重要的B-树。 目录 1.B树的相关介绍 1.1、B树的介绍 1.2、B树的特点 2.B树的节点类 3.小结 1.B树的相关介绍 1.1、B树的介绍 在介绍B树之前,我们回顾一下我们学的树。 首先是二叉树,这个不用多说ÿ…...
Tomcat源码解析——Tomcat的启动流程
一、启动脚本 当我们在服务启动Tomcat时,都是通过执行startup.sh脚本启动。 在Tomcat的启动脚本startup.sh中,最终会去执行catalina.sh脚本,传递的参数是start。 在catalina.sh脚本中,前面是环境判断和初始化参数,最终…...
蓝桥杯真题演练:2023B组c/c++
日期统计 小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的范围之内。 数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 …...
微信小程序实现预约生成二维码
业务需求:点击预约按钮即可生成二维码凭码入校参观~ 一.创建页面 如下是博主自己写的wxml: <swiper indicator-dots indicator-color"white" indicator-active-color"blue" autoplay interval"2000" circular > &…...
专业140+总分410+北京理工大学826信号处理导论考研经验北理工电子信息通信工程,真题,参考书,大纲。
今年考研专业课826信号处理导论(信号系统和数字信号处理)140,总分410,顺利上岸!回看去年将近一年的复习,还是记忆犹新,有不少经历想和大家分享,有得有失,希望可以对大家复…...
做一个后台项目的架构
后台架构的11个维度 架构1:团队协助基础工具链的选型和培训架构2:搭建微服务开发基础设施架构3:选择合适的RPC框架架构4:选择和搭建高可用的注册中心架构5:选择和搭建高可用的配置中心架构6:选择和搭建高性…...
嵌入式单片机 TTL电平、232电平、485电平的区别和联系
一、简介 TTL、232和485是常见的串口通信标准,它们在电平和通信方式上有所不同, ①一般情况下TTL电平应用于单片机外设,属于MCU/CPU等片外外设; ②232/485电平应用于产品整体对外的接口,一般是片外TTL串口转232/485…...
2024年大唐杯备考
努力更新中…… 第一章 网络架构和组网部署 1.1 5G的网络整体架构 5G网络中的中传、回传、前传(这里属于承载网的概念) CU和DU之间是中传 BBU和5GC之间是回传 BBU和AAU之间是前传(这个好记) 这里竟然还藏了MEC(…...
Spring Boot(06):Spring Boot与MySQL搭配,打造极简高效的数据管理系统
1. 前言 Spring Boot 是一个基于Spring框架的快速开发框架,可以使开发者快速搭建一个可靠的Java Web应用程序。而MySQL是最广泛使用的关系型数据库系统之一,也是Spring Boot整合数据库的首选。本文将介绍Spring Boot如何整合MySQL数据库。 2. 摘要 本文…...
Vue3 + Vite 构建组件库发布到 npm
你有构建完组件库后,因为不知道如何发布到 npm 的烦恼吗?本教程手把手教你用 Vite 构建组件库发布到 npm 搭建项目 这里我们使用 Vite 初始化项目,执行命令: pnpm create vite my-vue-app --template vue这里以我的项目 vue3-xm…...
Vite多环境配置与打包:灵活高效的Vue开发工作流
🌟 前言 欢迎来到我的技术小宇宙!🌌 这里不仅是我记录技术点滴的后花园,也是我分享学习心得和项目经验的乐园。📚 无论你是技术小白还是资深大牛,这里总有一些内容能触动你的好奇心。🔍 &#x…...
从零实现诗词GPT大模型:数据集介绍和预处理
专栏规划: https://qibin.blog.csdn.net/article/details/137728228 本章将介绍该系列文章中使用的数据集,并且编写预处理代码,处理成咱们需要的格式。 一、数据集介绍 咱们使用的数据集名称是chinese-poetry,是一个在github上开源的中文诗…...
45.HarmonyOS鸿蒙系统 App(ArkUI)创建列表(List)
列表是一种复杂的容器,当列表项达到一定数量,内容超过屏幕大小时,可以自动提供滚动功能。它适合用于呈现同类数据类型或数据类型集,例如图片和文本。在列表中显示数据集合是许多应用程序中的常见要求(如通讯录、音乐列…...
推荐算法之协同过滤
算法原理 透过百科,我们了解到协同过滤推荐(Collaborative Filtering recommendation)是在信息过滤和信息系统中正迅速成为一项很受欢迎的技术。与传统的基于内容过滤直接分析内容进行推荐不同,协同过滤算法结合用户行为分析用户…...
美团网网站建设 费用/长春网站搭建
一、Web开发介绍 目前Web开发属于Browser/Server模式,简称BS架构,开发语言有(Python、PHP、Java …)。基于Python的Web工作原理如下: 二、框架介绍 1.什么是框架? 软件框架就是为实现或完成某种软件开发…...
静态网站用什么做最快/广州白云区最新信息
有两个插件可以用 actiBPMActiviti BPMN visualizer 两款插件直接在IDEA插件市场搜索就可以搜到,也可以到官方网站的插件仓库也可以找到。 JetBrains插件市场:https://plugins.jetbrains.com/ 我正在使用的IDEA版本是2020.3,而actiBPM不兼容…...
十堰网站制作公司电话/活动策划方案详细模板
一 配置Path步骤: a:右键点击计算机 → 选择属性 → 更改设置 → 点击高级 → 点击环境变量 → 创建名为JAVA_HOME的环境变量 → 将jdk所在的目录路径(bin所在的路径)配置到JAVA_HOME变量中 b: 用;与其他变量分隔 → 在path环境变量中添…...
做设计外包的网站/自己的网站怎么建立
本次将原本控制台工程迁移到了web工程上,依旧保留原本控制台的版本。 需求: 1.把程序迁移到web平台,通过用户上传TXT的方式接收文件; 2.在页面上给出链接 (如果有封皮、作者、字数、页数等信息更佳)或表格,展示经典英文…...
网站建设是基础服务吗/网站如何宣传推广
目录 1、斐波那契数列 2、爬楼梯 1、斐波那契数列 /*** 509. 斐波那契数* 斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:** F(0) 0&#…...
b2b免费发布信息网站/如何免费自己创建网站
随着互联网的深入发展,前端开发工程师已成为市场上极具竞争力的人才。许多学生,包括以前的UI,java,或完全零基础,想学习的前端。那么话不多说,直接上干货,希望能帮助到大家。 前端开发受欢迎程度…...