黑马程序员技术交流社区
标题:
一道Java编程面试题,求高手解决!
[打印本页]
作者:
王小丑
时间:
2013-2-8 22:51
标题:
一道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);
}
}
作者:
王小丑
时间:
2013-2-8 22:54
补充一下:对于递归我感觉当然有更好效率,如预先预测法,但是还是那个比较辣手问题即怎样解决重复问题,我感觉这个问题很关键,希望高手给出程序,我几天后会做一个总结,谢谢大家支持!
作者:
张晋瑜
时间:
2013-2-8 23:51
顶起,期待解法
作者:
许晓华
时间:
2013-2-9 11:49
本帖最后由 许晓华 于 2013-2-12 15:42 编辑
一共有198种满足要求的排列,结果如下:(代码见下一楼)
1 2 2 3 4 5
1 2 2 5 4 3
1 2 3 2 4 5
1 2 3 2 5 4
1 2 3 4 2 5
1 2 3 4 5 2
1 2 5 2 3 4
1 2 5 2 4 3
1 2 5 4 2 3
1 2 5 4 3 2
1 3 2 2 4 5
1 3 2 2 5 4
1 3 2 4 2 5
1 3 2 4 5 2
1 3 2 5 2 4
1 3 2 5 4 2
1 4 2 3 2 5
1 4 2 5 2 3
1 4 3 2 2 5
1 4 3 2 5 2
1 4 5 2 2 3
1 4 5 2 3 2
1 5 2 2 3 4
1 5 2 2 4 3
1 5 2 3 2 4
1 5 2 3 4 2
1 5 2 4 2 3
1 5 2 4 3 2
2 1 2 3 4 5
2 1 2 5 4 3
2 1 3 2 4 5
2 1 3 2 5 4
2 1 3 4 2 5
2 1 3 4 5 2
2 1 5 2 3 4
2 1 5 2 4 3
2 1 5 4 2 3
2 1 5 4 3 2
2 2 1 3 4 5
2 2 1 5 4 3
2 2 3 1 4 5
2 2 3 1 5 4
2 2 3 4 1 5
2 2 3 4 5 1
2 2 5 1 3 4
2 2 5 1 4 3
2 2 5 4 1 3
2 2 5 4 3 1
2 3 1 2 4 5
2 3 1 2 5 4
2 3 1 4 2 5
2 3 1 4 5 2
2 3 1 5 2 4
2 3 1 5 4 2
2 3 2 1 4 5
2 3 2 1 5 4
2 3 2 4 1 5
2 3 2 4 5 1
2 3 2 5 1 4
2 3 2 5 4 1
2 4 1 3 2 5
2 4 1 5 2 3
2 4 2 3 1 5
2 4 2 5 1 3
2 4 3 1 2 5
2 4 3 1 5 2
2 4 3 2 1 5
2 4 3 2 5 1
2 4 5 1 2 3
2 4 5 1 3 2
2 4 5 2 1 3
2 4 5 2 3 1
2 5 1 2 3 4
2 5 1 2 4 3
2 5 1 3 2 4
2 5 1 3 4 2
2 5 1 4 2 3
2 5 1 4 3 2
2 5 2 1 3 4
2 5 2 1 4 3
2 5 2 3 1 4
2 5 2 3 4 1
2 5 2 4 1 3
2 5 2 4 3 1
3 1 2 2 4 5
3 1 2 2 5 4
3 1 2 4 2 5
3 1 2 4 5 2
3 1 2 5 2 4
3 1 2 5 4 2
3 1 5 2 2 4
3 1 5 2 4 2
3 1 5 4 2 2
3 2 1 2 4 5
3 2 1 2 5 4
3 2 1 4 2 5
3 2 1 4 5 2
3 2 1 5 2 4
3 2 1 5 4 2
3 2 2 1 4 5
3 2 2 1 5 4
3 2 2 4 1 5
3 2 2 4 5 1
3 2 2 5 1 4
3 2 2 5 4 1
3 2 5 1 2 4
3 2 5 1 4 2
3 2 5 2 1 4
3 2 5 2 4 1
3 2 5 4 1 2
3 2 5 4 2 1
3 4 1 2 2 5
3 4 1 2 5 2
3 4 1 5 2 2
3 4 2 1 2 5
3 4 2 1 5 2
3 4 2 2 1 5
3 4 2 2 5 1
3 4 2 5 1 2
3 4 2 5 2 1
3 4 5 1 2 2
3 4 5 2 1 2
3 4 5 2 2 1
4 1 2 3 2 5
4 1 2 5 2 3
4 1 3 2 2 5
4 1 3 2 5 2
4 1 5 2 2 3
4 1 5 2 3 2
4 2 1 3 2 5
4 2 1 5 2 3
4 2 2 3 1 5
4 2 2 5 1 3
4 2 3 1 2 5
4 2 3 1 5 2
4 2 3 2 1 5
4 2 3 2 5 1
4 2 5 1 2 3
4 2 5 1 3 2
4 2 5 2 1 3
4 2 5 2 3 1
4 3 1 2 2 5
4 3 1 2 5 2
4 3 1 5 2 2
4 3 2 1 2 5
4 3 2 1 5 2
4 3 2 2 1 5
4 3 2 2 5 1
4 3 2 5 1 2
4 3 2 5 2 1
4 5 1 2 2 3
4 5 1 2 3 2
4 5 1 3 2 2
4 5 2 1 2 3
4 5 2 1 3 2
4 5 2 2 1 3
4 5 2 2 3 1
4 5 2 3 1 2
4 5 2 3 2 1
5 1 2 2 3 4
5 1 2 2 4 3
5 1 2 3 2 4
5 1 2 3 4 2
5 1 2 4 2 3
5 1 2 4 3 2
5 1 3 2 2 4
5 1 3 2 4 2
5 1 3 4 2 2
5 2 1 2 3 4
5 2 1 2 4 3
5 2 1 3 2 4
5 2 1 3 4 2
5 2 1 4 2 3
5 2 1 4 3 2
5 2 2 1 3 4
5 2 2 1 4 3
5 2 2 3 1 4
5 2 2 3 4 1
5 2 2 4 1 3
5 2 2 4 3 1
5 2 3 1 2 4
5 2 3 1 4 2
5 2 3 2 1 4
5 2 3 2 4 1
5 2 3 4 1 2
5 2 3 4 2 1
5 4 1 2 2 3
5 4 1 2 3 2
5 4 1 3 2 2
5 4 2 1 2 3
5 4 2 1 3 2
5 4 2 2 1 3
5 4 2 2 3 1
5 4 2 3 1 2
5 4 2 3 2 1
5 4 3 1 2 2
5 4 3 2 1 2
5 4 3 2 2 1
一共有198种满足要求的排列
作者:
许晓华
时间:
2013-2-9 15:15
本帖最后由 许晓华 于 2013-2-12 15:41 编辑
public class c
{
static int MAX=6;
static int []rcd=new int[MAX];
static int []used=new int[MAX];
static int []num=new int[MAX];; //存放互不相同的m个数
static int n=MAX,m=0; //n个数,互不相同有m个
static int count=0;//记数器
static void unrepeat_full_permutation(int l)
{
int i;
if(l == n)
{
if(rcd[2]==4) return;//4不能在第3位
for(i=0;i<n-1;i++)//3与5不能相连
if(rcd[i]==3&&rcd[i+1]==5||rcd[i]==5&&rcd[i+1]==3) return;
count++;//记数器自增
for(i=0; i<n; i++)
{
System.out.print(rcd[i]);
if(i < n-1) System.out.print(" ");
}
System.out.println();
return ;
}
for(i=0; i<n; i++)
{
if(used[i] > 0)
{
used[i]--;
rcd[l] = num[i];
unrepeat_full_permutation(l+1);
used[i]++;
}
}
}
public static void main(String[] args)
{
int i, j;
int ori[]={1,2,2,3,4,5};
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(num[j] == ori[i])
{
used[j]++;
break;
}
}
if(j == m)
{
num[m] = ori[i];
used[m++] = 1;
}
}
unrepeat_full_permutation(0);
System.out.printf(" 一共有%d种满足要求的排列\n",count);
}
}
复制代码
作者:
姚永生
时间:
2013-2-9 15:53
递归这个鬼东西,我怎么越学越糊涂?杯具!!
作者:
王小丑
时间:
2013-2-12 12:58
许晓华 发表于 2013-2-9 15:15
很给力 支持
作者:
王小丑
时间:
2013-2-12 15:54
谢谢前辈 我会努力的!
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2