經典演算法大全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;

?? t e m p temp temp是臨時儲存元素，用來交換 a a a與 b b b，而交換完了之后，把指標進行位移（如果換了頭部，則頭部指標后移一位，如果換了尾部，則頭部指標前移一位），這里僅僅指對頭尾指標的操作，因為對于序列指標是需要分情況進行討論的，

??慣例，定義好變數：

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

??注意

??這里之所以把 s e a r c h search search也定位 0 0 0，是因為并不知道第一個元素是什么顏色，①如果不是藍色，那么自然是需要操作一下的，這種屬于正常情況②如果是藍色， s e a r c h search search卻從 1 1 1開始，那么造成的結果就是極大可能有一個藍色是沒法進入頭部佇列的，因為假如旗子為“藍白白白藍紅”，那么 s e a r c h search search從1開始，遇到了三個白色都跳過了，遇到了4號位的藍色，就會和0號位置的藍色互換，導致 4 4 4號位還是藍色；而把 s e a r c h search search設定為 0 0 0，就是確保 0 0 0號位即使是藍色，也不會被 s e a r c h search search所“拐賣”走🤪，

??然后理一下邏輯：當 w h i l e ( s e a r c h < = r F l a g ) while (search <= rFlag) while(search<=rFlag)的時候進行指標的移動，一直到 s e a r c h > r F l a g search>rFlag search>rFlag了，說明已經遍歷完整個陣列了，就不需要繼續進行了，然后就是對 n u m s [ s e a r c h ] nums[search] nums[search]進行條件判斷，不同的情況來進行不同操作，于是框架有了：

while (search <= rFlag){
	switch (nums[search]){
		case "藍":
			//如果是藍的進行的操作
			break;
		case "白":
			//如果是白的進行的操作
			break;
		case "紅":
			//如果是紅的進行的操作
			break;
		default:
			break;
	}
}

對于藍色的操作：

??藍色為隊伍頭的位置，對于他的操作分為這么幾個步驟：① s e a r c h search search序列指標進行搜索，發現該位置為藍色；②將 s e a r c h search search與 b F l a g bFlag bFlag兩個位置的旗子互換（利用臨時值 t e m p temp temp，不再贅述）；③ b F l a g bFlag bFlag指標后移（為了保證下次置換的旗子為佇列頭部的第一個非紅色旗子）， s e a r c h search search指標后移（繼續判斷下一個旗子），

		case "藍":
			temp = nums[search];
			nums[search] = nums[bFlag];
			nums[bFlag] = temp;
			bFlag++;
			search++;
			break;

對于白色的操作：

??因為白色是不需要進行位置交換的，所以也不用進行交換，直接后移序列指標就行，就可以保證中間為白色了，

		case "白":
			search++;
			break;

對于紅色的操作：

??紅色的操作相較于藍色有些特殊，具體我會在步驟之后說一下，紅色旗子的操作步驟為：① s e a r c h search search序列指標進行搜索，發現該位置為紅色；②將 s e a r c h search search與 r F l a g rFlag rFlag兩個位置的旗子互換（利用臨時值 t e m p temp temp，不再贅述）；③ r F l a g rFlag rFlag指標前移（為了保證下次置換的旗子為佇列尾部的最后一個非藍色旗子），

??注意

??認真的猿發現了，這里的第三步并沒有像操作紅色旗子一樣，去位移 s e a r c h search search，原因其實和 s e a r c h search search賦值為 0 0 0而不是 1 1 1的原因大同小異：試想一下，我們只是對 s e a r c h search search進行了判斷，那么是不是隊伍尾部換過來的那個旗子的顏色我們并不知道？比如：“藍紅白白藍紅”， s e a r c h search search指標開始判斷 1 1 1號位置，發現了是紅色，那么與隊伍尾部紅色進行交換，好的那么佇列變成了“藍紅白白藍紅”，這時候rFlag指標已經指向了 4 4 4號位置（倒數第二個），此時如果 s e a r c h + 1 search+1 search+1，是不是就把 1 1 1號位的紅色跳過去了？沒錯，又被 s e a r c h search search“綁架”了，所以此時 s e a r c h search search不能 + 1 +1 +1，依舊要對此元素進行判斷，

		case "紅":
			temp = nums[search];
			nums[search] = nums[rFlag];
			nums[rFlag] = temp;
			rFlag--;
			break;

??題外話：
??最終可以發現， s e a r c h search search沒有移動到隊伍末尾，但是其實他已經遍歷了整個陣列了，

代碼實作——Java

/**
 * com
 *
 * @author g55zhw
 * @create 2020-09-18-09-41
 */
public class SortFlag {
    public void sortColors(String[] nums) {
        //按照藍色、白色、紅色順序排列
        String temp;
        int bFlag = 0;
        int rFlag = nums.length - 1;
        int search = 0;
        while (search <= rFlag){
            switch (nums[search]){
                case "藍":
                    temp = nums[search];
                    nums[search] = nums[bFlag];
                    nums[bFlag] = temp;
                    bFlag++;
                    search++;
                    break;
                case "白":
                    search++;
                    break;
                case "紅":
                    temp = nums[search];
                    nums[search] = nums[rFlag];
                    nums[rFlag] = temp;
                    rFlag--;
                    break;
                default:
                    break;
            }
        }
    }
}

測驗代碼

/**
 * com
 *
 * @author g55zhw
 * @create 2020-09-18-09-41
 */
public class SortFlagTest {

    @Test
    public void sortColors() {
        SortFlag s = new SortFlag();
        String[] arr = new String[]{"紅","白","藍","紅","藍","白","藍","藍","紅","白"};
        s.sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
}

結果演示

[藍, 藍, 藍, 藍, 白, 白, 白, 紅, 紅, 紅]

相關題目其他變形：

1.顏色分類（來源：力扣LeetCode）

??這個力扣的三色旗問題是非常基礎的，在這里就不做過多的計算了，僅僅把旗子匹配顏色置換成數字就可以了，大家自己看看把，我的leetcode也不收錄了，沒啥意思，鏈接給你們，自己去看，可以練練手，75.顏色分類（不過那里面用其他方式的解題思路大家可以看看，學習學習，思路學會了真的很重要），

資源耗用情況

2.五色旗

分析

??五色旗其實操作原理是一模一樣，只不過剛開始先把需要排列再最中間的三種顏色進行過濾（當成三色旗里的白色一樣，不去理會），等把兩端的旗子排好之后，再操作中間的三種顏色，然后就可以實作了，多色就每次只整理兩端的旗子，慢慢壓縮到中間，即可，(四色原理一樣,多色也可以此類推)

代碼實作

package com;

/**
 * com
 *
 * @author g55zhw
 * @create 2020-09-18-14-52
 */
public class SortFlagFive {
    public void sortColors(String[] nums) {
        //按照紅色、白色、藍色、綠色、黑色順序排列，
        String temp;
        int head = 0;
        int tail = nums.length - 1;
        int search = 0;
        while (search <= tail){
            switch (nums[search]){
                case "紅":
                    temp = nums[search];
                    nums[search] = nums[head];
                    nums[head] = temp;
                    head++;
                    search++;
                    break;
                case "白":
                case "藍":
                case "綠":
                    search++;
                    break;
                case "黑":
                    temp = nums[search];
                    nums[search] = nums[tail];
                    nums[tail] = temp;
                    tail--;
                    break;
                default:
                    break;
            }
        }
        search = head;
        while (search <= tail){
            switch (nums[search]){
                case "白":
                    temp = nums[search];
                    nums[search] = nums[head];
                    nums[head] = temp;
                    head++;
                    search++;
                    break;
                case "藍":
                    search++;
                    break;
                case "綠":
                    temp = nums[search];
                    nums[search] = nums[tail];
                    nums[tail] = temp;
                    tail--;
                    break;
                default:
                    break;
            }
        }
    }
}

測驗代碼

/**
 * com
 *
 * @author g55zhw
 * @create 2020-09-18-14-55
 */
public class SortFlagTest {
    @Test
    public void sortColorsFive() {
        SortFlagFive s = new SortFlagFive();
        String[] arr = new String[]{"紅","白","藍","紅","白","藍","綠","黑","紅","綠","黑","綠","黑","紅","白","藍","綠","黑","綠","黑","紅"};
        s.sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
}

結果演示

[紅, 紅, 紅, 紅, 紅, 白, 白, 白, 藍, 藍, 藍, 綠, 綠, 綠, 綠, 綠, 黑, 黑, 黑, 黑, 黑]

官方題解

解法

??在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進行，遇到藍色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：
??只是要讓移動次數最少的話，就要有些技巧：

如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組，
如果W部份為藍色，則B與W的元素對調，而B與W必須各+1，表示兩個群組都多了一個元素，
如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1，

??注意B、W、R并不是三色旗的個數，它們只是一個移動的指標；什幺時候移動結束呢？一開始時未處理的R指標會是等于旗子的總數，當R的索引數減至少于W的索引數時，表示接下來的旗子就都是紅色了，此時就可以結束移動，

代碼——C語言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED	'r'
#define SWAP( x, y ) { char temp; \
		       temp	= color[x]; \
		       color[x] = color[y]; \
		       color[y] = temp; }
int main(){
	char color[] = { 'r', 'w', 'b', 'w', 'w', 'b', 'r', 'b', 'w', 'r','\0' };
	int	wFlag = 0;
	int	bFlag = 0;
	int	rFlag = strlen( color ) - 1;
	int	i;
	for ( i = 0; i < strlen( color ); i++ ){
		printf( "%c ", color[i] );
	}
	printf( "\n" );
	while ( wFlag <= rFlag ){
		if ( color[wFlag] == WHITE ){
			wFlag++;
		}
		else if ( color[wFlag] == BLUE ){
			SWAP( bFlag, wFlag );
			bFlag++; 
			wFlag++;
		}else {
			while ( wFlag < rFlag && color[rFlag] == RED ){
				rFlag--;
			}
			SWAP( rFlag, wFlag );
			rFlag--;
		}
	}
	for ( i = 0; i < strlen( color ); i++ ){
		printf( "%c ", color[i] );
	}
	printf( "\n" );
	return(0);
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/89290.html

標籤：其他

上一篇：Css打造伸縮時間軸樣式的WordPress歸檔頁面archive.php

下一篇：WebDriver常用API