飞机座位分配概率(LeetCode 1227)
哪些公司问过
答案要点
- 结论:n=1 时为 1,n≥2 时恒为 1/2
- 递推:f(n) = 1/n + (1/n)·Σ_{k=2}^{n−1} f(k)
- 第一人坐 1 号座则成功,坐 n 号座则失败,坐 i 号座则规模缩为 n−i+1
- 对称性:随机选座者选中 1 号或 n 号座的概率相同,先选中者决定结局
- 复杂度:公式 O(1);直接递推 O(n²),前缀和优化为 O(n)
易错点
- n=1 时也回答 1/2
- 直接写递归不加记忆化,导致指数级复杂度
- 只背结论,说不出对称性或递推的证明
面试官常见追问
- LeetCode 1227 解法的复杂度?如何优化到 O(n)?
- 第 k 位乘客坐到自己座位的概率呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。