StringSavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1),0);
CurFixPart=SavedFixPart;
//同层递增
if(curPos==varPart.length()-1)
return;
GenNext(varPart,curPos+1);
}
}
序列122345测试通过。
有什么意见请大家多多提点。
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
for(intj=0;j if(i==j){
a[i][j]=0;
}else{
a[i][j]=1;
}
}
}
//3and5cannotbetheneighbor.
a[3][5]=0;
a[5][3]=0;
//Begintodepthsearch.
for(inti=0;i this.depthFirstSearch(i);
}
//Printresulttreeset.
Iteratorit=set.iterator();
while(it.hasNext()){
Stringstring=(String)it.next();
//"4"cannotbethethirdposition.
if(string.indexOf("4")!=2){
System.out.println(string);
}
}
}