原题如下:用1、2、2、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
解题思路:
很明显,这是一个递归算法。我们可以排列将这6个数按从小到大的顺序排一下,如果是1,2,3,4,5,6,那么会有1*2*3*4*5*6=6!=720个递增的数。但如果是1,2,2,3,4,5,那么在这720个数中一定会有相同的数对出现(由于在这6个数中只有两个数两同,也就是说,如果有重复的数,那么一定是一对数,如122345会出现两次)。
排列的基本规则是分步进行。也就是说,要排列上面6个数,首先应该选择第一个数,这第一个数可以选择这6个数中的任意一个,如选择1.第二步是选择第二个数,这第二个数不能再选择已经选过的数,如1.因此,它只能从后面5个数中选择。如选择2。以此类推。
我们也可以在程序中模拟这一过程。源程序如下:
public class test1 {
private int[] numbers = new int[] { 1, 2, 3, 3, 4, 5 };
public int n;
private String lastResult = "";
private boolean validate(String s) {
if (s.compareTo(lastResult) <= 0)
return false;
if (s.charAt(2) == '4')
return false;
if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)
return false;
return true;
}
public void list(String index, String result) {
for (int i = 0; i < numbers.length; i++) {
if (index.indexOf(i + 48) < 0) {
String s = result + String.valueOf(numbers[i]);
if (s.length() == numbers.length) {
if (validate(s)) {
System.out.println(s);
lastResult = s;
n++;
}
break;
}
list(index + String.valueOf(i), s);
}
}
}
public static void main(String[] args) {
test1 t = new test1();
t.list("", "");
System.out.println("总数:" + t.n);
}
}
其中list函数是这个算法的核心函数。index参数表示已经选择过的数,用numbers数组的索引表示。如index="012",表示numbers的前三个数已经被选择,也表示应该选择第四个数了,而这第四个数应该从后三个数中选择。result参数表示临时的数字组合(这个数字组合最多是5个数字,因为,如果到了6个数字,就表示已经有一个结果产生了)。在默认情况下index和result的值都是""。
在validate中使用了 if (s.compareTo(lastResult) <= 0)进行判断,由于按这种方法进行排列,如果这6个数是递增给出的,那么排列的结果一定是递增的,但上述的6个数其中第2和第3个位置上都是2,因此,如果出现了上一个结果不小于当前结果的情况,一定是有重复了,因此,要将这部分数过滤出去。
使用1, 2, 2, 3, 4, 5的测试结果
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
132245
132254
132425
132452
132524
132542
142325
... ...
... ...
542313
542331
543123
543132
543213
543231
543312
543321
总数:118
使用1, 3, 3, 3, 4, 5的测试结果
133345
313345
315433
331345
331543
333145
333154
333415
333451
343315
345133
433315
451333
513334
513343
513433
541333
543133
543313
543331
总数:20
分享到:
相关推荐
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题
不骗人,整理的一套试卷的全部题目~2017年哒
该资源为2019年雷达算法工程师笔试题,包含单选,多选,判断和问答题。推荐需要应聘雷达算法岗的同学可以下载。
各大软件公司面试--算法笔试题各大软件公司面试--算法笔试题
软件开发中常用算法笔试题 1、将一个字符串逆序 2、将一个链表逆序 。。。。
大疆求职算法笔试题 大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题
华为OD、大厂笔试算法题; 一共87题,每一题附答案(java语言),笔试时频繁出现的原题,想进大厂的小伙伴,欢迎下载; eg: 1、5键键盘的输出 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键...
数据结构算法笔试题汇总.docx
数据结构与算法笔试题考点分析.doc
兔子繁殖 半段质数 水仙花数 最大公约数 最小公倍数 数字排序等经典的编程问题
根据网上的资源整理的一些算法笔试题及其入门,涵盖多种语言实现的版本,仅适合新手入门,不太适合算法老司机。
阿里巴巴最新算法工程师笔试题.pdf
算法笔试题:(Python实现)—— 算法面试题汇总算法笔试题:(Python实现)—— 算法面试题汇总开始之前Python实现只出现一次的数字多数元素搜索二维矩阵 II合并两个有序数组鸡蛋掉落字符串Python实现验证回文串...
数据结构和算法笔试题数据结构和算法笔试题数据结构和算法笔试题
互联网常见算法笔试题分类总结,欢迎下载,全是干货。
c数据结构算法面试笔试题_数据结构与算法笔试题.docxc数据结构算法面试笔试题_数据结构与算法笔试题.docx
c++数据结构算法面试笔试题-数据结构与算法笔试题.pdfc++数据结构算法面试笔试题-数据结构与算法笔试题.pdf
算法笔试题 有答案 笔试题 有答案 有答案
2014年大华笔试题目,和以往2012、2013笔试题目出入很大,备考利器啊!