Re: 一著名软件公司的java笔试算法题!该如何解决
发布时间:2010-06-05 05:31:03 文章来源:www.iduyao.cn 采编人员:星星草
Re: 一著名软件公司的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 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点,把六个结点连接成无向连通图,对于每一个结点求这个图形的遍历路径,所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑:
1. 3,5不能相连:实际要求这个连通图的结点3,5之间不能连通, 可在构造图结构时就满足改条件,然后再遍历图。
2. 不能有重复: 考虑到有两个2,明显会存在重复结果,可以把结果集放在TreeSet中过滤重复结果
3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构,最后的代码是:
import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{ "1 ", "2 ", "2 ", "3 ", "4 ", "5 "};
private int n = b.length;
友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。
其他相似内容:
-
[技术讨论]谈谈Android开发中的Java。
谈谈Android开发中的Java。
谁说得好,谁分多。
------解决方案--------------------
钱多...
-
JMenuBar问题
JMenuBar只能放在frame最上面?不能放在当中?
------解决方案--------------------
可以你想怎么搞都可以的.
下...
-
要提取这串内容的连接怎么有问题?
<a href="http://www.92mp3.com/lrc/lrc.asp?ac=down&id=17656&gq=晴天" target=_blank>LRC歌词...
-
我吐 - 对提问者的不负责任,误导他人
http://topic.csdn.net/u/20110916/13/1cebe474-27b1-4c5e-ba6a-b35c06332802.html?seed=169...
-
怎么读秒?
就是设计一个线程,让他每秒读一边,怎么实现?这个for循环怎么写比较好?
------解决方案--------------------
1 可参考Quar...
-
关于Swing单选问题
为什么我用 swing的单选按钮的时候可以多选?
要怎么设置才不会多选
代码: int margin = 30;
for (int ...
-
关于线程的问题
java写的歌词显示,一个panel,画出歌词,run里有两个功能,一个是重画,让歌词动起来,一个是每秒获得一个歌词的句子让歌词...
-
这段代码有问题,谁能帮我看看?左边拉不过去!
import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.Dimensio...
-
这两个字符表示什么意思
public class Interest
{
public static void main(String args[])
{
double amount;
double pr...
-
一些问题!
一个是使用HttpCilent的时候什么时候用get方法,什么时候用post方法?
还有就是些文档的时候设计和实现两块怎么区分,感觉有...