一行代码解决了三个常考算法题，面试官懵了

深碍√TFBOYSˉ_ 2022-10-05 15:43 129阅读 0赞

大家耐心看完，以后遇到相关问题，就可以装个逼了，另外，帅地也正在整理一些面试相关的资料，文末把最近整理的长达 20 万字的《Java面试必知必会》送给大家。

### 1、n 的阶乘 ###

> 问题描述：给定一个整数 N，那么 N 的阶乘 N! 末尾有多少个 0？例如： N = 10，则 N！= 3628800，那么 N! 的末尾有两个0。

我先给出个代码让大家品尝一下，在细细讲解

int f(n){
        
    	return n == 0 ? 0 : n / 5 + f(n / 5);
    }

对于这道题，常规操作是直接算 N！的值再来除以 10 判断多少个 0 ，然而这样肯定会出现溢出问题，并且时间复杂度还大，我们不妨从另一个思路下手：一个数乘以 10 就一定会在末尾产生一个零，那么，我们是否可以从**哪些数相乘能够得到 10** 入手呢？

答是可以的，并且只有 2 \* 5 才会产生 10。

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

于是，问题转化为 N! 种能够分解成多少对 2\*5，再一步分析会发现，在 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(n){
        
    	return n == 0 ? 0 : n / 5 + f(n / 5);
    }

别问，问就是一行代码的事。

### 2、2 的幂次方 ###

> 问题描述：判断一个整数 n 是否为 2 的幂次方

对于这道题，常规操作是不断这把这个数除以 2，然后判断是否有余数，直到 n 被整除成 1 。

我们可以把 n 拆成二进制看待处理的，如果 n 是 2 的幂次方的话，那么 n 的二进制数的最高位是 1，后面的都是 0，例如对于 16 这个数，它的二进制表示为 10000。

如果我们把它减 1，则会导致最高位变成 0，其余全部变成 1，例如 10000 - 1 = 01111。

然后我们把 n 和 （n - 1）进行**与**操作，结果就会是 0，例如(假设 n 是 16)

n & (n-1) = 10000 & （10000 - 1) = 10000 & 01111 = 0

也就是说，n 如果是 2 的幂次方，则 n & (n-1) 的结果是 0，否则就不是，所以代码如下

int isPow(n){
        
    	return (n & (n - 1)) == 0;
    }

一行代码搞定，在装逼的路上越走越远

## 3、找出一个没有重复的数 ##

> 给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。

然而我想告诉你的是，采用位运算来做，绝对高逼格！

我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：

由于异或支持交换律和结合律，所以:

123451234 = （11)(22)(33)(44)5= 00005 = 5。

也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下

int find(int[] arr){
        
        int tmp = arr[0];
        for(int i = 1;i < arr.length; i++){
        
            tmp = tmp ^ arr[i];
        }
        return tmp;
    }

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼，就问这波操作稳不稳？

> 这里说明一下，这个方式适合一个数出现了奇数次，其他数都出现了偶数次

不行，我还要继续装！

？一行代码解决方案如下：

// 例如使用这个函数的时候，我们最开始传给 i 的值是 1，传给 result 的是 arr[0]
    //例如 find(arr, 1, arr[0])
    int find(int[] arr,int i, int result){
        
    	return arr.length <= i ? result : find(arr, i + 1, result ^ arr[i]);
    }

实不相瞒，这道题用了一行代码之后，更加复杂 + 难懂了，，，，，，不好意思，我错了，不该把简单的问题搞复杂了再扔给面试题的。

另外，校招就要来了，帅地为大家整理了一份面试题，这份面试题，算是 Java 一整套技术栈都写了，包括 Java 基础，虚拟机，消息队列，框架等等。

当然，还有通用基础知识，例如计算机网络，操作系统，Mysql，Redis 也都整理了，给大家看一下目录。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTA3Nzk3_size_16_color_FFFFFF_t_70][]  
一方面也是方便自己以后跳槽的时候复习，相信这份面试题一定在面试和复习的过程中助大家一臂之力，送给大家，在帅地的公众号「**帅地玩编程**」后台回复「**Java面试题**」就可以获取到了。

有时候经常收到读者提问，例如

Java 应该要学习到哪个程度啊？

数据结构与算法要学习到哪个程度啊？

计算机基础要学习到哪个程度啊？

这其实很难衡量，我一般给的建议就是，把一本书 80% 的知识点啃完，我觉得就差不多了。

例如你说 mysql 要学到哪个程度，那么你只需把《mysql必知必会》和《MySQL技术内幕》看完，那么就差不多了，剩下的，以后遇到不懂的再去看文章即可。

不过呢，验证自己学的如何，还有另外一种可行方式，**就是看看市面上的面试题，你掌握了多少？**，帅地整理的这份 PDF，应该就适合你了，只求来个赞，嘻嘻。

### 作者简洁 ###

> 作者：大家好，我是帅地，从大学、自学一路走来，深知**算法**，**计算机基础知识**的重要性，公众号「**帅地玩编程**」10万粉丝作者，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我一起学习，点击[了解我四年大学学 习之路][Link 1] **转载说明**：未获得授权，禁止转载

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTA3Nzk3_size_16_color_FFFFFF_t_70]: /images/20221005/0ac113f3e2f643e09c7250077c8bf28b.png
[Link 1]: https://www.iamshuaidi.com/344.html