著名软件公司的java笔试算法题!(含参考答案)

 

原题如下:用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);

}

}

序列122345测试通过。

有什么意见请大家多多提点。

 

我来提个思路。

 

1. 先对1,2,2,3,4,5 全排序。 把结果存到一个数组里面去。

数组的元素是一个string. 比如 122345, 522413 等等

2. 历遍整个数组用正规表达式去判断这个元素是不是符合规格

比如 122435

规则1 。 match=[//d][//d][//d][4]

规则2。 match=[35]|[53]

如果正规表达式匹配的结果数大于0,说明这个元素不是我们要得

当匹配的结果等于0,则把这个元素加入一个新的集合中去

3. 新的集合就是我们要得结果集

 

好处: 1不要动脑子想,思路清楚。 2对于数字,字符,都适合。 3。规则的修改快速,比如要求改为第4位不能为1, 2和3不能相邻等, 只学要改规则就可以了。



本文转自左正博客园博客,原文链接:http://www.cnblogs.com/soundcode/archive/2010/12/19/1910307.html,如需转载请自行联系原作者

上一篇:淮南发力“大数据”激活新动能


下一篇:Interview:算法岗位面试—10.17早上—上海某科技公司算法岗位(偏算法,独角兽)非技术面试之比赛项目讲解和项目意义的探讨