当前位置: 首页 > news >正文

力扣最热一百题——颜色分类

目录

题目链接:75. 颜色分类 - 力扣(LeetCode)

题目描述

示例

提示:

解法一:不要脸用sort

Java写法:

运行时间

解法二:O1指针

Java写法:

重点

运行时间

C++写法:

运行时间

时间复杂度和空间复杂度

总结


题目链接:75. 颜色分类 - 力扣(LeetCode)

注:下述题目描述和示例均来自力扣

题目描述

        给定一个包含红色、白色和蓝色、共 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] 为 01 或 2

进阶:

  • 你能想出一个仅使用常数空间的一趟扫描算法吗?


解法一:不要脸用sort

        既然题目都说了不让用sort,那么我这种一生逆骨的选手是必须要用一下的嘿嘿。

Java写法:

class Solution {public void sortColors(int[] nums) {Arrays.sort(nums);}
}

运行时间

真爽啊哈哈哈哈哈哈哈哈哈


解法二:O1指针

Java写法:

class Solution {public void sortColors(int[] nums) {// p0用于交换0int p0 = 0;// p1用于交换1int p1 = 0;// 进入交换逻辑for (int i = 0; i < nums.length; i++) {if (nums[i] == 1) {// 遇到1int temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;p1++;} else if (nums[i] == 0) {// 遇到0int temp = nums[i];nums[i] = nums[p0];nums[p0] = temp;// 确保在遇到 0 时,p0 和 p1 之间的元素都是 1if (p0 < p1) {temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;}p0++;p1++;}}}
}

重点

  • 变量定义

    • p0:用于指向 0 的位置。
    • p1:用于指向 1 的位置。
  • 循环遍历数组

    • 当遍历到元素 1 时,代码会将其与 p1 位置的元素交换,然后 p1 向右移动一位。
    • 当遍历到元素 0 时,代码会将其与 p0 位置的元素交换,然后 p0 向右移动一位,p1 也向右移动。
  • if (p0 < p1) 逻辑

    • 这一条件判断是为了确保在遇到 0 时,p0p1 之间的元素都是 1
    • 这样做的目的是在 0 被移动到前面时,同时也要把 1 移动到 p1 的位置,确保 1 被正确放在 0 的右边。
  • 避免重复处理

    • 只有在 p0 小于 p1 时,才进行这次交换,因为这表示 p0p1 之间有 1,需要将当前的 01 进行交换,以保持排序。

运行时间

C++写法:

class Solution {
public:void sortColors(vector<int>& nums) {// p0 用于交换 0int p0 = 0;// p1 用于交换 1int p1 = 0;// 进入交换逻辑for (int i = 0; i < nums.size(); i++) {if (nums[i] == 1) {// 遇到 1swap(nums[i], nums[p1]);p1++;} else if (nums[i] == 0) {// 遇到 0swap(nums[i], nums[p0]);// 确保在遇到 0 时,p0 和 p1 之间的元素都是 1if (p0 < p1) {swap(nums[i], nums[p1]);}p0++;p1++;}}}
};

运行时间

时间复杂度和空间复杂度


总结

        Ez就完事啦~~~~~

相关文章:

力扣最热一百题——颜色分类

目录 题目链接&#xff1a;75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; 题目描述 示例 提示&#xff1a; 解法一&#xff1a;不要脸用sort Java写法&#xff1a; 运行时间 解法二&#xff1a;O1指针 Java写法&#xff1a; 重点 运行时间 C写法&#xff1a;…...

2024年工业制造企业CRM研究报告:需求清单、市场格局、案例分析

我国是世界上产业体系最完备的国家&#xff0c;拥有全球规模最大、门类最齐全的生产制造体系&#xff0c;在500种主要工业产品中&#xff0c;有四成以上产品产量位居全球第一。2023年制造业增加值达33万亿元&#xff0c;占世界的比重稳定在30%左右&#xff0c;我国制造业增加值…...

Spring MVC参数接收 总结

1. 简介 Spring MVC可以简化从前端接收参数的步骤。 2. Param传参 通过设定函数入参和添加标记来简化接受&#xff1a; //参数接收 RequestMapping("product") ResponseBody //接受/product?productgoods&id123 //1.名称必须相同&#xff0c;2.不传值不会不…...

Docekrfile和docker compose编写指南及注意事项

Dockerfile 基础语法 我们通过编写dockerfile,将每一层要做的事情使用语法固定下来&#xff0c;之后运行指令就可以通过docker来制作自己的镜像了。 构建镜像的指令&#xff1a;docker build /path -t imageName:tag 注意&#xff0c;docker build后的path必须是dockerfile…...

VITS源码解读6-训练推理

1. train.py 1.1 大体流程 执行main函数&#xff0c;调用多线程和run函数执行run函数&#xff0c;加载日志、数据集、模型、模型优化器for循环迭代数据batch&#xff0c;每次执行train_and_evaluate函数&#xff0c;训练模型 这里需要注意&#xff0c;源码中加载数据集用的分…...

力扣 简单 104.二叉树的最大深度

文章目录 题目介绍解法 题目介绍 解法 如果知道了左子树和右子树的最大深度 l 和 r&#xff0c;那么该二叉树的最大深度即为max(l,r)1&#xff0c;而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用递归的方法来计算二叉树的最大深度。具体而言&#xff…...

单片机长短按简单实现

单片机长短按简单实现 目录 单片机长短按简单实现1 原理2 示例代码2.1 按键实现 3 测试log4 其他实现方式 1 原理 按键检测和处理的步骤如下&#xff1a; 1&#xff1a;定时扫描按键&#xff08;使用定时器定时扫描&#xff0c;也可以用软件延时或者系统心跳之类的方式&#…...

如何用好通义灵码企业知识库问答能力?

通义灵码企业版&#xff1a;通义灵码企业标准版快速入门_智能编码助手_AI编程_智能编码助手通义灵码(Lingma)-阿里云帮助中心 通义灵码提供了基于企业知识库的问答检索增强的能力&#xff0c;在开发者使用通义灵码 IDE 插件时&#xff0c;可以结合企业知识库内上传的文档、文件…...

C语言自定义类型:联合体

目录 前言一、联合体1.1 联合体类型的声明1.2 联合体的特点1.3 相同成员的结构体和联合体对比1.4 联合体大小的计算1.5 联合体的⼀个练习 总结 前言 前面我讲到C语言中的自定义结构——结构体&#xff0c;其实C语言中的自定义结构不只有结构体&#xff0c;还有枚举和联合体&am…...

【JavaEE】——线程池大总结

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯&#xff0c; 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01;希望本文内容能够帮助到你&#xff01; 目录 引入&#xff1a;问题引入 一&#xff1a;解决方案 1&#xff1a;方案一——协程/纤程 &#xff08;1…...

编程中为什么使用0和1表示状态

前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 我们看到很多项目都使用0和1表示某些状态信息&#xff0c;具体含义取决于上下文。以下是一些常见的用法&#xff1a; 布尔值&#x…...

C++入门基础知识90(实例)——实例15【求两数的最大公约数】

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///C爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于求两数的最大公约数的相关内容&#xff…...

自动化办公-Python-os模块的使用

os.path 模块的使用 在指定文件路径时&#xff0c;由于操作系统的差异&#xff0c;直接使用硬编码的路径可能会导致程序在不同平台上无法正常运行。为了解决这个问题&#xff0c;Python 提供了 os.path 模块&#xff0c;它包含了一系列用于路径操作的函数&#xff0c;可以帮助您…...

无人机之数据处理技术篇

一、数据采集 无人机通过搭载的各种传感器和设备&#xff0c;如GPS、加速度计、陀螺仪、磁力计、激光雷达(LiDAR)、高光谱相机(Hyperspectral)、多光谱相机(Multispectral)以及普通相机等&#xff0c;实时采集飞行过程中的各种数据。这些数据包括无人机的位置、速度、高度、姿态…...

828华为云征文|部署多功能集成的协作知识库 AFFiNE

828华为云征文&#xff5c;部署多功能集成的协作知识库 AFFiNE 一、Flexus云服务器X实例介绍二、Flexus云服务器X实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置2.4 Docker 环境搭建 三、Flexus云服务器X实例部署 AFFiNE3.1 AFFiNE 介绍3.2 AFFiNE 部署3.3 AFFiNE 使用 四、…...

c++(AVL树及其实现)

一、AVL树的概念 AVL树是最先发明的自平衡⼆叉查找树&#xff0c;AVL是⼀颗空树&#xff0c;或者具备下列性质的⼆叉搜索树&#xff1a;它的 左右子树都是AV树&#xff0c;且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树&#xff0c; 通过控制高度差去控…...

Cesium GIS项目关于湖泊识别与提取的实现

1. 引言 项目背景 随着遥感技术的发展,地理信息系统的应用越来越广泛。本项目旨在开发一个基于Cesium的地理信息系统,利用深度学习技术自动识别并显示湖泊的位置。 目标与意义 通过自动化处理大量遥感影像数据,提高湖泊监测的效率和准确性,为水资源管理和环境保护提供支…...

两个圆形 一个z里面一个z外面,z里面的大,颜色不同 html

两个圆形 一个z里面一个z外面&#xff0c;z里面的大&#xff0c;颜色不同 html <!DOCTYPE html> <html> <head> <style> .outer-circle {width: 150px;height: 150px;border-radius: 50%;background-color: #ff9999; /* 外圆的颜色 */position: relat…...

【Power Query】M函数-table

M函数-table 添加列&#xff08;AddColumn&#xff09;&#xff1a;条件语句&#xff08;If..then..else&#xff09;&#xff1a;容错语句&#xff08;try..otherwise&#xff09;&#xff1a; 排序&#xff08;ReorderColumns&#xff09;&#xff1a;筛选&#xff08;Selec…...

uni-app 封装websocket 心跳检测,开箱即用

class websocketUtils {constructor(url, needbeat, options {}) {this.needbeat needbeat;this.url url;this.options options;this.ws null;this.heartbeatInterval options.heartbeatInterval || 10000; // 心跳间隔&#xff0c;默认为10秒 this.reconnectInterval …...

Swift-All快速上手:小白也能轻松搞定大模型训练与部署

Swift-All快速上手&#xff1a;小白也能轻松搞定大模型训练与部署 1. 为什么选择Swift-All&#xff1f; 如果你刚接触大模型训练&#xff0c;可能会被各种复杂的工具和框架吓到。配置环境、处理分布式训练、管理显存...这些技术细节常常让新手望而却步。这就是Swift-All的价值…...

如何用AnythingLLM打造你的智能文档聊天机器人:5大核心功能全解析

如何用AnythingLLM打造你的智能文档聊天机器人&#xff1a;5大核心功能全解析 【免费下载链接】anything-llm 这是一个全栈应用程序&#xff0c;可以将任何文档、资源&#xff08;如网址链接、音频、视频&#xff09;或内容片段转换为上下文&#xff0c;以便任何大语言模型&…...

UltraStar Deluxe实战指南:免费打造专业级家庭KTV系统

UltraStar Deluxe实战指南&#xff1a;免费打造专业级家庭KTV系统 【免费下载链接】USDX The free and open source karaoke singing game UltraStar Deluxe, inspired by Sony SingStar™ 项目地址: https://gitcode.com/gh_mirrors/us/USDX 还在为KTV包厢的高昂费用而…...

保姆级教程:用Java SpringBoot实现钉钉机器人自动回复@消息(附完整源码)

企业级钉钉机器人开发实战&#xff1a;SpringBoot实现智能消息处理 最近在帮一家电商公司搭建内部工单系统时&#xff0c;遇到了一个典型需求&#xff1a;当员工在钉钉群里机器人提交问题时&#xff0c;需要自动识别用户身份并回复处理进度。这个看似简单的功能&#xff0c;在…...

HyperDroid深度体验:安卓秒变Win11桌面的秘密武器

1. HyperDroid初体验&#xff1a;当安卓遇上Win11的奇妙化学反应 第一次打开HyperDroid时&#xff0c;我的手机屏幕瞬间变成了熟悉的Windows 11界面&#xff0c;那种感觉就像把电脑桌面装进了口袋。任务栏、开始菜单、甚至窗口的圆角设计都完美复刻&#xff0c;连动态磁贴的亚克…...

obsidian-i18n:让Obsidian插件全面支持中文的效率提升方案

obsidian-i18n&#xff1a;让Obsidian插件全面支持中文的效率提升方案 【免费下载链接】obsidian-i18n 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-i18n Obsidian作为一款强大的知识管理工具&#xff0c;其丰富的插件生态极大扩展了核心功能。然而&#xf…...

SFM3304热式流量传感器嵌入式驱动开发指南

1. Sensirion SFM3304 流量传感器技术解析与嵌入式驱动开发指南Sensirion SFM3304 是一款基于热式原理的高精度、低功耗数字质量流量传感器&#xff0c;专为医疗呼吸设备、工业过程控制及实验室气体分析等对响应速度、零点稳定性与长期可靠性要求严苛的应用场景设计。该器件采用…...

C语言头文件规范与工程实践优化指南

C语言头文件包含规范与工程实践指南1. 头文件包含问题的工程背景1.1 典型问题场景在嵌入式C语言开发中&#xff0c;当工程规模较小时&#xff0c;头文件包含问题往往不易显现。但随着项目代码量增长到数千甚至数万行时&#xff0c;不合理的头文件包含方式会导致以下典型问题&am…...

Rust 看了流泪,AI 看了沉默:扒开 Go 泛型最让你抓狂的“残疾”类型推断

大家好&#xff0c;我是Tony Bai。在这个大模型&#xff08;AI&#xff09;写代码如喝水一般简单的时代&#xff0c;你有没有遇到过一种极其憋屈的场景&#xff1a;你让 Claude Code 或者 Codex 帮你写了一段 Go 语言代码&#xff0c;逻辑清晰&#xff0c;结构优雅&#xff0c;…...

微信小程序UI组件库终极指南:WeUI-WXSS与Vant、ColorUI深度对比分析

微信小程序UI组件库终极指南&#xff1a;WeUI-WXSS与Vant、ColorUI深度对比分析 【免费下载链接】weui-wxss A UI library by WeChat official design team, includes the most useful widgets/modules. 项目地址: https://gitcode.com/gh_mirrors/we/weui-wxss WeUI-WX…...