• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

互联网 diligentman 4天前 9次浏览

大家耐心看完,以后遇到相关问题,就可以装个逼了,另外,帅地也正在整理一些面试相关的资料,文末把最近整理的长达 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 也都整理了,给大家看一下目录。
一行代码解决了三个常考算法题,面试官懵了
一方面也是方便自己以后跳槽的时候复习,相信这份面试题一定在面试和复习的过程中助大家一臂之力,送给大家,在帅地的公众号「帅地玩编程」后台回复「Java面试题」就可以获取到了。

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

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

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

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

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

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

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

作者简洁

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


程序员灯塔
转载请注明原文链接:一行代码解决了三个常考算法题,面试官懵了
喜欢 (0)