首页 > 其他分享 >Leecode热题100-75.颜色分类

Leecode热题100-75.颜色分类

时间:2024-10-03 19:47:12浏览次数:10  
标签:cur nums int Leecode ++ 75 红色 100 blueFirst

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

进阶:

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

写就写进阶的解,这还不简单,直接上代码,看不懂可以私信或评论,第一时间解答

class Solution {
    /**这个题目也是听起来比较唬人,但是这个仔细想想如果按照数字来看,不就是红色最小,白色居中,蓝色最大吗
    这是啥问题?荷兰国旗啊,下面我们用荷兰国旗问题解一下,这就是荷兰国旗里的Partition */
    public void sortColors(int[] nums) {
        /**如果就一个那就直接返回吧,没啥可操作的*/
        if(nums.length == 1) {
            return;
        }
        /**开始进行划分,redLast表示确定的红的最后一个位置,目前还没有,blueFirst表示确定的蓝色的第一个位置,目前也还没有*/
        int redLast = -1;
        int blueFirst = nums.length;
        int cur = 0;
        while(cur < blueFirst) {
            /**等于的不管 */
            if(nums[cur] == 1) {
                cur ++;
                /**如果是0和红色的最后一个位置的下一个交换,扩充红色区,因为换的是之前的位置,所以这里cur不用验证,也直接++ */
            } else if(nums[cur] == 0) {
                swap(nums, cur++, ++redLast);
            } else {
                /**如果是2,就和蓝色的最后一个位置的前一个交换,扩充红色区,但是这个是从后面缓过来的,需要看看*/
                swap(nums, cur, --blueFirst);
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

标签:cur,nums,int,Leecode,++,75,红色,100,blueFirst
From: https://blog.csdn.net/Chang_Yafei/article/details/142695311

相关文章

  • 代码随想录算法训练营 | 122.买卖股票的最佳时机II,55. 跳跃游戏,45.跳跃游戏II,1005.K次
    122.买卖股票的最佳时机II题目链接:122.买卖股票的最佳时机II文档讲解︰代码随想录(programmercarl.com)视频讲解︰买卖股票的最佳时机II日期:2024-10-03想法:本来还在想什么时候买股票,结果只需要考虑每天的正收益累加就是最大的收益了。Java代码如下:classSolution{public......
  • 20241002每日一题洛谷P1563
    粗看题目我靠,什么方向还变来变去的(哭泣核心思想:圈内右数,圈外左数为整体逆时针数;圈外右数,圈内左数为整体顺时针数运用结构体就有了第一版源码://///define_CRT_SECURE_NO_WARNINGS1include<stdio.h>includestructpeople{intface;charname[12];};intmain(){in......
  • 1002模拟赛
    \(T1\):题面注意:大凡求和求积的变量都要想想要不要开\(long\\long\)别人的一个很好的思路:这道题实在逆序对(\(n,n-1,..1\))上加限制,一串连续的1进行一个\(reverse\)。这给我们的启示是:当同时有两个限制(比如这题中的逆序对数最多和大小限制),可以先考虑一个,看看能产生什么,再把另......
  • Codeforces Round 975 (Div. 2)
    一万四参赛,VP赛时60A.MaxPlusSize一定选择最大值,若有多个最大值,优先选在奇数位置的最大值,后间隔涂上红色。#include<bits/stdc++.h>usingnamespacestd;constintN=105;intT,n,a[N];intmain(){ scanf("%d",&T); while(T--){ scanf("%d",&n); intm......
  • 20241002测试
    move题面:\(T\)组数据,每组数据有\(n\)个数轴上的点\(a_1,a_2,\dots,a_n\)。从原点开始,每次选择一个点未被选择过的点,如果当前在这个点上,那么分数加\(1\),否则向这个点移动\(1\)格。问最高分数。题解:容易发现,要么先往左再往右,要么先往右再往左。先考虑第一种情况,枚举左端......
  • 20241002
    bwtree我们可以设\(dp_{i,0/1}\)表示当前考虑至哪个点,这个节点的子树内选了几个叶子节点#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5,INF=1e9;intn,a[N],dp[N][2];vector<int>g[N];voiddfs(intu,intf){dp[u][0]=(a[u]=......
  • 题解:SP23875 DCEPC14A - Another Version of Inversion
    我们注意到这道题是二维的,所以要用到二维树状数组,不会的可以看一下这篇文章。这题的思路和P1908很像,按价值从大到小排序,排完序之后用树状数组维护,每次把这个数的位置加入到树状数组中,因为是排完序之后,所以之前加入的一定比后加入的大,然后在查询当前这个数前面位置的数(是前面位......
  • LoongArch@微处理器体系结构专利技术研究方法@20241002
    微处理器体系结构专利技术研究方法第一辑:X86指令集总述 微处理器体系结构专利技术研究方法第二辑:x86多媒体指令集 微处理器体系结构专利技术研究方法第三辑:X86指令实现专利技术 ......
  • INCS 775 – Data Center Security
    INCS775–DataCenterSecurityContent:OracleVirtualBoxor/andVMwareWorkstationPlayerinstallationPythonUserisnotinthesudoersfileMininetInstallationInstallingiPerf3onUbuntuStartMininetMininetHostsMininetMininetBuilt-inTopologi......
  • Leetcode 275. H 指数 II
    1.题目基本信息1.1.题目描述给你一个整数数组citations,其中citations[i]表示研究者的第i篇论文被引用的次数,citations已经按照升序排列。计算并返回该研究者的h指数。h指数的定义:h代表“高引用次数”(highcitations),一名科研人员的h指数是指他(她)的(n篇论文中)至......