一著名软件公司的java笔试算法题

 一著名软件公司的java笔试算法题！(2008-11-06 12:49:19)标签：java 面试题 it   分类：J2SE
原题如下：用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(newG