热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

经典算法大全51例——4.三色旗

经典算法大全51例——4.三色旗算法目录合集地址说明题目原理分析代码实现——Java相关题目其他变形:1.颜色分类(来源:力扣LeetCo


经典算法大全51例——4.三色旗

  • 算法目录合集
    • 地址
    • 说明
  • 题目
    • 原理分析
    • 代码实现——Java
    • 相关题目其他变形:
      • 1.颜色分类(来源:力扣LeetCode)
      • 2.五色旗
        • 分析
        • 代码实现
  • 官方题解
    • 解法
    • 代码——C语言


算法目录合集


地址

   算法目录合集


说明

  该地址指向所有由本人自己所经历的算法习题(也有可能仅仅是一个入门的案例或者是经典案例),仅仅为我做过而且比较有意思的,也许还会有一些我自己想出来的,出于兴趣写在这里,具体格式我会在下面列明,总目录也会在这里出现,方便查阅以及自己进行复习回顾。


题目


  三色旗的问题最早由E.W.Dijkstra所提出,他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人),而多数的作者则使用Three-Color Flag来称之。
  假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子颜色并没有顺序,您希望将之分类,并排列为蓝、白、红的顺序,要如何移动次数才会最少,注意您只能在绳子上进行这个动作,而且一次只能调换两个旗子。


  特别说明

  经过我对题目的分析以及自己尝试过的其他答案和自己所进行的其他变形,我有个拙见:那就是这个旗子原本在绳子上的位置应该是不发生改变的(假如绳子分为0、1、2、3、4、5、6、7,这八个位置,其中2、3、4有旗子,操作过之后,旗子应该所在位置还是2、3、4),如果不加这个限制,是很容易讨巧的,具体我会在后面进行说明。


原理分析

  首先,大家不要讨巧,不要讨巧,不要讨巧!!!否则三体星人会惩戒你的!!!哈哈哈,这题可千万不要把颜色给用1,2,3给代表,然后再来个sort,太low了🤣🤣🤣🤣

  不瞎扯了,下面我说一下正确(自诩🤪🤪)的思路:

  面对这个题,最直观的想法就是:“我先一个一个看,如果是蓝色,就扔到队伍前面去,如果是红色,就扔到队伍后面去,如果是白色,那就不理他。”没错,这就是核心思路,那么怎么实现呢,不利用多余的数组空间,怎么把他们的位置进行置换?这就需要指针了,一个指针指向队伍头,代表蓝色旗子将要被扔的位置,第二个指针指向队伍尾,代表红色旗子将要被扔的位置,第三个指针(序列指针)从队伍头一直往后,对每个旗子进行颜色判断。

  值得说明的是:数组是固定的,当要把元素插入到第一个位置,必将导致大规模的变动,所以需要一个方法,置换两个旗子,如果是蓝色,就与队伍头置换,红色则置换队伍尾;所以这便是我们的核心代码(虽然简单,但是用处很大):

temp = a;a = b;b = temp;

  temptemptemp是临时储存元素,用来交换aaabbb,而交换完了之后,把指针进行位移(如果换了头部,则头部指针后移一位,如果换了尾部,则头部指针前移一位),这里仅仅指对头尾指针的操作,因为对于序列指针是需要分情况进行讨论的。

  惯例,定义好变量:

String temp;int bFlag = 0;int rFlag = nums.length - 1;int search = 0;

  注意

  这里之所以把searchsearchsearch也定位000,是因为并不知道第一个元素是什么颜色,①如果不是蓝色,那么自然是需要操作一下的,这种属于正常情况②如果是蓝色,searchsearchsearch却从111开始,那么造成的结果就是极大可能有一个蓝色是没法进入头部队列的,因为假如旗子为“蓝白白白蓝红”,那么searchsearchsearch从1开始,遇到了三个白色都跳过了,遇到了4号位的蓝色,就会和0号位置的蓝色互换,导致444号位还是蓝色;而把searchsearchsearch设置为000,就是确保000号位即使是蓝色,也不会被searchsearchsearch所“拐卖”走🤪。

  然后理一下逻辑&#xff1a;当while(search<&#61;rFlag)while (search <&#61; rFlag)while(search<&#61;rFlag)的时候进行指针的移动&#xff0c;一直到search>rFlagsearch>rFlagsearch>rFlag了&#xff0c;说明已经遍历完整个数组了&#xff0c;就不需要继续进行了。然后就是对nums[search]nums[search]nums[search]进行条件判断&#xff0c;不同的情况来进行不同操作&#xff0c;于是框架有了&#xff1a;

while (search <&#61; rFlag){switch (nums[search]){case "蓝"://如果是蓝的进行的操作break;case "白"://如果是白的进行的操作break;case "红"://如果是红的进行的操作break;default:break;}
}

  • 对于蓝色的操作&#xff1a;

  蓝色为队伍头的位置&#xff0c;对于他的操作分为这么几个步骤&#xff1a;①searchsearchsearch序列指针进行搜索&#xff0c;发现该位置为蓝色&#xff1b;②将searchsearchsearchbFlagbFlagbFlag两个位置的旗子互换&#xff08;利用临时值temptemptemp&#xff0c;不再赘述&#xff09;&#xff1b;③bFlagbFlagbFlag指针后移&#xff08;为了保证下次置换的旗子为队列头部的第一个非红色旗子&#xff09;&#xff0c;searchsearchsearch指针后移&#xff08;继续判断下一个旗子&#xff09;。

case "蓝":temp &#61; nums[search];nums[search] &#61; nums[bFlag];nums[bFlag] &#61; temp;bFlag&#43;&#43;;search&#43;&#43;;break;

  • 对于白色的操作&#xff1a;

  因为白色是不需要进行位置交换的&#xff0c;所以也不用进行交换&#xff0c;直接后移序列指针就行&#xff0c;就可以保证中间为白色了。

case "白":search&#43;&#43;;break;

  • 对于红色的操作&#xff1a;

  红色的操作相较于蓝色有些特殊&#xff0c;具体我会在步骤之后说一下&#xff0c;红色旗子的操作步骤为&#xff1a;①searchsearchsearch序列指针进行搜索&#xff0c;发现该位置为红色&#xff1b;②将searchsearchsearchrFlagrFlagrFlag两个位置的旗子互换&#xff08;利用临时值temptemptemp&#xff0c;不再赘述&#xff09;&#xff1b;③rFlagrFlagrFlag指针前移&#xff08;为了保证下次置换的旗子为队列尾部的最后一个非蓝色旗子&#xff09;。

  注意

  认真的猿发现了&#xff0c;这里的第三步并没有像操作红色旗子一样&#xff0c;去位移searchsearchsearch&#xff0c;原因其实和searchsearchsearch赋值为000而不是111的原因大同小异&#xff1a;试想一下&#xff0c;我们只是对searchsearchsearch进行了判断&#xff0c;那么是不是队伍尾部换过来的那个旗子的颜色我们并不知道&#xff1f;比如&#xff1a;“蓝红白白蓝红”&#xff0c;searchsearchsearch指针开始判断111号位置&#xff0c;发现了是红色&#xff0c;那么与队伍尾部红色进行交换&#xff0c;好的那么队列变成了“蓝红白白蓝红”&#xff0c;这时候rFlag指针已经指向了444号位置&#xff08;倒数第二个&#xff09;&#xff0c;此时如果search&#43;1search&#43;1search&#43;1&#xff0c;是不是就把111号位的红色跳过去了&#xff1f;没错&#xff0c;又被searchsearchsearch“绑架”了&#xff0c;所以此时searchsearchsearch不能&#43;1&#43;1&#43;1&#xff0c;依旧要对此元素进行判断。

case "红":temp &#61; nums[search];nums[search] &#61; nums[rFlag];nums[rFlag] &#61; temp;rFlag--;break;

  题外话&#xff1a;
  最终可以发现&#xff0c;searchsearchsearch没有移动到队伍末尾&#xff0c;但是其实他已经遍历了整个数组了。


代码实现——Java

/*** com** &#64;author g55zhw* &#64;create 2020-09-18-09-41*/
public class SortFlag {public void sortColors(String[] nums) {//按照蓝色、白色、红色顺序排列String temp;int bFlag &#61; 0;int rFlag &#61; nums.length - 1;int search &#61; 0;while (search <&#61; rFlag){switch (nums[search]){case "蓝":temp &#61; nums[search];nums[search] &#61; nums[bFlag];nums[bFlag] &#61; temp;bFlag&#43;&#43;;search&#43;&#43;;break;case "白":search&#43;&#43;;break;case "红":temp &#61; nums[search];nums[search] &#61; nums[rFlag];nums[rFlag] &#61; temp;rFlag--;break;default:break;}}}
}

测试代码

/*** com** &#64;author g55zhw* &#64;create 2020-09-18-09-41*/
public class SortFlagTest {&#64;Testpublic void sortColors() {SortFlag s &#61; new SortFlag();String[] arr &#61; new String[]{"红","白","蓝","红","蓝","白","蓝","蓝","红","白"};s.sortColors(arr);System.out.println(Arrays.toString(arr));}
}

结果演示

[,,,,,,,,,]

相关题目其他变形&#xff1a;


1.颜色分类&#xff08;来源&#xff1a;力扣LeetCode&#xff09;

  这个力扣的三色旗问题是非常基础的&#xff0c;在这里就不做过多的计算了&#xff0c;仅仅把旗子匹配颜色置换成数字就可以了&#xff0c;大家自己看看把&#xff0c;我的leetcode也不收录了&#xff0c;没啥意思&#xff0c;链接给你们&#xff0c;自己去看&#xff0c;可以练练手&#xff0c;75.颜色分类&#xff08;不过那里面用其他方式的解题思路大家可以看看&#xff0c;学习学习&#xff0c;思路学会了真的很重要&#xff09;。

资源耗用情况


2.五色旗


分析

  五色旗其实操作原理是一模一样&#xff0c;只不过刚开始先把需要排列再最中间的三种颜色进行过滤&#xff08;当成三色旗里的白色一样&#xff0c;不去理会&#xff09;&#xff0c;等把两端的旗子排好之后&#xff0c;再操作中间的三种颜色&#xff0c;然后就可以实现了&#xff0c;多色就每次只整理两端的旗子&#xff0c;慢慢压缩到中间&#xff0c;即可。(四色原理一样,多色也可以此类推)


代码实现

package com;/*** com** &#64;author g55zhw* &#64;create 2020-09-18-14-52*/
public class SortFlagFive {public void sortColors(String[] nums) {//按照红色、白色、蓝色、绿色、黑色顺序排列。String temp;int head &#61; 0;int tail &#61; nums.length - 1;int search &#61; 0;while (search <&#61; tail){switch (nums[search]){case "红":temp &#61; nums[search];nums[search] &#61; nums[head];nums[head] &#61; temp;head&#43;&#43;;search&#43;&#43;;break;case "白":case "蓝":case "绿":search&#43;&#43;;break;case "黑":temp &#61; nums[search];nums[search] &#61; nums[tail];nums[tail] &#61; temp;tail--;break;default:break;}}search &#61; head;while (search <&#61; tail){switch (nums[search]){case "白":temp &#61; nums[search];nums[search] &#61; nums[head];nums[head] &#61; temp;head&#43;&#43;;search&#43;&#43;;break;case "蓝":search&#43;&#43;;break;case "绿":temp &#61; nums[search];nums[search] &#61; nums[tail];nums[tail] &#61; temp;tail--;break;default:break;}}}
}

测试代码

/*** com** &#64;author g55zhw* &#64;create 2020-09-18-14-55*/
public class SortFlagTest {&#64;Testpublic void sortColorsFive() {SortFlagFive s &#61; new SortFlagFive();String[] arr &#61; new String[]{"红","白","蓝","红","白","蓝","绿","黑","红","绿","黑","绿","黑","红","白","蓝","绿","黑","绿","黑","红"};s.sortColors(arr);System.out.println(Arrays.toString(arr));}
}

结果演示

[,,,,,,,,,,, 绿, 绿, 绿, 绿, 绿,,,,,]

官方题解


解法

  在一条绳子上移动&#xff0c;在程式中也就意味只能使用一个阵列&#xff0c;而不使用其它的阵列来作辅助&#xff0c;问题的解法很简单&#xff0c;您可以自己想像一下在移动旗子&#xff0c;从绳子开头进行&#xff0c;遇到蓝色往前移&#xff0c;遇到白色留在中间&#xff0c;遇到红色往后移&#xff0c;如下所示&#xff1a;
  只是要让移动次数最少的话&#xff0c;就要有些技巧&#xff1a;


  • 如果图中W所在的位置为白色&#xff0c;则W&#43;1&#xff0c;表示未处理的部份移至至白色群组。
  • 如果W部份为蓝色&#xff0c;则B与W的元素对调&#xff0c;而B与W必须各&#43;1&#xff0c;表示两个群组都多了一个元素。
  • 如果W所在的位置是红色&#xff0c;则将W与R交换&#xff0c;但R要减1&#xff0c;表示未处理的部份减1。
    题目
      注意B、W、R并不是三色旗的个数&#xff0c;它们只是一个移动的指标&#xff1b;什幺时候移动结束呢&#xff1f;一开始时未处理的R指标会是等于旗子的总数&#xff0c;当R的索引数减至少于W的索引数时&#xff0c;表示接下来的旗子就都是红色了&#xff0c;此时就可以结束移动。

代码——C语言

#include
#include
#include
#define BLUE &#39;b&#39;
#define WHITE &#39;w&#39;
#define RED &#39;r&#39;
#define SWAP( x, y ) { char temp; \temp &#61; color[x]; \color[x] &#61; color[y]; \color[y] &#61; temp; }
int main(){char color[] &#61; { &#39;r&#39;, &#39;w&#39;, &#39;b&#39;, &#39;w&#39;, &#39;w&#39;, &#39;b&#39;, &#39;r&#39;, &#39;b&#39;, &#39;w&#39;, &#39;r&#39;,&#39;\0&#39; };int wFlag &#61; 0;int bFlag &#61; 0;int rFlag &#61; strlen( color ) - 1;int i;for ( i &#61; 0; i < strlen( color ); i&#43;&#43; ){printf( "%c ", color[i] );}printf( "\n" );while ( wFlag <&#61; rFlag ){if ( color[wFlag] &#61;&#61; WHITE ){wFlag&#43;&#43;;}else if ( color[wFlag] &#61;&#61; BLUE ){SWAP( bFlag, wFlag );bFlag&#43;&#43;; wFlag&#43;&#43;;}else {while ( wFlag < rFlag && color[rFlag] &#61;&#61; RED ){rFlag--;}SWAP( rFlag, wFlag );rFlag--;}}for ( i &#61; 0; i < strlen( color ); i&#43;&#43; ){printf( "%c ", color[i] );}printf( "\n" );return(0);
}

推荐阅读
  • 具备括号和分数功能的高级四则运算计算器
    本研究基于C语言开发了一款支持括号和分数运算的高级四则运算计算器。该计算器通过模拟手算过程,对每个运算符进行优先级标记,并按优先级从高到低依次执行计算。其中,加减运算的优先级最低,为0。此外,该计算器还支持复杂的分数运算,能够处理包含括号的表达式,提高了计算的准确性和灵活性。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • Objective-C 中的委托模式详解与应用 ... [详细]
  • Android中将独立SO库封装进JAR包并实现SO库的加载与调用
    在Android开发中,将独立的SO库封装进JAR包并实现其加载与调用是一个常见的需求。本文详细介绍了如何将SO库嵌入到JAR包中,并确保在外部应用调用该JAR包时能够正确加载和使用这些SO库。通过这种方式,开发者可以更方便地管理和分发包含原生代码的库文件,提高开发效率和代码复用性。文章还探讨了常见的问题及其解决方案,帮助开发者避免在实际应用中遇到的坑。 ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 深入解析 Golang 中 Context 的功能与应用
    本文详细探讨了 Golang 中 Context 的核心功能及其应用场景,通过深入解析其工作机制,帮助读者更好地理解和运用这一重要特性,对于提升代码质量和项目开发效率具有重要的参考价值。 ... [详细]
  • 无论是计算机专业学生还是非计算机专业的学习者,在掌握C语言的过程中可能会遇到诸多挑战,不清楚从何入手。为此,本文系统地梳理了2019年福建省C语言的核心知识点,并结合最新的技术进展进行了详细总结,旨在为初学者提供全面的学习指导。文章不仅涵盖了基础语法和数据结构,还深入探讨了指针、内存管理和算法优化等高级主题,帮助读者快速提升编程能力。 ... [详细]
  • 蓝桥杯物联网基础教程:通过GPIO输入控制LED5的点亮与熄灭
    本教程详细介绍了如何利用STM32的GPIO接口通过输入信号控制LED5的点亮与熄灭。内容涵盖GPIO的基本配置、按键检测及LED驱动方法,适合具有STM32基础的读者学习和实践。 ... [详细]
  • 本文详细介绍了在CodeUp平台中实现大数进制转换的技术方法。具体而言,该问题要求将一个最多包含30位数字的十进制非负整数转换为二进制表示。输入数据包含多行,每行包含一个不超过30位的十进制非负整数。通过高效的算法设计,确保了大数转换的准确性和性能。 ... [详细]
  • 在探讨P1923问题时,我们发现手写的快速排序在最后两个测试用例中出现了超时现象,这在意料之中,因为该题目实际上要求的是时间复杂度为O(n)的算法。进一步研究题解后,发现有选手使用STL中的`nth_element`函数成功通过了所有测试点。本文将详细分析这一现象,并提出相应的优化策略。 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 本文探讨了 Kafka 集群的高效部署与优化策略。首先介绍了 Kafka 的下载与安装步骤,包括从官方网站获取最新版本的压缩包并进行解压。随后详细讨论了集群配置的最佳实践,涵盖节点选择、网络优化和性能调优等方面,旨在提升系统的稳定性和处理能力。此外,还提供了常见的故障排查方法和监控方案,帮助运维人员更好地管理和维护 Kafka 集群。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
author-avatar
吴素婷76625
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有