一著名
软件公司的java笔试算法题!2009-06-0511:01原题如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连.
我看了回贴都没有很好解决,主要是没有排除重复。
解决思路:强化题目,用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路:显然是递归,初始序列122345,先从末两位(45)变化(45,54),然后末三位(345)...直到最后六位.怎样解决重复
问题?很简单,由于是递增序列,每生成新序列可与前一生成序列比较,如<放弃当前序列。当然有更好效率,如预先预测。代码如下:
classtest
{
//当前固定部分
privateStringCurFixPart;
privateStringPreGenNum;
publicstaticvoidmain(String[]args)
{
testt=newtest();
t.GenControll("122345");
}
//调整字符串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)
{
StringnewGenNum=CurFixPart+newNum;
if(Integer.valueOf(newGenNum)<=Integer.valueOf(PreGenNum))
return0;
if(newGenNum.substring(2,3).equals("4")||
(newGenNum.indexOf("35")!=-1)||(newGenNum.indexOf("53")!=-1))
return0;
PreGenNum=newGenNum;
System.out.println(newGenNum);
return0;
}
publicvoidGenControll(StringBase)
{
PreGenNum="0";
CurFixPart="";
GenNext(Base,0);
}
voidGenNext(StringvarPart,intcurPos)
{
if(varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart,1));
return;
}
//NextLayer
StringnewGen=shift(varPart,curPos);