两个鸡蛋确定楼层
哪些公司问过
答案要点
- 目标:最坏情况下的最少次数;让每一次扔的最坏情况总次数相同
- 设最少 n 次:第一次从第 n 层扔,之后每次少走一层(n-1、n-2、……)
- 总楼层覆盖 n + (n-1) + … + 1 = n(n+1)/2 ≥ 100,得 n = 14
- 策略:第一个鸡蛋依次从 14、27、39、50、60、69、77、84、90、95、99、100 层扔
- 碎了就用第二个鸡蛋从上次没碎的楼层往上逐层试;一般情况用动态规划
易错点
- 直接每 10 层扔一次,最坏 19 次,不是最优
- 不明白为什么要让每次递减
- 把题目当作求平均次数,而不是最坏情况
- 一般情况的 DP 转移写错
面试官常见追问
- 为什么递减的步长是最优的?
- k 个鸡蛋 n 层楼怎么做?
- 如果只有一个鸡蛋怎么办?
- 二分查找可以吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。