import java.util.Arrays;
/**
问题:
假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子颜色并没有顺序,
您希望将之分类,并排列为蓝、白、红的顺序,要如何移动次数才会最少,注意您只能在绳
子上进行这个动作,而且一次只能调换两个旗子。
网上的解法大多类似:
在一条绳子上移动,在程式中也就意味只能使用一个阵列,而不使用其它的阵列来作辅助,
问题的解法很简单,您可以自己想像一下在移动旗子,从绳子开头进行,遇到蓝色往前移,
遇到白色留在中间,遇到红色往后移。
只是要让移动次数最少的话,就要有些技巧:
如果图中W所在的位置为白色,则W+1,表示未处理的部份移至至白色群组。
如果W部份为蓝色,则B与W的元素对调,而B与W必须各+1,表示两个群组都多了一个元素。
如果W所在的位置是红色,则将W与R交换,但R要减1,表示未处理的部份减1。
注意B、W、R并不是三色旗的个数,它们只是一个移动的指标;
什么时候移动结束呢?一开始时未处理的R指标会是等于旗子的总数,
当R的索引数减至少于W的索引数时,表示接下来的旗子就都是红色了,此时就可以结束移动
其实这个算法不复杂,自己拿一个实例来把算法走一遍就理解了
核心就是维护b,w,r这三个指针(下标):
w作为当前元素的下标,而b则表示下标在b之前的旗子颜色都是蓝色,r表示下标在r后面的都是红色,不符合这个条件的,就交换
*/
public class ThreeColorFlag {
public static void main(String[] args) {
char[] flags = "rbbwwbrbw".toCharArray();
sort(flags);
System.out.println(Arrays.toString(flags));
}
public static void sort(char[] flags) {
if (flags == null || flags.length <= 1) {
return;
}
int b = 0;
int w = 0;
int r = flags.length - 1;
while (w <= r) {
switch (flags[w]) {
case 'w':
w++;
break;
case 'b':
swap(flags, w, b);
w++;
b++; //b总是跟在w后面
break;
case 'r':
swap(flags, w, r);
r--;
break;
default:
throw new IllegalArgumentException("invalid input");
}
}
}
private static void swap(char[] array, int i, int j) {
char tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
分享到:
相关推荐
java算法三色旗算法 真的不错啊 java版
用javascript来编写三色旗算法的源码,并且带有交换旗子的过程
三色旗问题 * 最左边开始,遇到蓝色向左移,遇到白色不动,遇到红色右移
三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长...
10.12.1 三色旗算法 335 10.12.2 三色旗求解 337 10.13 渔夫捕鱼 339 10.13.1 渔夫捕鱼算法 339 10.13.2 渔夫捕魚求解 340 10.14 爱因斯坦的阶梯 341 10.14.1 爱因斯坦的阶梯算法 341 10.14.2 爱因斯坦的...
三色旗的问题最早由E.W.Dijkstra所提出,他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人),而多数的作者则使用Three-Color Flag来称之。 假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子...
数据结构经典算法他全 如 河内之塔 三色旗 老鼠走迷宫 八皇后等等
智能分拣系统(目前仅有智能分拣模拟器,以后会扩展汉诺塔、三色旗等)共有三个版本选择:免费介绍版、竞赛版、高级版,免费介绍版仅能查看功能,操作仅限于10步;竞赛版可" + "随机或手动放置箱子,可练习分拣方法...
C++的各种经典算法大全包括河内之塔,费式数列,三色旗,走迷宫,走棋盘,八皇后,背包问题等等一系列经典算法
C/C++的51个经典算法实例,包含有经典的河内之塔,费式数列,巴斯卡三角形,三色旗,老鼠走迷宫,八皇后,背包问题等,每个实例都有解析以及算法代码。
数据结构与算法中的经典算法(C语言),如三色旗问题,八皇后问题,汉诺塔问题等
黑白棋,八皇后,哥德巴赫猜想,自守数,矩阵运算,三色旗,青蛙过河等问题。
数据结构经典算法大全+如+河内之塔+三色旗+老鼠走迷宫
AlgorithmJava 用 java 写的一些算法问题,目前包括 八皇后问题 八枚银币 杨辉三角 汉诺塔 老鼠走迷宫 排列组合 骑士走棋盘 三色旗 生命游戏 字符串查找