阶乘很简单?说实话,这几道阶乘相关面试题你还真不一定懂!

对于如何算 n 的阶乘,只要你知道阶乘的定义,我想你都知道怎么算,但如果在面试中,面试官抛给你一道与阶乘相关,看似简单的算法题,你还真不一定能够给出优雅的答案!本文将分享几道与阶乘相关的案例,且难度递增。

案例一

给定一个整数 N,那么 N 的阶乘 N! 末尾有多少个 0?例如: N = 10,则 N!= 3628800,那么 N! 的末尾有两个0。

有些人心想,这还不简单,直接算出 N!的值,然后用除以 10 来判断多少个 0 就可以了。

有些人则这样想,直接算 N!的值再来除以 10 判断多少个 0 的话肯定会出现溢出问题,于是开始思索:一个数乘以 10 就一定会在末尾产生一个零,于是,我们可以从“哪些数相乘能够得到 10 ”入手。

没错,只有 2 * 5 才会产生 10。

注意,4 * 5 = 20 也能产生 0 啊,不过我们也可以把 20 进行分解啊,20 = 10 * 2。

于是,问题转化为 N! 种能够分解成多少对 25,再一步分析会发现,在 N!中能够被 2 整除的数一定比能够被 5 整除的数多,于是问题就转化为求 1...n 这 n 个数中能够被 5 整除的数有多少个,注意,像 25 能够被 5整除两次,所以25是能够产生 2 对 2 5滴。有了这个思路,代码如下:

int f(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 5 == 0){
            sum++;
            j = j / 5;
        }
    }
    return sum;
}

有些人想出了这个规律,很是得意,然而,这还不是面试官要的答案,大家想一个问题,

当 N = 20 时,1~20 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

当 N = 24 时,1~24 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

当 N = 25 时,1~25 可以产生几个 5?答是 6 个,主要是因为 25 贡献了两个 5,此时有 N / 5 + N / 5^2 = 6。

...

可以发现 产生 5 的个数为 sum = N/5 + N/5^2 + N/5^3+....

于是,最优雅的写法应该是这样:

int f(int n){
    int sum = 0;
    while(n! = 0){
        sum += n / 5;
        n = n / 5;
    }
}

这时,你就可以自信这把代码扔给面试官了。

案例2

求 N! 的二进制表示中最低位 1 的位置。例如 3!=6,二进制为 1010,所以 最低位 1 的位置在第二位。

没有思路?请仔细想一下这道题与上道题的关系!

仔细想一下,这道题不也是求末尾有多少个 0 吗?你求出了末尾有多少个0自然知道 1 的位置(0的个数加1就是1的位置了),只不过,这道题是求二进制末尾有多少个 0。

由于是二进制,所以每次乘以 2 末尾就会产生一个 0 。

于是,模仿上面一道题,求 N!含有多少个 2 的个数。心想,幸好我做个类似了,于是一波操作猛如虎,一分钟就写出了代码:

int f(int n){
    int sum = 0;
    while(n! = 0){
        sum += n / 2;
        n = n / 2;
    }
}

面试官:还能在优化吗?

什么鬼?还要在优化?我都 O(logn) 时间复杂度了。

还记得我之前讲解了几道有关位运算的吗?这道题确实可以用位运算来优化,除以 n / 2 == n >> 1。不过位运算的速度快多了,于是,优化后的代码如下:

int f(int n){
    int sum = 0;
    while(n! = 0){
        n >>= 1;
        sum += n;
    }
}

还能在优化吗?

可以,不过我先不讲,因为我觉得,这已经够快了。后面讲其他题可能会把这道题再拿出来讲。

如果你能写出这样的代码,已经算很牛逼了。

案例三

给你一个数 N,输出 N! 的值。

没错,就是这么简单,直接让你求阶乘的值。

这个时候,你就要小心了,千万别一波操作

long long sum = 1;
for(int i = 1; i <= n; i++){
    sum *= i;
    
}

一个 for 循环,马上搞定。

因为你不知道 n 的范围,有可能你用 long long 也是会溢出的,所以这个时候应该要问一下面试官有没有限定 n 的范围。

面试官:没有限定!

这下好了,这道阶乘的题,难度顿时上升了,说实话,我敢保证大部分人还真没去实现过。所以,今天我就带大家来实现一下,以防以后真的被问到。结果最熟悉的题顿时不知道怎么下手好。

这个时候,我们就必须用字符串来存放所求的值的,在相乘的时候也是用字符串来相乘,说白了,就是要会求两个大整数相乘

下面我们先来实现一个求两个大整数相乘的函数。一种比较简单的方法就是,像我们小学那会一样,让个位数与另一个数的其他数相乘,然后让十位数与另一个的其他数相乘,最后在把他们进行相加。

实现代码如下:

    public static String mul(String s1, String s2) {
        // 先把字符串转化为 字符数组。
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int len = c1.length + c2.length;
        // 用来存放两个数的积,字符的初始值为 \'\\u0000\',也就是 0
        char[] c = new char[len];
        // 由于大整数的低位是在字符串的末尾,所以我们从末尾遍历来计算
        for (int i = c1.length - 1; i >= 0; i--) {
            int index = len - 1;
            int res = 0;//用来存放进位
            for (int j = c2.length - 1; j >= 0; j--) {
                int temp = (c1[i]-\'0\') * (c2[j]-\'0\') + c[index] + res;
                res = temp / 10;
                c[index--] = (char)(temp % 10);
            }
            // 每趟乘下来的进位要进行保存。
            c[index] = (char)res;
            len--;
        }
        // 最后把c中的字符加上 \'0\'
        for (int i = 0; i < c.length; i++) {
            c[i] += \'0\';
        }
        String s = new String(c);
        // n位数乘以m位数得到积位 (m+n)位数或者(n+m-1)位数
        // 我们只需要判断c[0]是否为0,为0则把它舍弃。
        if(c[0] == \'0\')
            return s.substring(1);
        else
        return s;
    }

注意,一定要自己实现一遍,一定要自己实现一遍,因为原理简单,但手动实现就不一定那么简单了,容易出现bug。

采用这种方法的话,两个大整数相乘的时间复杂度为 O(n),其实还有更快的方法,大概时间复杂度是 O(n^1.6),不过代码有点小复杂,感兴趣的可以阅读这篇文章:漫画:如何实现大整数相乘?,我这里就不展开说了,不然单独这个就可以另起一篇很长的文章了。

知道了两个大整数相乘之后,我们再来算我们的阶乘,就好做了,我们每次相乘的时候,只需要把它当作两个大整数重复乘就可以了。代码如下:

    // N 的阶乘
    public static String f(int n) {
        String s = \"1\";
        Integer t = null;
        for (int i = 2; i <= n; i++) {
            t = i;
            s = 大整数相乘.mul(s,t.toString());
        }
        return s;
    }
    
    // 大整数相乘
    public static String mul(String s1, String s2) {
        // 先把字符串转化为 字符数组。
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int len = c1.length + c2.length;
        // 用来存放两个数的积,字符的初始值为 \'\\u0000\',也就是 0
        char[] c = new char[len];
        // 由于大整数的低位是在字符串的末尾,所以我们从末尾遍历来计算
        for (int i = c1.length - 1; i >= 0; i--) {
            int index = len - 1;
            int res = 0;//用来存放进位
            for (int j = c2.length - 1; j >= 0; j--) {
                int temp = (c1[i]-\'0\') * (c2[j]-\'0\') + c[index] + res;
                res = temp / 10;
                c[index--] = (char)(temp % 10);
            }
            // 每趟乘下来的进位要进行保存。
            c[index] = (char)res;
            len--;
        }
        // 最后把c中的字符加上 \'0\'
        for (int i = 0; i < c.length; i++) {
            c[i] += \'0\';
        }
        String s = new String(c);
        // n位数乘以m位数得到积位 (m+n)位数或者(n+m-1)位数
        // 我们只需要判断c[0]是否为0,为0则把它舍弃。
        if(c[0] == \'0\')
            return s.substring(1);
        else
        return s;
    }
    

时间复杂度是 O(n^3)。如果要优化的话,主要是在大整数相乘这里进行优化。

总结

是不是觉得,阶乘也没有那么简单了?这三道与阶乘相关的题,应该是比较常见的题吧,今天跟大家分享一波,希望大家有时间的话,自己也用代码实现一下,特别是算 N!。后面会继续跟大家分享一些我觉得不错的算法题,敬请关注。

最后推广下我的公众号:苦逼的码农戳我即可关注,文章都会首发于我的公众号,期待各路英雄的关注交流。

人已赞赏
随笔日记

程序员过关斩将--论商品促销代码的优雅性(一大波福利)

2020-11-9 3:52:09

随笔日记

JavaScript 为什么要有 Symbol 类型?

2020-11-9 3:52:11

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索