热门标签 | 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语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 来自FallDream的博客,未经允许,请勿转载,谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]
  • 实现系统调用
    实现系统调用一、实验环境​本次操作还是基于上次编译Linux0.11内核的实验环境进行操作。环境如下:二、实验目标​通过对上述实验原理的认识,相信 ... [详细]
  • 编译原理中的语法分析方法探讨
    本文探讨了在编译原理课程中遇到的复杂文法问题,特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略,包括递归下降解析、运算符优先级解析等,并提供了相关示例。 ... [详细]
  • 2022年4月15日的算法练习题,包括最长公共子序列和线段树的应用。 ... [详细]
  • 本文详细介绍了在Luat OS中如何实现C与Lua的混合编程,包括在C环境中运行Lua脚本、封装可被Lua调用的C语言库,以及C与Lua之间的数据交互方法。 ... [详细]
  • 本文提供了一个使用C语言实现的顺序表区间元素删除功能的完整代码示例。该程序首先初始化一个顺序表,然后根据用户输入的数据进行插入操作,最后根据指定的区间范围删除相应的元素,并输出最终的顺序表。 ... [详细]
  • 本文探讨了Java中有效停止线程的多种方法,包括使用标志位、中断机制及处理阻塞I/O操作等,旨在帮助开发者避免使用已废弃的危险方法,确保线程安全和程序稳定性。 ... [详细]
  • Java实现实时更新的日期与时间显示
    本文介绍了如何使用Java编程语言来创建一个能够实时更新显示系统当前日期和时间的小程序。通过使用Swing库中的组件和定时器功能,可以实现界面友好且功能强大的时间显示应用。 ... [详细]
  • 本文介绍了一种在 Android 开发中动态修改 strings.xml 文件中字符串值的有效方法。通过使用占位符,开发者可以在运行时根据需要填充具体的值,从而提高应用的灵活性和可维护性。 ... [详细]
  • 最近遇到了一个关于单链表的编程问题,这是来自福富公司的笔试题目。以往我通常使用C语言来解决这类问题,但这次决定尝试用Java来实现。该题目要求实现一个单链表,并完成特定的方法。 ... [详细]
  • Android 中的布局方式之线性布局
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 本文将深入探讨C语言中的位操作符——按位与(&)、按位或(|)和按位异或(^),通过具体示例解释这些操作符如何在位级别上对数据进行操作。 ... [详细]
  • JUnit下的测试和suite
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • PHP面试题精选及答案解析
    本文精选了新浪PHP笔试题及最新的PHP面试题,并提供了详细的答案解析,帮助求职者更好地准备PHP相关的面试。 ... [详细]
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社区 版权所有