算法leetcode|75. 颜色分类(rust重拳出击)
文章目录
- 75. 颜色分类:
- 样例 1:
- 样例 2:
- 提示:
- 分析:
- 题解:
- rust:
- go:
- c++:
- python:
- java:
75. 颜色分类:
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
样例 1:
输入:nums = [2,0,2,1,1,0]输出:[0,0,1,1,2,2]
样例 2:
输入:nums = [2,0,1]输出:[0,1,2]
提示:
- n == nums.length
- 1 <= n <= 300
- nums[i] 为 0、1 或 2
分析:
- 面对这道算法题目,二当家的再次陷入了沉思。
- 感觉最直观的方式就是两次遍历,先从左到右遍历把红色都换到左边,再从右到左遍历把蓝色都换到右面,常数级的额外空间,O(n) 的时间复杂度,已经很优秀了吧,还要什么自行车,要什么手表,这么简单易懂。
- 但是算法就是要尽可能优化啊,没错,我们遍历了两次,能不能只遍历一次呢?
- 那就必须在一次遍历中同时将红色换到左边,并且把蓝色换到右面,有什么好的办法吗?注意到一个细节,题目中要求不能用内置的排序,为什么呢?优秀的排序算法的时间复杂度也要到 O(n*log n) 啊,还不如两次遍历呢,什么鬼?突然我转念一想,一般内置的排序算法都是 快速排序,然后想到快速排序中的一个片段,就是找到一个基准数,然后将小于基准数的元素都移动到基准数的左边,大于基准数的元素都移动到基准数的右边,怎么样,是不是豁然开朗?这不就是答案吗?
- 使用双指针分别放在头尾表示红色和蓝色的边界,然后遍历元素,如果是红色就交换到左边红色的边界并且移动这个红色的边界,如果是蓝色就交换到右边蓝色的边界并且移动这个蓝色的边界,如果是白色就不做处理继续遍历下一个元素。
题解:
rust:
impl Solution {pub fn sort_colors(nums: &mut Vec<i32>) {let (mut i, mut l, mut r) = (0, 0, nums.len() - 1);while i <= r {if nums[i] < 1 {if i == l {i += 1;} else {nums.swap(i, l);}l += 1;} else if nums[i] > 1 {if i == r {break;}nums.swap(i, r);r -= 1;} else {i += 1;}}}
}
go:
func sortColors(nums []int) {i, l, r := 0, 0, len(nums)-1for i <= r {if nums[i] < 1 {if i == l {i++} else {nums[i], nums[l] = nums[l], nums[i]}l++} else if nums[i] > 1 {if i == r {break}nums[i], nums[r] = nums[r], nums[i]r--} else {i++}}
}
c++:
class Solution {
public:void sortColors(vector<int>& nums) {int i = 0, l = 0, r = nums.size() - 1;while (i <= r) {if (nums[i] < 1) {if (i == l) {++i;} else {swap(nums[i], nums[l]);}++l;} else if (nums[i] > 1) {if (i == r) {break;}swap(nums[i], nums[r]);--r;} else {++i;}}}
};
python:
class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i, l, r = 0, 0, len(nums) - 1while i <= r:if nums[i] < 1:if i == l:i += 1else:nums[i], nums[l] = nums[l], nums[i]l += 1elif nums[i] > 1:if i == r:breaknums[i], nums[r] = nums[r], nums[i]r -= 1else:i += 1
java:
class Solution {public void sortColors(int[] nums) {int i = 0, l = 0, r = nums.length - 1;while (i <= r) {if (nums[i] < 1) {if (i == l) {++i;} else {int t = nums[i];nums[i] = nums[l];nums[l] = t;}++l;} else if (nums[i] > 1) {if (i == r) {break;}int t = nums[i];nums[i] = nums[r];nums[r] = t;--r;} else {++i;}}}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
相关文章:
算法leetcode|75. 颜色分类(rust重拳出击)
文章目录 75. 颜色分类:样例 1:样例 2:提示: 分析:题解:rust:go:c:python:java: 75. 颜色分类: 给定一个包含红色、白色和蓝色、共 n…...
网络安全(黑客)自学笔记学习路线
谈起黑客,可能各位都会想到:盗号,其实不尽然;黑客是一群喜爱研究技术的群体,在黑客圈中,一般分为三大圈:娱乐圈 技术圈 职业圈。 娱乐圈:主要是初中生和高中生较多,玩网恋…...
NoSQL:非关系型数据库分类
NoSQL,全称 Not Only SQL,意为不仅仅是 SQL,泛指非关系型数据库。NoSQL 是基于键值对的,而且不需要经过 SQL 层的解析,数据之间没有耦合性,性能非常高。 非关系型数据库又可细分如下: 键值存储…...
【Eclipse】Project interpreter not specified 新建项目时,错误提示,已解决
目录 0.环境 1)问题截图: 2)错误发生原因: 1.解决思路 2.具体步骤 0.环境 windows 11 64位,Eclipse 2021-06 1)问题截图: 2)错误发生原因: 由于我手欠,将…...
OPENCV实现图像查找
特征匹配+单应性矩阵 # -*- coding:utf-8 -*- """ 作者:794919561 日期:2023/9/4 """ import cv2 import numpy as np# 读图像 img1 = cv2.imread(F:\\learnOpenCV\\openCVLearning\\pictures\\chess...
vue仿企微文档给页面加水印(水印内容可自定义,超简单)
1.在src下得到utils里新建一个文件watermark.js /** 水印添加方法 */let setWatermark (str1, str2) > {let id 1.23452384164.123412415if (document.getElementById(id) ! null) {document.body.removeChild(document.getElementById(id))}let can document.createE…...
“金融级”数字底座:从时代的“源启”,到“源启”的时代
今年初《数字中国建设整体布局规划》正式发布,这代表着数字中国建设迈向了实质的落地阶段,其背后的驱动就是遍及各行各业的数字化转型。 千姿百态、复杂多样的应用场景,可以看作是遍布数字中国的“点”;千行百业、各种类型的行业…...
zabbix自动发现linux系统挂载的nas盘,并实现读写故障的监控告警
一.准备好被监控机器上面执行脚本,以备服务端发现和监控 脚本的内容: ZABBI安装路径可执行文件及配置文件根据实际部署的路径更改 #!/bin/bash >/zabbixconfpath/zbx_nas.conf >/zabbixscriptspath/findnas.sh >/zabbixscriptspath/checknas.sh >/zabbixscripts…...
无涯教程-JavaScript - DAYS函数
描述 DAYS函数返回两个日期之间的天数。 语法 DAYS (end_date, start_date)争论 Argument描述Required/OptionalEnd_dateStart_date and End_date are the two dates between which you want to know the number of days.RequiredStart_dateStart_date and End_date are th…...
48、springboot 的国际化之让用户在程序界面上弄个下拉框,进行动态选择语言
上一篇是直接改浏览器的支持语言。 在浏览器上面直接改国际化语言 这次要实现的功能是直接在程序界面动态选择语言。 Locale 代表语言、国家。 ★ 在界面上动态改变语言 应用之所以能动态呈现不同的语言界面,其实关键在于如何确定客户端的Locale(代…...
FPGA可重配置原理及实现(1)——导论
一、概述 可重配置技术是Xilinx提供的用来高效利用FPGA设计资源实现FPGA资源可重复利用的最新的FPGA设计技术,这种技术的发展为FPGA应用提供了更加广阔的前景。 术语“重构”是指FPGA已经配置后的重新编程。FPGA的重构有两种类型:完全的和部分的。完全重…...
Ubuntu系统下使用宝塔面板实现一键搭建Z-Blog个人博客的方法和流程
文章目录 1.前言2.网站搭建2.1. 网页下载和安装2.2.网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar临时数据隧道3.2.Cpolar稳定隧道(云端设置)3.3.Cpolar稳定隧道(本地设置) 4.公网访问测试5.结语 1.前言 Ubuntu系统作…...
数据结构 | 第一章 绪论
问题求解与程序设计 这一节都是介绍性的内容,但是哥尼斯堡的七桥问题值得写写。 #include <stdio.h>int Euler(int mat[4][4], int n) {int count 0;for (int i 0; i < n; i) {int degree 0;for (int j 0; j < n; j) {degree mat[i][j];}if (degr…...
python爬虫入门教程(非常详细):如何快速入门Python爬虫?
示例示例Python爬虫入门教程什么是爬虫爬虫(又称网络爬虫)是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。它可以自动地抓取网页内容,并从中提取有用的数据,存储到本地文件或数据库中。 Python爬虫入门教…...
ElementUI浅尝辄止21:Tree 树形控件
树形组件:用清晰的层级结构展示信息,可展开或折叠。 树组件使用挺频繁的,常见于侧边栏树形目录、树形下拉选项按钮或搜索查询树形信息选项 1.如何使用? 基础的树形结构展示 <el-tree :data"data" :props"defa…...
插入排序,选择排序,交换排序,归并排序和非比较排序(C语言版)
前言 所谓排序,就是将一组数据按照递增或者递减的方式进行排列,让这组数据变得有序起来。排序在生活中运用的是十分广泛的,各行各业都用到了排序,比如我们在网购的时候就是按照某种排序的方式来选择东西的。所以去了解排序的实现也…...
【每日一题】1041. 困于环中的机器人
1041. 困于环中的机器人 - 力扣(LeetCode) 在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。注意: 北方向 是y轴的正方向。南方向 是y轴的负方向。东方向 是x轴的正方向。西方向 是x轴的负方向。 机器人可以接受下列三条指令之…...
C# 采用3DES-MAC进行签名 base64解码与编码
** 3DES-MAC ** 3DES-MAC(Triple Data Encryption Standard Message Authentication Code)是一种消息认证码(MAC)算法,用于验证消息的完整性和真实性。3DES-MAC使用了3DES(Triple Data Encryption Standa…...
AI绘画:StableDiffusion实操教程-完美世界-魔女(附高清图下载)
前段时间我分享了StableDiffusion的非常完整的教程:“AI绘画:Stable Diffusion 终极宝典:从入门到精通 ” 尽管如此,还有读者反馈说,尽管已经成功安装,但生成的图片与我展示的结果相去甚远。真实感和质感之…...
python excel 读取及写入固定格式
import xlrd import xlwt import re import pandas as pd from datetime import date,datetimefile_path "C:\\Users\\function_model.xls" def readexcel():df pd.read_excel(file_path ,"配置")# e_id# id# expression# name# freq# column_data df[e…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目
应用场景: 1、常规某个机器被钓鱼后门攻击后,我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后,我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...
