前言
前几天看到了一道简单的面试题，从5个数字中找出所有每位数字都不同的三位数的数量并且一一输出。从数学上来讲，算出数量比较简单，只是一个排列的计算。比如这道题的计算方法就是P(5,3) = 60。输出的过程也比较简单，这里提出两种方法：
正文
方法一：
一种通俗易懂的方法。用三个for循环，第一个for循环遍历所有的数字，第二个循环遍历除了第一个数字之外的所有数字，第三个循环遍历除了前两个数字之外的所有数字。然后输出就可以了。具体实现代码如下：
public class Number {
public static final int []num = {1, 2, 3, 4, 5};
public static int count = 0;
public static void main(String[] args) {
calculate(num);
System.out.println("总数为" + count);
}
public static void calculate(int []arr){
for(int i=0; i<arr.length; i++)
{
for(int j=0; j<arr.length; j++)
{
if(j!=i)
{
for(int k=0; k<arr.length; k++)
{
if(k!=i && k!=j){
count++;
System.out.println("第" + count + "个数为: " + arr[i] + "" + arr[j] + "" + arr[k]);
}
}
}
}
}
}
}下面是程序的输出
第1个数为: 123
第2个数为: 124
第3个数为: 125
第4个数为: 132
第5个数为: 134
第6个数为: 135
第7个数为: 142
第8个数为: 143
第9个数为: 145
第10个数为: 152
第11个数为: 153
第12个数为: 154
第13个数为: 213
第14个数为: 214
第15个数为: 215
第16个数为: 231
第17个数为: 234
第18个数为: 235
第19个数为: 241
第20个数为: 243
第21个数为: 245
第22个数为: 251
第23个数为: 253
第24个数为: 254
第25个数为: 312
第26个数为: 314
第27个数为: 315
第28个数为: 321
第29个数为: 324
第30个数为: 325
第31个数为: 341
第32个数为: 342
第33个数为: 345
第34个数为: 351
第35个数为: 352
第36个数为: 354
第37个数为: 412
第38个数为: 413
第39个数为: 415
第40个数为: 421
第41个数为: 423
第42个数为: 425
第43个数为: 431
第44个数为: 432
第45个数为: 435
第46个数为: 451
第47个数为: 452
第48个数为: 453
第49个数为: 512
第50个数为: 513
第51个数为: 514
第52个数为: 521
第53个数为: 523
第54个数为: 524
第55个数为: 531
第56个数为: 532
第57个数为: 534
第58个数为: 541
第59个数为: 542
第60个数为: 543
总数为60这种方式使用了三个for循环，并不是太好。因为假如题目的条件变为从10个不同的数字中找出不同的5位数，那么就需要写五个for循环。要找出的数字位数越多，就需要写越多的循环。总之，这不是一个一般性的解法，对于不同的题目条件，要写出不同的循环数量，不具有统一性。如果从遍历数的角度来看，这是一种“深度优先搜索”策略。
方法二
从题目的条件看，这是一个很典型的遍历树的问题。我们也可以使用“广度优先搜索”算法来解决这道题。下面是代码：
import java.util.Stack;
public class Num {
public static final Stack<String> stack = new Stack<String>();
public static final int goalDigits = 3;
public static final int []num = {1, 2, 3, 4, 5};
public static int totalNum = 0;
public static void main(String[] args) {
for(int i : num){
numS(i);
}
System.out.println("总数为" + totalNum);
}
public static void numS(int i){
stack.push(i + "");
while(!stack.isEmpty()){
String iString = stack.pop();
if(isGoal(iString)){
totalNum++;
System.out.println("第" + totalNum + "个数字为: " + Integer.parseInt(iString));
continue;
}
for(int j : num){
if(!iString.contains(j + ""))
stack.push(iString + j + "");
}
}
}
public static boolean isGoal(String s){
return s.length() == goalDigits;
}
}这里用到了一个数据结构，栈（stack）。基本的算法就是，对于数组中的每个元素，都把它当做一个树的根节点（即push，入栈操作），接着把这个子节点pop出来，然后对于数组中的所有其他元素，都当做这个根节点的子节点（push操作）。这时栈内的元素都是两位数。然后再依次把这些节点pop出来，再寻找数组中不与这个两位数相同的所有元素，再继续入栈，以此类推。这样，当栈内所有元素都被pop出来，即栈为空的时候，就是这棵树被遍历完成的时候。我们可以看到，树的数量就是元素的数量。有5个元素，就要遍历5棵树。遍历的时候，如果正好pop出了一个三位数（就是我们的目标之一），我们就可以跳出当前循环。
以下是程序的输出：
第1个数字为: 154
第2个数字为: 153
第3个数字为: 152
第4个数字为: 145
第5个数字为: 143
第6个数字为: 142
第7个数字为: 135
第8个数字为: 134
第9个数字为: 132
第10个数字为: 125
第11个数字为: 124
第12个数字为: 123
第13个数字为: 254
第14个数字为: 253
第15个数字为: 251
第16个数字为: 245
第17个数字为: 243
第18个数字为: 241
第19个数字为: 235
第20个数字为: 234
第21个数字为: 231
第22个数字为: 215
第23个数字为: 214
第24个数字为: 213
第25个数字为: 354
第26个数字为: 352
第27个数字为: 351
第28个数字为: 345
第29个数字为: 342
第30个数字为: 341
第31个数字为: 325
第32个数字为: 324
第33个数字为: 321
第34个数字为: 315
第35个数字为: 314
第36个数字为: 312
第37个数字为: 453
第38个数字为: 452
第39个数字为: 451
第40个数字为: 435
第41个数字为: 432
第42个数字为: 431
第43个数字为: 425
第44个数字为: 423
第45个数字为: 421
第46个数字为: 415
第47个数字为: 413
第48个数字为: 412
第49个数字为: 543
第50个数字为: 542
第51个数字为: 541
第52个数字为: 534
第53个数字为: 532
第54个数字为: 531
第55个数字为: 524
第56个数字为: 523
第57个数字为: 521
第58个数字为: 514
第59个数字为: 513
第60个数字为: 512
总数为60对于不同的题目条件，我们只要修改goalDigits这个变量就可以了。
当然，深度优先搜索的策略也可以用stack的数据结构实现，实现方式和广度优先搜索差异不大，只是遍历树的方式由横向改为纵向。
