面试题:从1, 2, 3, 4, 5五个数字中能找出多少个每位数字都不同的三位数?

  1. 云栖社区>
  2. 博客>
  3. 正文

面试题:从1, 2, 3, 4, 5五个数字中能找出多少个每位数字都不同的三位数?

天降风云 2017-07-05 14:35:50 浏览1106
展开阅读全文

前言

前几天看到了一道简单的面试题,从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的数据结构实现,实现方式和广度优先搜索差异不大,只是遍历树的方式由横向改为纵向。

网友评论

登录后评论
0/500
评论
天降风云
+ 关注