今天看到某公司（中兴）一道面试编程题，题目如下：
用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：”4″不能在第三位，”3″与”5″不能相连，并用1、2、2、3、4、5这六个数字排列“递增”序列！
这道题咋一看很简单啊，可是如果你要是仔细看一下就发现，其实不那么好做，我的想法是：
这道题显然应该是递归，比如初始序列122345，先从末两位(45)变化(45,54),然后末三位(345) … 直到最后六位.
可是怎样解决重复问题呢？这个我想了好久，有一种简单的想法，由于是递增序列，每生成新序列可与前一生成序列比较，如<放弃当前序列。
由于本人很想以后去中兴，所以很重视这道题，我试着编写出一个。基本上能运行出来，只是在跳出循环的时候感觉不太理想，一下是我的程序，我只是一个小菜鸟，忘高手给出简单的方法，多谢！
class test
{
// 当前固定部分
private String CurFixPart;
private String PreGenNum;
public static void main(String[] args)
{
test t=new test();
t.GenControll(“122345″);
}
// 调整字符串s位置pos字符到最前
private String shift(String s, int pos)
{
String newStr;
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);
return newStr;
}
protected int Validate(String newNum)
{
String newGenNum=CurFixPart+newNum;
if (Integer.valueOf(newGenNum)<=Integer.valueOf(PreGenNum))
return 0;
if (newGenNum.substring(2,3).equals(“4″) ||
(newGenNum.indexOf(“35″)!=-1) || (newGenNum.indexOf(“53″)!=-1))
return 0;
PreGenNum=newGenNum;
System.out.println(newGenNum);
return 0;
}
public void GenControll(String Base)
{
PreGenNum=”0″;
CurFixPart=”";
GenNext(Base, 0);
}
void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
|
收藏
淘帖
踩
