算法目录合集
该地址指向所有由本人自己所经历的算法习题(也有可能仅仅是一个入门的案例或者是经典案例),仅仅为我做过而且比较有意思的,也许还会有一些我自己想出来的,出于兴趣写在这里,具体格式我会在下面列明,总目录也会在这里出现,方便查阅以及自己进行复习回顾。
三色旗的问题最早由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是临时储存元素,用来交换aaa与bbb,而交换完了之后,把指针进行位移(如果换了头部,则头部指针后移一位,如果换了尾部,则头部指针前移一位),这里仅仅指对头尾指针的操作,因为对于序列指针是需要分情况进行讨论的。
惯例,定义好变量:
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;}
}
蓝色为队伍头的位置&#xff0c;对于他的操作分为这么几个步骤&#xff1a;①searchsearchsearch序列指针进行搜索&#xff0c;发现该位置为蓝色&#xff1b;②将searchsearchsearch与bFlagbFlagbFlag两个位置的旗子互换&#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;
因为白色是不需要进行位置交换的&#xff0c;所以也不用进行交换&#xff0c;直接后移序列指针就行&#xff0c;就可以保证中间为白色了。
case "白":search&#43;&#43;;break;
红色的操作相较于蓝色有些特殊&#xff0c;具体我会在步骤之后说一下&#xff0c;红色旗子的操作步骤为&#xff1a;①searchsearchsearch序列指针进行搜索&#xff0c;发现该位置为红色&#xff1b;②将searchsearchsearch与rFlagrFlagrFlag两个位置的旗子互换&#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;但是其实他已经遍历了整个数组了。
/*** 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));}
}
结果演示
[蓝, 蓝, 蓝, 蓝, 白, 白, 白, 红, 红, 红]
这个力扣的三色旗问题是非常基础的&#xff0c;在这里就不做过多的计算了&#xff0c;仅仅把旗子匹配颜色置换成数字就可以了&#xff0c;大家自己看看把&#xff0c;我的leetcode也不收录了&#xff0c;没啥意思&#xff0c;链接给你们&#xff0c;自己去看&#xff0c;可以练练手&#xff0c;75.颜色分类&#xff08;不过那里面用其他方式的解题思路大家可以看看&#xff0c;学习学习&#xff0c;思路学会了真的很重要&#xff09;。
五色旗其实操作原理是一模一样&#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;
#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);
}