猴子吃桃问题:逆推求最初桃子数
哪些公司问过
答案要点
- 逆推关系:吃完剩 r 个,则吃之前有 2(r+1) 个
- 从第 n 天吃完后剩 0 开始,往前迭代 n 次即可,循环 O(n) 时间 O(1) 空间
- 闭式解:最初桃子数为 2^(n+1) - 2,可用小样例 n=1 得 2 验证
- 经典变体“第 10 天早上只剩 1 个”答案为 1534,需先确认题意边界
- n 较大时结果指数增长,注意整数溢出,使用 long long 或大数
易错点
- 正向模拟去猜初始值,而不是用逆推公式
- 混淆“第 n 天吃完后剩 0”和“第 n 天早上剩 1 个”两种题意
- n 稍大就用 int 存储导致溢出
面试官常见追问
- 递归和循环写法哪个更好?
- 如何验证答案正确?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。