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

【算法题】荷兰国旗问题[力扣75题颜色分类] - JAVA

news 来源：原创 2025/5/7 0:17:15

一、题目

二、文字解释

1.1 前言

本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。如同图中所示的荷兰国旗，其由红、白、蓝三色水平排列组成。在算法领域，该问题可类比为将一个由特定的三种元素（可抽象对应红、白、蓝）组成的数组，通过特定算法实现元素的有序排列，使得相同元素相邻，且按照类似荷兰国旗颜色顺序的规则分布。

1.2 三指针算法实现

Java 代码实现

public class Solution {public void sortColors(int[] nums) {int low = 0;int mid = 0;int high = nums.length - 1;while (mid <= high) {if (nums[mid] == 0) {// 交换 nums[low] 和 nums[mid]int temp = nums[low];nums[low] = nums[mid];nums[mid] = temp;low++;mid++;} else if (nums[mid] == 1) {mid++;} else { // nums[mid] == 2// 交换 nums[mid] 和 nums[high]int temp = nums[mid];nums[mid] = nums[high];nums[high] = temp;high--;}}}
}

1.3 实现细节

三指针定义：
- low：指向 0 元素的右边界，区间 [0, low-1] 中所有元素均为 0。
- mid：当前遍历的指针，负责检查并处理每个元素。
- high：指向 2 元素的左边界，区间 [high+1, n-1] 中所有元素均为 2。
交换逻辑：
- 当 nums[mid] == 0 时：
  - 将 nums[low] 和 nums[mid] 交换，然后 low++ 和 mid++。
  - 这确保了所有 0 都被移动到数组左侧。
- 当 nums[mid] == 1 时：
  - 无需交换，直接 mid++，因为 1 应该保持在中间位置。
- 当 nums[mid] == 2 时：
  - 将 nums[mid] 和 nums[high] 交换，然后 high--。
  - 注意此时 mid 不移动，因为交换后的元素需要重新检查。
循环条件：
- mid <= high，确保遍历到所有未处理的元素。
- 当 mid > high 时，所有元素都已完成归类。

1.4 运行过程（以 `[2,0,2,1,1,0]` 为例）

初始状态：low=0, mid=0, high=5，数组：[2,0,2,1,1,0]
nums[mid]=2：执行交换操作，nums[0] 与 nums[5] 交换
- 交换后数组：[0,0,2,1,1,2]，high=4
nums[mid]=0：执行交换操作，nums[0] 与 nums[0] 交换（实际不变）
- 数组保持：[0,0,2,1,1,2]，low=1, mid=1
nums[mid]=0：执行交换操作，nums[1] 与 nums[1] 交换（实际不变）
- 数组保持：[0,0,2,1,1,2]，low=2, mid=2
nums[mid]=2：执行交换操作，nums[2] 与 nums[4] 交换
- 交换后数组：[0,0,1,1,2,2]，high=3
nums[mid]=1：执行 mid++
- 数组保持：[0,0,1,1,2,2]，mid=3
nums[mid]=1：执行 mid++
- 数组保持：[0,0,1,1,2,2]，mid=4
此时 mid=4 > high=3，算法终止。

1.5 时间与空间复杂度

时间复杂度：O(n)
- 算法只需对数组进行一次遍历，每个元素最多被交换一次。
- 所有操作都是常数时间的简单比较和交换。
空间复杂度：O(1)
- 算法只使用了三个指针变量和一个临时变量进行交换。
- 属于原地排序算法，不需要额外的空间。

【算法题】荷兰国旗问题[力扣75题颜色分类] - JAVA

一、题目二、文字解释 1.1 前言本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。如同图中所示的荷兰国旗，其由红、白、蓝三色水平排列组成。在算法领域，该问题可类比为将一个由特定的三种元素（可…...

编程日记 2025/5/7 0:17:15

【数据结构】堆的完整实现

堆的完整实现堆的完整实现GitHub地址前言堆的核心功能实现重温堆的定义堆结构定义1. 堆初始化与销毁2. 元素交换函数3. 堆化操作向上调整（子→父）向下调整（父→子） 4. 堆元素插入5. 堆元素删除6. 辅助功能函数堆的判空获取堆顶元…...

编程日记 2025/5/6 23:51:58

软考系统架构设计师系列知识点之杂项集萃（51）

接前一篇文章：软考系统架构设计师系列知识点之杂项集萃（50） 第80题设三个煤场A1、A2、A3分别能供应煤7、12、11万吨，三个工厂B1、B2、B3分别需要10、10、10万吨，从各煤场到各工厂运煤的单价（百元/吨&…...

编程日记 2025/5/6 23:39:06

patch命令在代码管理中的应用

patch 是一个用于将差异文件（补丁）应用到源代码的工具，常用于修复 bug、添加功能或调整代码结构。在您提供的代码中，patch 命令通过一系列补丁文件（.patch）修改了 open-amp 库的源代码。 patch 命令的核心作…...

编程日记 2025/5/6 23:30:18

Qt结构体运算符重载指南

在 Qt 中，结构体（struct）或类（class）中重载运算符是一种常见的做法，用于实现自定义类型的逻辑操作（如比较、算术运算等）。以下是一些常见的运算符重载示例和注意事项： 1.…...

编程日记 2025/5/3 8:58:52

基于bert预训练模型的垃圾短信分类系统

文章目录任务介绍数据说明注意事项数据处理数据准备数据集划分数据集类构建模型构建与训练模型构建模型训练模型推理附录任务介绍随着移动通信技术的飞速发展，短信（Short Message Service, SMS）已成为人们日常生活中不可或缺的沟通方式之一。然而，垃圾短信（Spam SMS）的…...

编程日记 2025/5/3 8:58:51

[Android] 网易爆米花TV 2.0.0.0429（原网易Filmly，支持多网盘的TV版、电脑版带海报墙播放器）

[Android] 网易爆米花链接：https://pan.xunlei.com/s/VOPDuQS9D7qixvAnoy7-he2PA1?pwdhzvh# [Android] 网易爆米花TV 2.0.0.0429（原网易Filmly，支持多网盘的TV版、电脑版带海报墙播放器） 详细介绍直接上主页截图，…...

编程日记 2025/5/3 8:58:49

# 前后端分离象棋对战项目开发记录

1. **结构清晰**：使用更直观的标题、分段和列表，增强可读性。 2. **视觉美观**：添加Markdown格式化（如代码块、加粗、斜体），并建议配色和排版风格。 3. **内容精炼**：精简冗余表述，突…...

编程日记 2025/5/6 23:44:57

Android Framework学习二：Activity创建及View绘制流程

文章目录 Window绘制流程Window Manager Service（WMS）SurfaceSurfaceFlinger 安卓View层次结构ActivityPhoneWindowActivity与PhoneWindow两者之间的关系ViewRootImplDecorViewDecorView 的作用DecorView 的结构总结 Activity创建流程View invalidate调用…...

编程日记 2025/5/6 23:30:18

文章五《卷积神经网络（CNN）与图像处理》

文章5：卷积神经网络（CNN）与图像处理——让AI学会"看图说话" 引言：你的AI宠物如何认出猫狗？ 想象你的手机突然有了"眼睛"，不仅能识别照片里的猫狗，还能告诉你它们的品种&am…...

编程日记 2025/5/6 23:44:57

Ubuntu系统下Firefox浏览器完整指南：故障修复、国内版安装与下载加速

Ubuntu系统下Firefox浏览器完整指南：故障修复、国内版安装与下载加速一、Firefox无法启动问题修复二、替换国际版安装国内版完整流程准备工作操作步骤验证要点三、下载延迟问题解决方案现象分析优化配置步骤注意事项四、进阶技巧补充五、常见问题FAQ 一、Firefox…...

编程日记 2025/5/6 23:49:10

【论文阅读一】掌握高效阅读法，开启学术研究新旅程：S. Keshav教授论文阅读的三遍法

文章目录一、三遍阅读法1. 初读：10分钟：宏观把握，快速筛选2. 第二遍：1个小时：更仔细的阅读，了解文中论点3. 第三遍：深入理解，注重细节，挑战假设二、运用三遍阅读法进行…...

编程日记 2025/5/7 0:14:32

多线程编程的常见问题

目录 1. 线程安全和可重入函数问题 2. 死锁的理解 2.1 死锁的概念 2.2 死锁的四个必要条件 3. C中STL容器的线程安全问题 4. C中智能指针的线程安全问题 1. 线程安全和可重入函数问题线程安全：线程安全是指在多线程环境下，一个函数或者一段代码可…...

编程日记 2025/5/7 0:13:11

算法篇（九）【滑动窗口】

如果在分析一道算法题的时候，发现使用的两个 ”双指针“ ， 都是同向的 ， 不回退的 ， 且一直都在维护 “一段连续的区间” ， 此时我们可以考虑使用 “滑动窗口” ！ 一、长度最小的子数组 209. 长度最小的子…...

编程日记 2025/5/6 23:34:49

【AI面试准备】传统测试工程师Prompt Engineering转型指南

介绍技能转型：传统测试工程师需掌握Prompt Engineering优化AI输出。如何快速掌握，以及在实际工作中如何运用。传统测试工程师向AI时代的技能转型，掌握Prompt Engineering（提示工程）已成为提升工作效率、适应智能化测…...

编程日记 2025/5/3 8:54:37

数字智慧方案6186丨智慧应急指挥解决方案（43页PPT）（文末有下载方式）

资料解读：智慧应急指挥解决方案详细资料请看本解读文章的最后内容。在当今社会，各类突发事件频发，应急管理工作面临着巨大挑战。智慧应急指挥解决方案应运而生，旨在提升应急管理的效率和水平，保障人民生命财产安全。…...

编程日记 2025/5/3 8:53:32

d202552-sql

一、184. 部门工资最高的员工 - 力扣（LeetCode） 要找到每个部门工资最高的使用窗口函数加排序函数排序函数用rank dense_rank都行把最高相同的找出来就行 select *, dense_rank() over(partition by departmentId order by Salary desc) as rank …...

编程日记 2025/5/3 8:52:31

cpper 转 java

快速上手 java 特性文章目录 java 语言特点JVM工作过程组成 java 语言特点 Java 程序编译成字节码，然后由 Java 虚拟机（JVM）执行不同平台适配相同的 JVM ，从而使得 Java 程序具备跨平台性 —— 一次编写，到处运行 …...

编程日记 2025/5/7 0:00:26

PostgreSQL常用函数

常用函数数值函数名称作用AVG(col)列的平均值COUNT(col)列的行数MAX(col)列的最大值MIN(col)列的最小值SUM(col)列值求和字符串函数名称作用LENGTH(str)计算字符串长度CONCAT(str1,str2)合并字符串LTRIM(col,str)从字串string的开头删除只包含str(默认空白LTRIM(col))R…...

编程日记 2025/5/7 0:13:11

P2196 [NOIP 1996 提高组] 挖地雷

P2196 [NOIP 1996 提高组] 挖地雷 - 洛谷题目描述在一个地图上有N（N ≤ 20）个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷&#…...

编程日记 2025/5/3 8:51:27

截图软件、画图软件、左右分屏快捷键

截图软件画图软件画图时候按字母可以改变颜色：红色r,蓝色b,绿色g,粉色p,橙色o 左右分屏：...

编程日记 2025/5/6 23:56:15

小刚说C语言刷题—1018三角形类别

1.题目描述输入三个整数，以这三个数为边长，判断是否构成三角形；若不能输出 no 。若构成三角形，进一步判断它们构的是：锐角三角形或直角三角形或钝角三角形。分别输出 ruijiao , zhijiao , dunjiao 。输入三个…...

编程日记 2025/5/3 8:46:12

【Linux】PetaLinux开发

使用Xilinx的PetaLinux工具编译用于Zynq7020的Linux. 部分图片和经验来源于网络，若有侵权麻烦联系我删除，主要是做笔记的时候忘记写来源了，做完笔记很久才写博客。专栏目录：记录自己的嵌入式学习之路-CSDN博客目录 1 一般开发流程 2 离线编译过程 3 系统根文…...

编程日记 2025/5/7 0:07:43

【计算机网络网络层深度解析】从IP协议到路由优化

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心实验实现实验1：IPv6地址配置实验2：OSPF路由配置实验3：NAT转换验证运行…...

编程日记 2025/5/6 23:31:40

第 12 届蓝桥杯 C++ 青少组中 / 高级组省赛 2021 年真题

一、选择题第 1 题题目：下列符号中哪个在 C++ 中表示行注释 ( )。 A. ! B. # C. ] D. // 正确答案：D 答案解析：在 C++ 中，//用于单行注释（行注释），从//开始到行末的内容会被编译器忽略。选项 A（!）、B（#）、C（]）均无注释功能，其中#常用于预处理指令（如#inclu…...

编程日记 2025/5/3 8:44:07

【quantity】5 derive_more库 2.0 版介绍

derive_more 是一个 Rust 过程宏库，旨在通过派生宏自动生成常见 trait 的实现，减少样板代码。2.0 版本带来了多项改进和新特性。主要特性 1. 支持的 Trait 派生 derive_more 2.0 支持派生以下 trait： 基本操作 trait: Display - 格式化显…...

编程日记 2025/5/3 8:44:06

Qt编译报错:Unexpected compiler version, expected Clang 18.0.0 or newer——Qt安装MSVC编译器

截止到本人所使用的Qt6.6.3为止，Qt尚不支持MSVC2022编译器的默认编译器配制。所以，在Qt构建套件中使用MSVC编译器的话，可能仍需要调整Visual Studio版本，或者手动设置MSVC编译器。如果你的系统安装的是Visual Studio2022&#x…...

编程日记 2025/5/3 8:44:05

（转）角色与动画的性能优化 | UnrealFest演讲干货

八、蓝图 8.1. Tick 优化的重点关注对象——Tick事件。在不需要的情况下，请默认关闭Tick。在蓝图中Actor上关掉还不行，Component也需要关掉。在CPP中，我们可以从PrimaryActorTick或PrimaryComponentTick中关闭Tick。如果需要Tick&…...

编程日记 2025/5/3 8:43:01

小程序云开发-环境配置

如果点云开发没有反应，需要修改软件安装目录不要有中文，但软件名可以是中文： 首次使用，会送1个月的云开发，配置后要等10分钟以后，才可以使用如果不能选择环境，关掉重新打开一次。然后记…...

编程日记 2025/5/3 8:40:56

【c++】【STL】priority_queue详解

目录 priority_queue的作用priority_queue的接口构造函数emptysizetoppushpopswap priority_queue的实现仿函数（函数对象）是什么？向上调整算法（adjustup）向下调整算法（adjustdown）迭代器构造pus…...

编程日记 2025/5/3 8:40:55

C语音中的三元运算符

一、三元运算符的基本语法三元运算符，也被称为条件运算符，是 C 语言中唯一有三个操作数的运算符。它的语法格式为：condition ? expression1 : expression2。从语法结构可以看出，三元运算符由一个条件表达式和两个普通表达式组…...

编程日记 2025/5/3 8:40:55

C++模板知识

目录引言一、非类型模板参数二、类模板的特化 （一）概念 （二）函数模板特化 （三）类模板特化 1. 全特化 2. 偏特化 （四）类模板特化应用示例三、模板的分离编译 …...

编程日记 2025/5/3 8:40:54

MCP 探索：微软 Microsoft MarkItDown MCP ，可把 Word、Excel 等转换成 MarkDown 格式

简简单单 Online zuozuo：简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo ：本心、输入输出、结果简简单单 Online zuozuo ：文章目录 MCP 探索：微软 Microsoft MarkItDown MCP ，可把 Word、Excel 等转换成 MarkDown 格式…...

编程日记 2025/5/3 8:39:52

文本中地理位置提取方法—正则和NLP模型

这里写目录标题一、提取地址列后12个字二、正则表达式删除不需要的文本三、保留关键字并删除之后的字四、相似度计算，查重五、去重大量的文本中识别数据，要充分考虑效率和准确率。本文的方案是通过正则和NLP门址模型联合识别的方案。首先利用现有粗略…...

编程日记 2025/5/3 8:39:52

AI大模型-RAG到底能做些什么？

RAG常见的应用场景，有以下几个方面： 1.智能客服系统：比如电商领域，对客户提出的常见问题，进行自动回复。减少人力成本。 2.人力资源管理：一个新的员工，入职一家大型公司，公司中有各…...

编程日记 2025/5/3 8:38:49

【算法基础】冒泡排序算法 - JAVA

一、算法基础 1.1 什么是冒泡排序冒泡排序是一种简单直观的比较排序算法。它重复地走访待排序的数列，依次比较相邻两个元素，如果顺序错误就交换它们，直到没有元素需要交换为止。 1.2 基本思想比较相邻元素：从头开始&#xf…...

编程日记 2025/5/3 8:38:49

Nginx搭建test服务器

创建test域名进入阿里云添加解析创建域名：test.xxxxx.com 服务器复制项目代码新建目录，Git拉取项目代码，安装上插件包修改配置文件，启动测试服务修改配置文件“服务器接口” 开启服务pm2 start app.js --name "t…...

编程日记 2025/5/3 8:38:47

依赖倒置原则

当然可以！这次我们来详细讲解依赖倒置原则（DIP: Dependency Inversion Principle），它是 SOLID 五大设计原则中的压轴，也是最关键的“架构型原则”。我将从： 什么是依赖倒置原则（定义&#x…...

编程日记 2025/5/3 8:37:45

PostgreSQL 的 VACUUM 与 VACUUM FULL 详解

PostgreSQL 的 VACUUM 与 VACUUM FULL 详解一、基本概念对比特性VACUUMVACUUM FULL定义常规维护操作，清理死元组激进重组操作，完全重写表数据锁级别不阻塞读写(共享锁)排他锁(阻塞所有操作)空间回收只标记空间为可用，不返还OS空间返还操作…...

编程日记 2025/5/3 8:37:44

SQL面试题——留存分析之使用bitmap 计算留存

使用bitmap 计算留存之前我们说过，留存分析其实在企业数据分析中，是很基础但是也很重要的，留存分析可以反映产品的发展是否健康，是否可持续发展，之前我们介绍过，可以看看之前的文章 SQL面试题——留存分析因为使用工具的限制，所以我们实现方式也会有所不同，之前我们…...

编程日记 2025/5/3 8:37:42

P2415集合求和题解

P2415 集合求和题解公式推导： 设集合有 n 个元素，记为 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an。每个子集要么包含某个元素，要么不包含。我们固定某个元素 a k a_k ak，再从剩下的 n − 1 n -…...

编程日记 2025/5/3 8:36:39

【2025年五一数学建模竞赛】C题完整论文模型建立与求解

目录 2025年五一数学建模竞赛 C题完整论文：建模与求解 Matlab代码一、问题重述二、模型假设与符号说明2.1 模型基本假设2.2 符号说明问题一：预测博主新增关注数问题二：预测用户的新关注行为问题三：预测用户在线状态及互动博主问题…...

编程日记 2025/5/3 8:36:38

wpf 输入框在输入时去除水印

wpf ScrollViewer 在输入数据时去除水印在WPF（Windows Presentation Foundation）中，ScrollViewer控件通常用于显示滚动内容。如果你想在ScrollViewer中使用数据输入（例如文本输入），并且希望在输入时去除水…...

编程日记 2025/5/3 8:36:37

数字智慧方案5857丨智慧机场解决方案与应用（53页PPT）（文末有下载方式）

资料解读：智慧机场解决方案与应用详细资料请看本解读文章的最后内容。随着科技的飞速发展，智慧机场的建设已成为现代机场发展的重要方向。智慧机场不仅提升了旅客的出行体验，还极大地提高了机场的运营效率。本文将详细解读沃土数字平台在…...

编程日记 2025/5/3 8:36:37

C语言-指针（二）

一级指针一级指针指的是存储了变量地址的指针一级指针的变量类型是类型 * 一级指针的类型与变量的类型有些不同例：int * p 前面的int * 是该地址的类型 int a 0; int * p a; 这里的指针 p 就是一级指针二级指针指针变量也是变量因此也会有地…...

编程日记 2025/5/3 8:35:35

React 组件prop添加类型

给函数的props做注解 import { useState } from reacttype Props { className:string,title?:string } // 自定义一个Button组件 function Button(props:Props){// 解构出classname\const {className} propsreturn <button className{className}>点击我</button&g…...

编程日记 2025/5/3 8:35:34

Spring Boot中集成Guava Cache或者Caffeine

一、在Spring Boot(1.x版本)中集成Guava Cache 注意： Spring Boot 2.x用户：优先使用Caffeine，性能更优且维护活跃。 1. 添加依赖在pom.xml中添加Guava依赖： <dependency><groupId>com.google.guava</groupId&…...

编程日记 2025/5/3 8:33:28