开发者社区> 天降风云> 正文

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

简介: 前言 前几天看到了一道简单的面试题,从5个数字中找出所有每位数字都不同的三位数的数量并且一一输出。
+关注继续查看

前言

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
面试题:从1, 2, 3, 4, 5五个数字中能找出多少个每位数字都不同的三位数?
前言 前几天看到了一道简单的面试题,从5个数字中找出所有每位数字都不同的三位数的数量并且一一输出。
1407 0
Bug现形记(一):一个多重继承程序的查错
  【课程支撑】我的 C++程序设计课程教学材料   要完成的任务详见第12周-任务2-双肩挑干部。题目要求   分别定义Teacher(教师)类和Cadre(干部)类,采用多重继承方式由这两个类派生出新类Teacher_Cadre(教师兼干部)。要求:  (1)在两个基类中都包含姓名、年龄、性别、地址、电话等数据成员。  (2)在Teacher类中还包含数据成员title(职称),在Cadr
1355 0
《VMware Virtual SAN权威指南》一3.10.2 为什么要在VSAN中配置多个磁盘组
本节书摘来华章计算机《VMware Virtual SAN权威指南》一书中的第3章 ,第3.10.2节, [美] 科马克·霍根(Cormac Hogan)邓肯·埃平(Duncan Epping)  著 徐 炯 译译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1284 0
.NET Core和.NET Standard有什么不同
原文:.NET Core和.NET Standard有什么不同         近日,微软发布了.NET Core 2.0,但是开发人员中间仍然存在一些疑惑,就是.NET Core、.NET Standard、Xamarin和.NET Framework有什么不同。
1456 0
ELK收集多个docker容器日志(十二)
filebeat收集容器日志 现在很多公司都是用docker容器来运行服务,一台机器上会有很多个docker,docker容器里面的日志也需要收集分析,filebeat也有docker容器的日志收集方案 官方配置地址https://www.elastic.co/guide/en/beats/filebeat/6.6/filebeat-input-docker.html
31 0
+关注
天降风云
java,前端,算法相关技术专家
16
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载