Java经典算法集2009/04/0217:49算法
程序题:
该公司笔试题就1个,要求在10分钟内作完。
题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
staticint[]bits=newint[]{1,2,3,4,5};
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
sort("",bits);
}
privatestaticvoidsort(Strin
gprefix,int[]a){
if(a.length==1){
System.out.println(prefix+a[0]);
}
for(inti=0;i
sort(prefix+a[i],copy(a,i));
}
}
privatestaticint[]copy(int[]a,intindex){
int[]b=newint[a.length-1];
System.arraycopy(a,0,b,0,index);
System.arraycopy(a,index+1,b,index,a.length-index-1);
returnb;
}
**********************************************************************
基本思路:
1把问题归结为图结构的遍历问题。实际上6个数字就是六个结点,把六个结点连接成无向连通图,对于每一个结点求这个图形的遍历路径,所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2显然这个结果集还未达到题目的要求。从以下几个方面考虑:
1.3,5不能相连:实际要求这个连通图的结点3,5之间不能连通,可在构造图结构时就满足改条件,然后再遍历图。
2.不能有重复:考虑到有两个2,明显会存在重复结果,可以把结果集放在TreeSet中过滤重复结果
3.4不能在第三位:仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构,最后的代码是:
importjava.util.Iterator;
importjava.util.TreeSet;
publicclassTestQuestion{
privateString[]b=newString[]{"1","2","2","3","4","5"};
privateintn=b.length;
privateboolean[]visited=newboolean[n];
privateint[][]a=newint[n][n];
privateStringresult="";
privateTreeSetset=newTreeSet();
publicstaticvoidmain(String[]args){
newTestQuestion().start();
}
privatevoidstart(){
//Initialthemapa[][]
for(inti=0;i