Go语言视频零基础入门到精通

javalearner

问题：
    假设有一根绳子，上面有一些红、白、蓝色的旗子。起初旗子的顺序是任意的，现在要求用最少的次数移动这些旗子，使得它们按照蓝、白、红的顺序排列。注意只能在绳子上操作，并且一次只能调换两个旗子。 解法：从绳子的开头（最左边）开始，遇到蓝色的往前移，遇到白色的不动，遇到红色的往后移。  注：我们这里说的前移指往左，后移指往右。

    我们可以定义三个指针 a、b、c 。从下图可以看出，a和b指向第一个元素，c指向最后一个元素。a的作用是确保蓝色的旗子移到左边，而c的作用是确保红色的旗子移到右边。b则用于顺序访问各个旗子。
   再来看具体的代码实现，先看下图：  
  
   
   
     
   

     
   
  


思路如下：
    查看b所指向的旗子的颜色：
      如果是白色的，则不移动任何旗子（因为要求白色的旗子在中间，所以不去动它），将b往后移一位。      如果是红色的，此时将b所指向的旗子和c所指向的旗子交换位置，同时c往前移一位。（交换后c指向的已经是红色的旗子了，所以可以往前移一位了）。      如果是蓝色的，此时将b所指向的旗子和a所指向的旗子交换位置，同时a往后移一位。（交换后a指向的已经是蓝色的旗子了，所以可以往后移一位了）。这里要注意的是b也要后移一位。

注意的细节：

第一，当b指向的是红色而和c交换时，如果此时c指向的是红色，显然没有必要把两个红色的旗子交换。所以这时应该把c前移，直到c指向的不是红色的时候才和b指向的旗子交换。当然移动时必须确保b<c。  第二，同样地，当b指向的是蓝色而要和a的指向交换时，如果a指向的不是蓝色，则交换。否则如果a指向的是蓝色，则也没有必要把两个蓝色的旗子交换。所以这时应该把a和b都往后移一位。

1. import java.util.*;  
   
2. public class ThreeColorFlag {  
   
3.       
   
4.     public static void main(String[] args) {           
   
5.          
   
6.           System.out.println("请输入三色旗的顺序(例如 BRRWWB)：");  
   
7.           Scanner scanner=new Scanner(System.in);  
   
8.           String s=scanner.next();  
   
9.           ThreeColorFlag tcf=new ThreeColorFlag();  
   
10.           s=tcf.move(s.toUpperCase().toCharArray());  
    
11.           System.out.println("排列好后的顺序："+s);  
    
12.     }  
    
13.     //互相交换   
    
14.     public void change(char[] flags,int x,int y){  
    
15.          
    
16.         System.out.println("交换前："+new String(flags));  
    
17.         char temp=flags[x];  
    
18.         flags[x]=flags[y];  
    
19.         flags[y]=temp;   
    
20.         System.out.println((x+1)+" 号和 "+(y+1)+" 号交换");  
    
21.         System.out.println("交换后："+new String(flags));  
    
22.     }  
    
23.     public String move(char[] flags){  
    
24.          
    
25.          int a=0,b=0;  
    
26.          int c=flags.length-1;  
    
27.            
    
28.          while(b<=c){  
    
29.              switch (flags[b]){  
    
30.                case "W":  
    
31.                     b++;  
    
32.                     break;  
    
33.                case "B":  
    
34.                    if(flags[a]=="B")  
    
35.                        {a++;b++;}  
    
36.                    else{  
    
37.                    change(flags, a, b);  
    
38.                    a++;  
    
39.                    b++;  
    
40.                    }  
    
41.                    break;  
    
42.                case "R":  
    
43.                  while(b< c && flags[c]=="R")  
    
44.                        c--;  
    
45.                  if(flags[b]==flags[c])  return new String(flags);
    
46.                          change(flags, b, c);  
    
47.                       c--;
    
48.                    break;  
    
49.              }      
    
50.               
    
51.          }  
    
52.          return new String(flags);  
    
53.     }  
    
54. }  
    

复制代码

  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/19/000959609.zip