ring.indexOf("4")!=2){
System.out.println(string);
}
}
}
privatevoiddepthFirstSearch(intstartIndex){
visited[startIndex]=true;
result=result+b[startIndex];
if(result.length()==n){
//Filttheduplicatevalue.
set.add(result);
}
for(intj=0;j
if(a[startIndex][j]==1&;&;visited[j]==false){
depthFirstSearch(j);
}else{
continue;
}
}
//restoretheresultvalueandvisitedvalueafterlistinganode.
result=result.substring(0,result.length()-1);
visited[startIndex]=false;
}
}
3,5不能相连:实际要求这个连通图的结点3,5之间不能连通,可在构造图结构时就满足改条件,然后再遍历图。
代码中请注意这几行:
//3and5cannotbetheneighbor.
a[3][5]=0;
a[5][3]=0;
只要这样定义图,根本不用在代码中写IFELSE语句。
实际上基于图的算法好处在于,只要你能定义好满足题目要求的图结构,遍历的结果就是你要的结果,不用任何对遍历结果做任何处理。包括本题中的:4不能在第三位置,3,5不能相连,唯一
性要求,其实都可以在体现在构造的图形结构里,然后直接遍历图取得自己要的结果。而不用再次处理结果集。
只是说这里实际上对其它要求要体现在图结构里有困难(理论上是可以的),但起码3,5不能相接是很好构造的,就是上面的代码段来解释的。
关于图形数据结构建议先看看数据结构的书,主要是将如何利用二维数组描述图结构,再看看图的深度遍历实现原理。最后再应用到这个问题上来,自然就不难明白了。
补充:由于时间的关系,上面给的代码没有多做考虑。
其实有两方面可以优化一下:
1。Validate可以学习Struts,利用抽象Validate集去掉If/Else语句。在此不多说。
2。在同层递增前增加“重复预测“减少不必要的重复排序,提高效率。
改进代码如下,其中“//********”处为修改地方
classtest
{
//当前固定部分
privateStringCurFixPart;
privateStringPreGenNum;
publicstaticvoidmain(String[]args)
{
testt=newtest();
t.GenControll("1111111111");
}
//调整字符串s位置pos字符到最前
privateStringshift(Strings,intpos)
{
StringnewStr;
if(s.length()>pos+1)
newStr=s.substring(pos,pos+1)
+s.substring(0,pos)
+s.substring(pos+1);
else
newStr=s.substring(pos)
+s.substring(0,pos);
returnnewStr;
}
protectedintValidate(StringnewNum)
{