网站建设营销一站式服务,红酒企业网站模板免费下载,搜索引擎营销的英文缩写,人们常用的网页设计工具是今天想跟大家分享一个有意思的面试题#xff0c;这让我再一次感叹思维的奇妙#xff0c;接下来我们一起看看吧~
首先来看看题目#xff1a;
你有2颗鸡蛋#xff0c;需要以最少的尝试次数来判断在100层的高楼上#xff0c;哪一层楼是鸡蛋的安全层。
换句话说#xff0c…今天想跟大家分享一个有意思的面试题这让我再一次感叹思维的奇妙接下来我们一起看看吧~
首先来看看题目
你有2颗鸡蛋需要以最少的尝试次数来判断在100层的高楼上哪一层楼是鸡蛋的安全层。
换句话说就是需要确定我们从哪一层楼扔鸡蛋下去鸡蛋恰好不会摔碎。高于安全层鸡蛋都会碎低于安全层都不会碎。比如鸡蛋在第1层没有摔碎在第2层摔碎了那么鸡蛋的安全层就是第1层。
这里有几个假设条件 没有摔碎的鸡蛋可以重复使用 每颗鸡蛋的坚硬程度都是相同的。 这道题乍一看挺简单的但其实解答相对复杂而且解法多种多样要在面试时逻辑清楚地表达完整思路不仅要求面试者的知识储备要广、反应能力要快逻辑思维和语言表达能力也是必不可少的。
成为经典可谓当之无愧。
解法1简单粗暴
我们先来个最省事儿的方法假设我们只有一颗鸡蛋显然只有从一楼开始扔逐层试探直到鸡蛋摔碎安全层就是第N-1层。
但是缺点想必大家也看出来了这是拼运气啊最坏情况需要扔100次。
用一颗鸡蛋的方法虽然简单粗暴但也是给两颗鸡蛋的情况缕清一些思路。
简单写一下如何实现
// 假设arr表示100层楼,每层楼鸡蛋会不会碎,如果arr[i] 1 表示i层楼的鸡蛋会碎,arr[i] 0表示第i层楼的鸡蛋不会碎// 简单暴力
const throwEggs1 (arr) {for(let i 1; i 100; i) {if (arr[i] 1) {return i}}
}解法2常规二分
有两颗鸡蛋二分法想必是大多数同学脑海里浮现的第一个念头吧
我们先从50楼扔一颗鸡蛋如果没碎就往上继续二分到75楼继续扔······
这是比较顺利的情况如果不顺利呢比如我们从50楼扔鸡蛋直接碎了那就只有一颗鸡蛋了。
这时候我们就回到解法1了只能从1楼开始遍历又是拼运气的时候了要是运气好1楼鸡蛋就没了那测试次数就是112次但最坏情况就是14950次。
这么多次显然是不能通过google面试的。
// 常规二分const throwEggs2 (arr) {let left 1let right 100let mid 0while(left right) {mid Math.floor(left right) / 2if (arr[mid] 0) {left mid 1} else {right mid - 1}}return mid
}解法3均衡切割
虽然二分法不够优秀但体现了切分范围的思想。
我们的基本思路是将100层切分成两个维度由两个鸡蛋分别控制一个维度。
一个维度是用第一颗鸡蛋分金定穴另一个维度是用第二颗鸡蛋在前蛋的基础上进行遍历。
换言之我们是将100层切分成若干个区块由第一颗鸡蛋确定最高安全楼层所属的区块再由第二颗鸡蛋逐层确定其具体的位置。
在1-100层楼之间假设我们从上往下尝试即从100层开始扔第一颗蛋大概率是碎了那第二颗蛋便又回到了解法1。
所以我们应该从下往上进行划分、尝试这样即使第一颗鸡蛋碎了用第二颗蛋遍历的成本也比较低。
比如第一颗蛋每10层扔一次第一次从10层扔第二次从20层扔第三次从30层扔……一直扔到100层。
第二颗蛋就只用在第一颗蛋摔碎的层数和前一次的安全层之间的9层进行范围遍历。
也就是说要是第一颗鸡蛋在第30层摔碎了那就拿第二颗蛋从21层到29层逐层尝试。
这样的最好情况就是第一颗蛋在第10层碎掉总的尝试次数为112次。
最坏的情况是在第100层碎掉总尝试次数为10919次。 // 均衡切割
const throwEggs3 (arr) {let count 0// 第一个鸡蛋for (let i 1; i 10; i) {if (arr[i * 10] 1) {count i * 10break}}// 第二个鸡蛋for(let i count - 1; i count - 10; i--) {if (arr[i] ! 1) {return i}}
}解法4微妙平衡
上面的方法看似已经比较完美了。
但是我们再具像化一点就能发现问题第一颗鸡蛋能快速定位安全楼层低的情况但如果安全楼层位置越高耗时就会越久而第二颗鸡蛋在每个区块内的消耗都是一样的。
如果鸡蛋的最高安全层为18或者98用解法3的思路的话这两种情况的总尝试次数并不一样
最高安全楼层为18时第一颗鸡蛋试了2次就定位了区块而最高安全楼层为98时第一颗鸡蛋试了10次才定位了区块。
虽然第二颗鸡蛋在区块内部的逐层尝试次数是一样的但98层对应的总尝试次数就多太多了。
原因就是区块完全均匀划分对大数不利。
明白了这个缺陷也就知道了改进的基本思想要对100找出一种二维区块划分但不是均匀划分。
对于比较小的区块部分其包含的楼层范围可以适当增加越向大数部分走其包含的楼层范围越来越小。从下往上每一个区块内所含楼层递减。
在最高安全楼层比较低的情况下第一颗鸡蛋尝试的次数少在最高安全楼层比较高的情况下则第二颗鸡蛋尝试的次数少。
就是用第二颗鸡蛋尝试次数的减少来弥补第一颗鸡蛋需要的尝试次数的递增使两颗鸡蛋在不同维度上的尝试次数此消彼长达到一种总体上的平衡。
每上一个区块第一颗鸡蛋消耗的次数就1我们索性就假设每个区块包含的楼层数逐级递减1以达到平衡。
那么每个区块包含的层数应该如何划分呢
我们假设第一个区块有X层那么第二个就是X-1以此类推我们就得到了一个方程式
XX-1X-2···321≥100
可以看出来这时候区块个数和第一个区块包含的层数其实是相等的。 现在我们回过头来再仔细看看方程式是不是有点熟悉不就是等差数列求和么
所以我们化简方程式
X(X1)/2≥100
这里X最小值我们向上取整得到14。
有同学会问为什么一定到1呢最后一个区块一定只有1层吗
不是的到1是表示在X个区块的情况下最多能覆盖的层数。
比如我们这个例子X是14求出的楼层总数是105也就是可以覆盖105层题目要求的100层当然绰绰有余。
由此第一个区块包含14层楼即1到14层
第二个区块包含13层楼即15到27层
第三个区块包含12层楼即28到39层
······
第一颗鸡蛋依次试第14、27、39、50、60、69、77、84、90、95、99、100层。只要期间任何一次鸡蛋碎了就拿第二颗鸡蛋从上一次的安全层之后开始逐层尝试直至第二颗鸡蛋也摔碎为止。
用这个方法总次数一定不会超过14次。
因为最高安全楼层越高第一颗鸡蛋的尝试次数也就越多但第二颗鸡蛋的尝试次数随之越来越少两者始终维持着一种微妙的平衡最后总的尝试次数波动也不会太大。 下面是全部的代码实现
// 假设arr表示100层楼,每层楼鸡蛋会不会碎,如果arr[i] 1 表示i层楼的鸡蛋会碎,arr[i] 0表示第i层楼的鸡蛋不会碎// 暴力
const throwEggs1 (arr) {for(let i 1; i 100; i) {if (arr[i] 1) {return i}}
}// 常规二分const throwEggs2 (arr) {let left 1let right 100let mid 0while(left right) {mid Math.floor(left right) / 2if (arr[mid] 0) {left mid 1} else {right mid - 1}}return mid
}// 均衡切割
const throwEggs3 (arr) {let count 0// 第一个鸡蛋for (let i 1; i 10; i) {if (arr[i * 10] 1) {count i * 10break}}// 第二个鸡蛋for(let i count - 1; i count - 10; i--) {if (arr[i] ! 1) {return i}}
}// 微妙平衡
const throwEggs4 (arr) {let block 10let count 0// block(block 1) / 2 100while(block * block block 100 * 2) {block}// 第一个鸡蛋的尝试let temp block // 每层区块的最后一个while(temp 100) {if (arr[temp] 1) {count tempbreak}--blocktemp block}// 第二个鸡蛋的尝试for(let i count - 1; i count - block; i--) {if (arr[i] 0) {return i}}
}除了文中我们讨论的解法这道题也还有其他解法可以选择如果感兴趣大家可以自己研究研究也欢迎来一起讨论
凭心而论要是在毫无准备的情况下一般人只能想到第一种做过算法题的应该能够想到第二种想到解法三已经是最优解了能在这么短的时间内想到解法四的大神是凤毛麟角。
好了祝大家周末愉快
最后希望大家读完这篇文章都能有所收获
