内容简介:扔鸡蛋问题是一道非常经典的面试题,Google、百度、腾讯等大厂都使用过,此题有多个变体版本,扩展性很强,解决思路有多种,下面一起来探讨吧!举例:
概述
扔鸡蛋问题是一道非常经典的面试题,Google、百度、腾讯等大厂都使用过,此题有多个变体版本,扩展性很强,解决思路有多种,下面一起来探讨吧!
标准版面试题
题目描述
有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。 问:如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?
举例:
举个栗子,最笨的测试方法是什么样呢? 把其中一个鸡蛋从第1层开始往下扔。 如果在第1层没碎,换到第2层扔 如果在第2层没碎,换到第3层扔 ....... 如果第59层没碎,换到第60层扔 如果第60层碎了,说明不会摔碎的临界点是第59层 在最坏情况下,这个方法需要扔100次。
方法一:二分法
初看此题,部分同学可能会觉得,这不就相当于从1-100中,找到某个数么?采用二分法最快,下面我们推演一番
采用类似于二分查找的方法,把鸡蛋从一半楼层(50层)往下扔。
如果第一枚鸡蛋在50层碎了,第二枚鸡蛋就从第1层开始扔,一层一层增长,一直扔到第49层。
如果第一枚鸡蛋在50层没碎了,则继续使用二分法,在剩余楼层的一半(75层)往下扔......
这个方法在最坏情况下,需要尝试50次(100/2)。
方法二:平方根法
如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数尽可能均衡呢?
很简单,做一个平方根运算,100的平方根是10。
因此,我们尝试每10层扔一次,第一次从10层扔,第二次从20层扔,第三次从30层......一直扔到100层。
这样的最好情况是在第10层碎掉,尝试次数为 1 + 9 = 10次。
最坏的情况是在第100层碎掉,尝试次数为 10 + 9 = 19次。
这里有一个优化点,比如我们可以从15层开始扔,接下来25,35....一直到95层,最快情况下是第95层碎掉,尝试次数为 9+9 = 18次
方法三:解方程法
中学开始,同学们都学过方程,假设存在一个未知数X满足条件,根据已知条件列出一元n次方程,求解,下面我们根据题目描述,推出这个方程式
假设问题存在最优解(扔鸡蛋过程),这个解的最坏情况尝试次数是x次,那么,我们第一次扔鸡蛋该选择哪一层?
恰恰是从第x层开始扔,选择更高一层或是更低一层都不合适
为什么第一次扔就要选择第x层呢?
这里的解释也是通过假设法,然后演绎,有些烧脑,小伙伴们坚持住:
假设第一次扔在第x+1层(比x大):
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x层。
这样一来,我们总共尝试了x+1次,和假设尝试x次相悖。由此可见,第一次扔的楼层必须小于x+1层。
假设第一次扔在第x-1层(比x小):
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-2层。
这样一来,我们总共尝试了x-2+1 = x-1次,虽然没有超出假设次数,但似乎有些过于保守。
假设第一次扔在第x层:
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-1层。
这样一来,我们总共尝试了x-1+1 = x次,刚刚好没有超出假设次数。
因此,要想尽量楼层跨度大一些,又要保证不超过假设的尝试次数x,那么第一次扔鸡蛋的最优选择就是第x层。
以上都是假设+逻辑推理,并没有经过严格的数学证明,我们也不是数学家
归纳
如果第一次扔鸡蛋没有碎,我们的尝试消耗了一次,问题就转化成了两个鸡蛋在100-x层楼往下扔,要求尝试次数不得超过x-1次
所以第二次尝试的楼层跨度是x-1层,绝对楼层是x+(x-1)层
同理,如果鸡蛋还没有碎,第三次楼层跨度是x-2,第四次是x-3
小伙伴们,到此看出了规律没?根据总结,可以列出一个楼层数的方程式:
x + (x-1) + (x-2) + ... + 1 = 100
下面我们来解这个这个方程:
(x+1)*x/2 = 100
最终x向上取整,得到 x=14
因此,最优解在最坏情况的尝试次数是 14 次,第一次扔鸡蛋的楼层也是 14 层。
最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:
14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
举个栗子验证下: 假如鸡蛋不会碎的临界点是65层,那么第一个鸡蛋扔出的楼层是14,27,50,60,69。这时候啪的一声碎了。 第二个鸡蛋继续,从61层开始,61,62,63,64,65,66,啪的一声碎了。 因此得到不会碎的临界点65层,总尝试次数是 6 + 6 = 12 < 14 。
进阶版面试题
题目描述
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
示例1:
输入:K = 1, N = 2 输出:2 解释: 鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。 否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。 如果它没碎,那么我们肯定知道 F = 2 。 因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例2:
输入:K = 2, N = 6 输出:3
示例3:
输入:K = 3, N = 14 输出:4
提示:
1. 1 <= K <= 100 2. 1 <= N <= 10000
动态规划求出扔鸡蛋问题的通解 1
什么是动态规划?
动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划解决问题的过程分为两步:
1.寻找状态转移方程式
2.利用状态转移方程式自底向上求解问题
如何找到状态转移方程式?
在标准版问题中,两个鸡蛋100层楼的条件下,我们找到的规律:
假设存在最优解,在最坏情况下尝试次数是x,那么第一个鸡蛋首次扔出的楼层也是x
这个规律在三个以上鸡蛋的条件下还能否适用呢?
假设有三个鸡蛋,100层楼,第一个鸡蛋扔在第10层并摔碎了。这时候我们还剩下两个鸡蛋,因此第二个鸡蛋不必从底向上一层一层扔,而是可以选择在第5层扔。如果第二个鸡蛋也摔碎了,那么第三个鸡蛋才需要老老实实从第1层开始一层一层扔。 这样一来,总的尝试次数是1+1+4 = 6 < 10(最少次数)。 因此,最优解的最坏情况下尝试次数是 X,鸡蛋首次扔出的楼层也是 X 这个规律不再成立。
那么,我们如何寻找规律呢?
在这里,我们把M层楼/N个鸡蛋的问题,抽象成一个黑盒子函数F(M,N),楼层数M和鸡蛋数N是函数的两个参数,函数的返回值是最优解的最大尝试次数
假设我们第一个鸡蛋扔出的位置在第X层(1<=X<=M),会出现两种情况:
1.第一个鸡蛋没碎
那么剩余的M-X层楼,剩余N个鸡蛋,可以转变为下面的函数:
F(M-X,N)+ 1,1<=X<=M
2.第一个鸡蛋碎了
那么只剩下从1层到X-1层楼需要尝试,剩余的鸡蛋数量是N-1,可以转变为下面的函数:
F(X-1,N-1) + 1,1<=X<=M
整体而言,我们要求出的是 N层楼 / K个鸡蛋 条件下,最大尝试次数最小的解,所以这个题目的状态转移方程式如下:
X可以为1......N,所以有M个Max( F(N-X,K)+ 1, F(X-1,K-1) + 1)的值,最终F(N,K)是这M个值中的最小值,即最优解
F(N,K)= Min(Max( F(N-X,K)+ 1, F(X-1,K-1) + 1)),1<=X<=N
如何进行求解?
状态转移方程式有了,如何计算出这个方程式的结果呢?
诚然,我们可以用递归的方式来实现。但是递归的时间复杂度是指数级的,当M和N的值很大的时候,递归的效率会变得非常低。
根据动态规划的思想,我们可以自底向上来计算出方程式的结果。
何谓自底向上呢?让我们以3个鸡蛋,4层楼的情况为例来进行演示。
根据动态规划的状态转移方程式和自底向上的求解思路,我们需要从1个鸡蛋1层楼的最优尝试次数,一步一步推导后续的状态,直到计算出3个鸡蛋4层楼的尝试次数为止。
首先,我们可以填充第一个鸡蛋在各个楼层的尝试次数,以及任意多鸡蛋在1层楼的尝试次数。
原因很简单:
1.只有一个鸡蛋,所以没有任何取巧方法,只能从1层扔到最后一层,尝试次数等于楼层数量。
2.只有一个楼层,无论有几个鸡蛋,也只有一种扔法,尝试次数只可能是1。
按照上面的方程式,代入计算,得出下面的结果。具体计算过程就不细说了
代码实现
根据刚才的思路,代码初步实现:
func superEggDrop(K, N int) int { if K < 1 || N < 1 { return 0 } //备忘录,存储K个鸡蛋,N层楼条件下的最优化尝试次数 //cache := [K + 1][N + 1]int{} cache := make([][]int, K+1) //把备忘录每个元素初始化成最大的尝试次数 for i := 0; i <= K; i++ { cache[i] = make([]int, N+1) for j := 1; j <= N; j++ { cache[i][j] = j } } for n := 2; n <= K; n++ { for m := 1; m <= N; m++ { //假设楼层数可以是1---N, min := cache[n][m] for k := 1; k < m; k++ { //M层,N鸡蛋,F(N,K)= Min(Max( F(N-X,K)+ 1, F(X-1,K-1) + 1)),1<=X<=N //(动态规划) //鸡蛋碎了 max := cache[n-1][k-1] + 1 if cache[n][m-k]+1 > max { max = cache[n][m-k] + 1 //鸡蛋没碎 } if max < min { min = max } } cache[n][m] = min } } return cache[K][N] }
三层循环,时间复杂度是O(K*N*N)
二维数组:空间复杂度是O(M*N)
时间复杂度太高,无法通过leetcode的测试用例,一直超时
动态规划求出扔鸡蛋问题的通解 2
上面的解决办法,时间复杂度相当高,那么是否存在更快的算法呢?
上面的算法中,主要在于三层for循环,需要假设第一次扔鸡蛋分别从第1.....N层
有没有一种算法,结合归纳演绎和动态规划的思想,在这里可以进一步抽象?
假设移动x次,k个鸡蛋,最优解的最坏条件下可以检测n层楼,层数n=黑箱子函数f(x,k) 假设从n0+1层丢下鸡蛋, 1,鸡蛋破了 剩下x-1次机会和k-1个鸡蛋,可以检测n0层楼 2, 鸡蛋没破 剩下x-1次机会和k个鸡蛋,可以检测n1层楼 那么 临界值层数F在[1,n0+n1+1]中的任何一个值,都都能被检测出来 归纳的状态转移方程式为:f(x,k) = f(x-1,k-1)+f(x-1,k)+1,即x次移动的函数值可以由x-1的结果推导,这个思路很抽象,需要花时间去理解,具体看代码,对照着代码理解 可以简化为黑箱子函数的返回值只跟鸡蛋个数k有关系: 本次fun(k) = 上次fun(k-1)+上次fun(k)+1
代码实现
时间复杂度是O(K*moves),跟楼层数无关(楼层数N的值相对很大)
func superEggDrop(K, N int) int { moves := 0 dp := make([]int, K+1) // 1 <= K <= 100 // dp[i] = n 表示, i 个鸡蛋,利用 moves 次移动,最多可以检测 n 层楼 for dp[K] < N { for i := K; i > 0; i-- { //逆序从K---1,dp[i] = dp[i]+dp[i-1] + 1 相当于上次移动后的结果,dp[]函数要理解成抽象出来的一个黑箱子函数,跟上一次移动时鸡蛋的结果有关系 dp[i] += dp[i-1] + 1 // 以上计算式,是从以下转移方程简化而来 // dp[moves][k] = 1 + dp[moves-1][k-1] + dp[moves-1][k] // 假设 dp[moves-1][k-1] = n0, dp[moves-1][k] = n1 // 首先检测,从第 n0+1 楼丢下鸡蛋会不会破。 // 如果鸡蛋破了,F 一定是在 [1:n0] 楼中, // 利用剩下的 moves-1 次机会和 k-1 个鸡蛋,可以把 F 找出来。 // 如果鸡蛋没破,假如 F 在 [n0+2:n0+n1+1] 楼中 // 利用剩下的 moves-1 次机会和 k 个鸡蛋把,也可以把 F 找出来。 // 所以,当有 moves 个放置机会和 k 个鸡蛋的时候 // F 在 [1, n0+n1+1] 中的任何一楼,都能够被检测出来。 } moves++ } return moves }
总结
- 对于类似的智力题,如果不能想出其它办法,我们可以采用先假设存在某个满足结果的最优解x,然后代入上下文进行分析问题,归纳演绎,找出规律
- 对于很复杂的问题,可能需要非常发散的思维,对算法进行高度抽象化
- 思考问题的过程很烧脑,与君共勉!
GitHub
- 项目源码在这里
- 笔者会一直维护该项目,对leetcode中的算法题进行解决,并写下自己的思路和见解,致力于人人都能看懂的算法
个人公众号
- 喜欢的朋友可以关注,谢谢支持
- 来自:吴名(微信号:wm497735138),作者:吴名
以上所述就是小编给大家介绍的《一篇文章带你搞定经典面试题之扔鸡蛋问题》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 一篇文章搞定前端面试
- 搞定面试中的系统设计题
- Golang精编100题-搞定golang面试
- 一文搞定HashMap的实现原理和面试
- 一文搞定 UDP 和 TCP 高频面试题!
- 搞定PHP面试 - HTTP协议知识点整理
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Microsoft.NET框架程序设计
Jeffrey Richter / 李建忠 / 清华大学出版社 / 2003-11 / 68.00元
《Microsoft.NET框架程序设计》(修订版)是《微软.NET程序员系列》丛书之一,主要介绍如何开发面向Microsoft.NET框架的各种应用程序。Microsoft.NET框架是微软公司推出的新平台,包含通用语言运行时(CLR)和.NET框架类库(FCL)。《Microsoft.NET框架程序设计》(修订版)将深入解释CLR的工作机制及其提供的各种构造,同时还将讨论FCL中一些重要的类型......一起来看看 《Microsoft.NET框架程序设计》 这本书的介绍吧!
HTML 编码/解码
HTML 编码/解码
XML 在线格式化
在线 XML 格式化压缩工具