扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 面试中的智力题 > 24.高层扔鸡蛋问题:有一个100层的高楼,给你两个鸡蛋,需要测试出在哪层楼扔鸡蛋,鸡蛋不会碎。鸡蛋如果没有碎可以扔无数次。最少需要扔多少次?

这是一个非常经典的动态规划问题,手撕代码时也很常见

如果是只有1个鸡蛋,这个问题就很简单了,为保证一定找到这个楼层,只能从第一层开始试。

题目中是两个鸡蛋,正常就是会想到二分法之类,先在50层扔一个,没碎,捡回来在75层扔,碎了,第二个鸡蛋只能从第1层开始试了。第一个鸡蛋用来缩短范围,第二个鸡蛋用来遍历范围。

假设需要x次才能找到临界的楼层,也就是说第一个鸡蛋从第x层扔出(因为需要考虑最差情况,万一第一个鸡蛋碎了,为保证x次能找到,第一个鸡蛋需要从x层扔出。因为如果鸡蛋恰好在第x层碎了,在第x-1层没碎,第一个鸡蛋在x层以上的楼层扔的话,第二个鸡蛋需要遍历x次,一共需要x+1次)

如果第一个鸡蛋碎了,第二个鸡蛋遍历1至x-1层,则需要x次找到。

如果第一个鸡蛋没碎,则第一个鸡蛋的任务是需要继续缩小范围,还是为了保持这个x次能找到临界楼层的条件,现在只剩x-1次了,下一次只能在x+x-1层扔第一个鸡蛋,以此类推,x+(x-1)+(x-2)+……+1>=100,x=14

也就是说最少需要扔14次。

这个问题还有一些变种问题,比如2个鸡蛋,n层楼;k个鸡蛋,n层楼(力扣887题,大家感兴趣可以看看)


点击面试手册,获取本站面试手册PDF完整版