Posted on 2007-03-14 11:09
semovy 阅读(327)
评论(0) 编辑 收藏 所属分类:
JAVA基础
网上看到一道java算法题，题目如下： 用1，2，2，3，4，5，这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”与“5”不能相连。
我的解题思路是这样的：这是一个典型的遍历题型，可以用递归实现。在每一次递归中，要解决的问题包括，“4”不能排第3位，“1”与“5”不能相连，“2”的个数最多为2个且要保证不能重复，其他数字也要不重复。最难解决的就是要使“2”不重复，我假定两个2的顺序不变，也就是在排列组合中两个2始终保持一种出现顺序，这样就不会重复。其他的约束看一下注释就可以明白了。网上有个使用图的解法，尽管很有创意，但原理性差不多，而使用TreeSet的方法颇让人跌眼镜。Java代码如下：
package test;
/** *//**
* 用1，2，2，3，4，5，这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”与“5”不能相连。
* @author kafka0102
*
*/
public class ATest 
{
private static boolean is1Or5(char a,char b){
if(a=='1' && b=='5')return true;
if(a=='5' && b=='1')return true;
return false;
}
private static int countOf2(char[] num,int index){
int n=0;
for(int i=0;i<index;i++){
if(num[i]=='2')n++;
}
return n;
}
private static boolean hasSameNumber(int index,char a, char[] num){
for(int i=0;i<index;i++){
if(num[i]==a)return true;
}
return false;
}
public static int testArrange(char[] number,char[] num,int index){
int size = 0;//组合的个数
int pos1=1,pos2=2;//该变量为重复的2的数组位置，可以提取出来作为参数
int emp = countOf2(num,index);//得到当前的数组中有几个2
for(int i=0;i<num.length;i++){
if(number[i]=='2'){//当前的数字为2
if(emp >= 2){//数组中2的个数多于2个
continue;
}else if(emp == 1){//数组中有一个2时，要求当前的2不能为位置1的2
if(i==pos1)continue;
}else{
if(i==pos2)continue;//数组中没有2时，要求当前的2不能为位置2的2
}
}else{
if(index==2 && number[i]=='4')continue;//去除4
if(index>0 && is1Or5(num[index-1],number[i]))continue;//去除相邻的1和5
if(hasSameNumber(index,number[i], num))continue;//去除重复数字
}
num[index] = number[i];
if(index==5){
System.out.println(num);
size++;
}else{
size = size + testArrange(number,num,index+1);
}
}
return size;
}
public static void aTest(){
char[] number = {'1','2','2','3','4','5'};
char[] num = new char[number.length];
int size =0;
size = testArrange(number,num,0);
System.out.println("size="+size);
}
public static void main(String[] args) {
aTest();
}
}