LeetCode 1227在题解区的画风一直很特别正经推导没多少人在写评论区最常见的回复就是“这不就是 return n 1 ? 1 : 0.5 吗”而且这样的代码确实能过。于是很多人刷完这道题留下的印象只有“又一个脑筋急转弯”。但如果你愿意认真把这个概率过程推一遍会发现它比想象中有层次得多既能练到状态抽象又能练到数学归纳还能在面试被追问时用一条非常漂亮的对称性原理解释清楚。这篇文章想做的就是把飞机座位分配问题从头到尾拆开题目到底在描述什么、递推方程怎么来、为什么结论稳定在 0.5、以及那些改一改条件就面目全非的变体。刚入门刷题的同学可以重点看前两章被面试官问烦了的人可以直接跳到第 4 章的直觉解释和第 6 章的复盘。1. 题目到底在问什么先把场景在脑子里完整跑一遍1.1 场景还原与题面拆解有 n 个乘客即将登机飞机上有 n 个座位编号从 1 到 n乘客 i 的登机牌上写的是 i 号座。乘客 1 第一个走进机舱他发现登机牌丢了于是在 n 个座位里等概率随机挑一个坐下。从乘客 2 开始每个人都执行一条固定规则如果自己的座位还空着就坐自己的如果自己的座位被前面的人占了就在剩余空位中等概率随机挑一个。乘客 n 是最后一个登机的问他能坐到自己座位 n 号位的概率是多少题目限制 n 1。当 n 1 时第一个乘客就是最后一个乘客他随机选的唯一座位正好是自己的座位概率直接就是 1。这也是整道题唯一的边界特例。复述题面的时候有一个细节值得单独拎出来说后续乘客并不是“每个人都随机选座”而是“自己的座位空着就一定坐自己的被占了才随机”。这个前提决定了整个随机过程不是简单的均匀随机抽样。很多人第一反应是“n 个座位最后一个乘客坐对概率不是 1/n 吗”恰恰就是因为忽略了后续乘客会优先吸收掉自己座位对应的随机性导致越往后局面越不像一个纯粹的均匀随机问题。1.2 三个常见的理解误区第一个误区是把最终概率当成古典概型。古典概型要求每个基本事件等概率但这个实验的完整结果不是简单从 n 个座位里抽一个。中间任何一次“被迫随机”都会改变后面的空位结构所以不能直接拿座位总数做分母。第二个误区是觉得“越靠后越倒霉最后乘客概率应该趋近 0”。这个直觉来自“座位可能被前面任意一个人占掉”但只要认真算就会发现倒数第一个乘客的成功率在 n2 时恒定是 0.5并不会随着 n 增大而衰减。第三个误区是混淆“最后一个座位提前被占的概率”和“最后一个乘客坐对的概率”。实际上这两个事件是等价的最后乘客坐对当且仅当 n 号座位在轮到他之前没有被占。所以算坐对概率本质上是在算 n 号座位在整条随机链条中“活到最后一刻”的概率。想清楚这一点后面理解 0.5 会容易很多。2. 从暴力枚举到递归方程让概率结构自己浮现2.1 状态定义F(n) 到底表示什么我设 F(n) 表示在一个规模为 n 的问题里第一个上飞机的乘客是“随机选择者”他会等概率选择任意一个座位后续乘客遵循“座位空着就坐自己的被占才随机”的规则最后一位乘客最终坐到自己座位的概率。这里的关键是这个状态只和当前问题的规模 n 有关和具体座位编号无关。初次接触递推的人会问如果中间某个座位被占了剩余空位并不是连续的编号怎么能保证还是同一个问题举个具体例子。n 5乘客 1 随机坐到了 3 号座那么乘客 2 上来时发现 2 号座空着会正常坐自己的座位。乘客 3 上来时才发现自己座位被占此时剩余空位是 1、4、5 号座。站在乘客 3 的视角看他是在 3 个空位里随机选。如果我们把 1 号座重新标记成“自己的座位”、4 号座标记成“下一个人的座位”、5 号座标记成“最后乘客的座位”就会发现这和原来问题的结构完全一致只是规模从 5 缩到了 3。这种方法叫相对编号真正影响概率的从来不是绝对座位号而是“还剩多少个位置处于同一套随机规则之下”。2.2 第一次随机选择的三种去向与递推方程第一个人选择座位时所有情况可以分成三类。第一类他选到了自己的 1 号座概率是 1/n。此时后面所有乘客都能按编号正常入座最后乘客必然坐到自己座位所以这类情况的成功概率是 1。第二类他选到了最后乘客的 n 号座概率也是 1/n。n 号座被占后最后乘客无论怎么选都不可能坐回自己的座位所以这类情况成功概率是 0。第三类他选到了某个中间座位 k其中 k 的范围是 2 到 n-1概率同样是 1/n。座位 k 被占后前面的乘客 2 到 k-1 都会正常入座轮到乘客 k 时他会成为新的“随机选择者”。正如上一节所说此时问题变成规模为 n-k1 的同构子问题所以这类情况对成功概率的贡献是 F(n-k1)。把这三类情况按全概率公式加起来F(n) (1/n) * [1 0 F(n-1) F(n-2) ... F(2)]更整洁一点可以写成F(n) (1 / n) * [1 F(2) F(3) ... F(n-1)]边界条件 F(1) 1。2.3 用记忆化搜索验证前几项这个递推方程本身就可以用代码验证。写一个简单的记忆化递归把前几项打印出来看看趋势。from functools import lru_cache lru_cache(maxsizeNone) def f(n: int) - float: if n 1: return 1.0 total 1.0 # 第一个乘客直接选1号座的情况 for j in range(2, n): total f(j) return total / n for n in range(1, 11): print(n, f(n))跑出来的结果非常整齐1 1.0 2 0.5 3 0.5 4 0.5 5 0.5 6 0.5 7 0.5 8 0.5 9 0.5 10 0.5从 n2 开始答案清一色是 0.5。这个结果看起来很“无聊”但正是这种无聊里藏着这道题最值得琢磨的地方为什么无论 n 多大概率都是一个常数这时候就该上数学归纳法了。3. 数学归纳法把 0.5 钉死边界证明比结论重要3.1 枚举前面的完整计算过程在正式归纳前先把 n2、3、4、5 的计算过程展开这样后面看归纳会更有体感。n2 时第一个乘客只有两个选择选 1 号座最后乘客成功选 2 号座最后乘客失败。所以 F(2) 1/2。n3 时第一个乘客选 1 号座概率 1/3直接成功选 3 号座概率 1/3直接失败选 2 号座概率 1/3此时乘客 2 在 1 号和 3 号之间随机成功失败各一半。所以 F(3) (1/3) * 1 (1/3) * F(2) (1 0.5) / 3 0.5。n4 时F(4) (1/4) * [1 F(2) F(3)] (1 0.5 0.5) / 4 0.5。n5 时F(5) (1/5) * [1 F(2) F(3) F(4)] (1 0.5 0.5 0.5) / 5 0.5。可以整理成一张表n计算过程F(n)1特殊情况121 / 20.53(1 0.5) / 30.54(1 0.5 0.5) / 40.55(1 0.5 0.5 0.5) / 50.53.2 归纳假设的坑为什么不能从 n1 开始很多人看到这张表会想F(1)1F(2) 开始都是 0.5那我证明“从第二项起全是 0.5”就是了。但实际操作中很容易出现一个不严谨的表述“假设 F(1) 到 F(n-1) 都为 0.5然后推出 F(n)0.5”。这个表述是错的因为 F(1) 是特例假设里不能包含它。正确做法是明确归纳命题只对 n 2 成立归纳起点是 F(2) 0.5。证明时只用 F(2) 到 F(n-1) 都等于 0.5完全不需要 F(1) 参与。这个细节看起来很小却是我见过很多人在推导时翻车的地方——结论本身没错但证明陈述不严谨面试官一追问就露怯。3.3 归纳证明全过程现在做完整归纳。基础情况已经验证 F(2) 0.5。假设对于某个 n 3所有 F(2)、F(3)、...、F(n-1) 都等于 0.5。根据递推方程F(n) (1/n) * [1 F(2) F(3) ... F(n-1)]把归纳假设代入方括号里除了开头的 1剩下 n-2 项都是 0.5F(n) (1/n) * [1 (n-2) * 0.5]继续化简F(n) (1/n) * [1 (n-2) / 2] (1/n) * [n / 2] 1/2归纳完成。也就是说从 n2 开始概率永远恒等于 0.5不存在其他隐藏状态。3.4 推导出 O(1) 结论后的代码形态递推归纳的最终结论落到代码上就是一道分叉判断class Solution: def nthPersonGetsNthSeat(self, n: int) - float: return 1.0 if n 1 else 0.5如果你只看结论这道题确实配得上“脑筋急转弯”这个标签。但推导过程的价值在于它让你有底气在面试时证明“我不是背答案我知道这个 0.5 是怎么撞出来的”。4. “劫持链条”直觉1号座位和n号座位在玩对称游戏4.1 链条如何传递从“乘客1坐错位置”说起数学证明严谨但对部分读者来说不够直观。这里分享一个我常用的“劫持链条”解释。把“某个人坐到了另一个人的座位上”看成一次劫持。乘客 1 是链条起点。如果他选了 1 号座链条当场结束所有人正常入座最后乘客成功如果他选了 n 号座链条也当场结束但最后乘客失败如果他选了中间某个座位 k乘客 k 的座位被劫持了下一个被劫持者就是乘客 k。当乘客 k 上飞机时他的座位已经没了只能随机选一个剩余空位。如果他随机选到 1 号座链条结束此时后面所有人包括被劫持过的乘客 k 自己都能找到自己的座位最后乘客成功如果他随机选到 n 号座链条结束最后乘客失败如果他随机选到另一个还没登机的人的座位那么劫持者身份继续转移。关键来了在链条没有结束的任何一个时刻1 号座和 n 号座都一定还是空着的。因为一旦这两个座位中的任何一个被选中链条就已经终止不会再有“下一次随机选择”。所以只要链条还在传递这两个座位就像两个并列的终止开关始终同时存在于下一轮随机选择的候选池里。4.2 两条吸收路径的对称性整个随机过程可以看成一条随机游走最终只有两种吸收结局某个时刻有人选了 1 号座或者有人选了 n 号座。这两种结局分别对应最后乘客成功与失败。在每个还没终止的节点上1 号座和 n 号座在候选集合里的地位完全对称它们被选中的概率始终相同而且一旦被选中就立刻决定结局。其他中间座位的选择只是把劫持者换成下一个人并不会直接决定成功或失败。既然每一步“选到 1 号座”和“选到 n 号座”的概率都相等那么整条随机链最终“先吸收到 1 号座”和“先吸收到 n 号座”的概率也相等。二者概率之和为 1所以各占 1/2。这个直觉比数学归纳法更适合在面试中口头表述。它不会替代证明但它能帮你快速建立一个“正确答案就该是 0.5”的方向感。4.3 用 n3 和 n4 的路径表验证直觉对称性听起来有点玄我们用小规模路径验证一下。n3 时把乘客 1 的所有选择和后续发展列出来乘客1的行为概率后续最后乘客成功概率贡献选1号座1/3全部正常入座1/3选3号座1/3最后乘客座位被占0选2号座1/3乘客2在1号和3号间随机1/3 * 1/2 1/6成功概率合计 1/3 1/6 1/2。再看 n4乘客1的行为概率后续最后乘客成功概率贡献选1号座1/4全部正常入座1/4选4号座1/4最后乘客座位被占0选2号座1/4变成规模3的子问题成功概率0.51/4 * 1/2 1/8选3号座1/4变成规模2的子问题成功概率0.51/4 * 1/2 1/8成功概率合计 1/4 1/8 1/8 1/2。可以看到无论中间怎么绕最终都是“1 号座先被选中”和“n 号座先被选中”在竞争双方势均力敌。5. 变体题大赏条件稍微改一改题目还成立吗5.1 变体一第一个乘客坐到自己座位的概率这个问题可以作为热身第一个乘客在 n 个座位里均匀随机选坐到自己座位的概率当然是 1/n。它和原题放在一起看会产生一个非常反直觉的对比第一个乘客坐对的概率只有 1/n而离他最远的最后乘客反而有 0.5 的概率坐对。原题里最吃亏的反而是最初制造随机性的那个人因为他的座位没有被任何一个“正常乘客”保护纯粹是被自己随机掉的。这个变体经常被面试官当作追问的第一个台阶用来确认你是否真的理解随机链条的位置差异。5.2 变体二如果随机者不是第一个而是第 m 个乘客把题目改成前 m-1 个乘客都正常按规则入座第 m 个乘客才是丢登机牌的人他会在剩余空位中等概率随机选一个问最后乘客坐对的概率。前 m-1 个乘客都会坐自己的座位不会占用别人的位置所以轮到第 m 个乘客时1 到 m-1 号座位已经坐满剩余空位是 m、m1、...、n一共 n-m1 个。第 m 个乘客随机选完以后问题就等价于一个规模为 n-m1 的原版问题。直接套结论如果 n-m1 1也就是 m n答案就是 1因为最后一个乘客自己就是随机者他面前只剩自己的座位如果 n-m1 2答案就是 0.5。这个变体说明一个问题原题里的“随机者”和“最后乘客”的相对位置并不重要重要的是从随机者开始后面还剩多少个座位处于同构规则之下。5.3 变体三如果第一个乘客有一定概率坐对答案怎么变这是我在面试复盘中最喜欢抛给对方的一个扩展。假设第一个乘客有概率 p 会老老实实坐自己的 1 号座只有 1-p 的概率会随机乱坐那么最后乘客坐对的概率是多少当第一个乘客坐对时概率 p后面所有人都正常入座最后乘客成功当第一个乘客乱坐时概率 1-p整个问题退化成原题最后乘客成功概率是 0.5。因此P p * 1 (1-p) * 0.5 0.5 0.5pp 0 时就是原题答案 0.5p 1 时全员归位答案 1p 0.5 时答案就是 0.75。这个公式非常干净而且能看出原题 0.5 其实是 p0 的特例。5.4 变体四一道留给你自己推的思考题有个讨论度很高的改法如果前两位乘客都没有看座位号无论自己的座位空不空都在剩余空位里随机选问最后乘客坐对的概率。这道题比原题难不少因为它改变了“被占才随机”这个关键规则。定义状态时必须多引入一个维度还剩多少个“正常被动乘客”、还剩多少个“随机主动乘客”然后做二维递推。n3 时你可以手算出答案不是 0.5而是 1/3。这类思考题很适合用来检验自己是否真的理解了原题的结构。原题之所以能递归简化正是因为从第二个乘客开始几乎所有人都被“自己的座位空着就坐自己的”这条规则保护住随机性很难扩散而一旦有多名主动随机者保护层被打破概率结构会立刻变得复杂。6. 提交代码与面试复盘三个容易翻车的细节6.1 看似能用的 DP 方案为什么过不了看到递推方程的第一反应通常是开一个长度为 n 的 DP 数组从小到大算一遍。这个思路没有错但 LeetCode 1227 的 n 上限是 10^9至少是远超 DP 数组可接受范围的量级开 O(n) 数组在内存上完全不可行递归写法在数据量大时也必然爆栈。所以这道题真正的工程解必须落在 O(1) 时间和 O(1) 空间上。数学结论在这里不是“投机取巧”而是经过推导后唯一合理的实现方式。6.2 返回值类型、n1 边界、O(1) 编码三个细节最终提交代码很短但越短的代码越容易在细节上翻车。第一n1 必须特判。原题 n1 时答案是 1不能直接返回 0.5。很多人背答案背成“直接 return 0.5”结果在 n1 这个用例上 WA 一次。第二确认返回类型是浮点数。LeetCode 的函数签名要求返回 double所以常量要写成 1.0、0.5不要贪方便写成 1 或者 0。Python 里影响不大但 C、Java 里类型不匹配或者隐式转换都容易引出不必要的问题。第三不要在最终代码里引入多余计算。有人会写成return n 1 ? 1.0 : (n 2 ? 0.5 : 0.5)之类虽然结果对但没有意义。记住这道题的结论是“n2 恒为 0.5”不需要再分 n 是否大于 2。一份完整的 C 实现可以是这样的class Solution { public: double nthPersonGetsNthSeat(int n) { return n 1 ? 1.0 : 0.5; } };Java 版本也几乎一样class Solution { public double nthPersonGetsNthSeat(int n) { return n 1 ? 1.0 : 0.5; } }6.3 面试考场上应该怎么讲这道题如果你在面试里遇到这道题最忌讳的就是上来直接给结论。面试官想看的不是“知道答案”而是“能不能把概率模型拆明白”。我建议按这个顺序讲先定义 F(n) 并解释状态含义然后分析第一个人的三种选择写出递推方程接着补一句“用数学归纳可以证明 n2 时 F(n)1/2”最后可以补上劫持链条的对称性直觉。这样一个回答同时覆盖了建模、推导和直观理解三个层次。如果时间紧张或者面试官只想要个解释可以只讲劫持链条除了 1 号座和 n 号座其他座位被选中都只是把劫持者换一个人整个过程只有“选到 1 号座”和“选到 n 号座”两种吸收结局而二者每一步被选中的概率都相等所以最终各占一半。这个解释虽然不如归纳法严格但足够让人快速接受 0.5 这个答案。力扣官方把这道题放在“脑筋急转弯”“数学”“动态规划”“概率与统计”这些标签下其实已经暗示了它有多种解题路径。你可以用 DP 推也可以用数学归纳证还可以用对称性解释。选择哪条路径取决于你面对的是笔试还是面试。我自己第一次刷这道题的时候完全是“O(1) 能过就过”的心态直到有次面试被追问“为什么”才发现自己虽然 AC 了却讲不清楚。后来再带人准备面试我都会要求对方先把 n3 的所有路径亲手写出来再把 1 号座和 n 号座的对称性讲明白。能做到这两步LeetCode 1227 对你来说就不再是一个“背答案的脑筋急转弯”而是一道能展示概率建模能力的漂亮题目。
LeetCode 1227飞机座位分配：从递推方程到对称性，解开0.5之谜
LeetCode 1227在题解区的画风一直很特别正经推导没多少人在写评论区最常见的回复就是“这不就是 return n 1 ? 1 : 0.5 吗”而且这样的代码确实能过。于是很多人刷完这道题留下的印象只有“又一个脑筋急转弯”。但如果你愿意认真把这个概率过程推一遍会发现它比想象中有层次得多既能练到状态抽象又能练到数学归纳还能在面试被追问时用一条非常漂亮的对称性原理解释清楚。这篇文章想做的就是把飞机座位分配问题从头到尾拆开题目到底在描述什么、递推方程怎么来、为什么结论稳定在 0.5、以及那些改一改条件就面目全非的变体。刚入门刷题的同学可以重点看前两章被面试官问烦了的人可以直接跳到第 4 章的直觉解释和第 6 章的复盘。1. 题目到底在问什么先把场景在脑子里完整跑一遍1.1 场景还原与题面拆解有 n 个乘客即将登机飞机上有 n 个座位编号从 1 到 n乘客 i 的登机牌上写的是 i 号座。乘客 1 第一个走进机舱他发现登机牌丢了于是在 n 个座位里等概率随机挑一个坐下。从乘客 2 开始每个人都执行一条固定规则如果自己的座位还空着就坐自己的如果自己的座位被前面的人占了就在剩余空位中等概率随机挑一个。乘客 n 是最后一个登机的问他能坐到自己座位 n 号位的概率是多少题目限制 n 1。当 n 1 时第一个乘客就是最后一个乘客他随机选的唯一座位正好是自己的座位概率直接就是 1。这也是整道题唯一的边界特例。复述题面的时候有一个细节值得单独拎出来说后续乘客并不是“每个人都随机选座”而是“自己的座位空着就一定坐自己的被占了才随机”。这个前提决定了整个随机过程不是简单的均匀随机抽样。很多人第一反应是“n 个座位最后一个乘客坐对概率不是 1/n 吗”恰恰就是因为忽略了后续乘客会优先吸收掉自己座位对应的随机性导致越往后局面越不像一个纯粹的均匀随机问题。1.2 三个常见的理解误区第一个误区是把最终概率当成古典概型。古典概型要求每个基本事件等概率但这个实验的完整结果不是简单从 n 个座位里抽一个。中间任何一次“被迫随机”都会改变后面的空位结构所以不能直接拿座位总数做分母。第二个误区是觉得“越靠后越倒霉最后乘客概率应该趋近 0”。这个直觉来自“座位可能被前面任意一个人占掉”但只要认真算就会发现倒数第一个乘客的成功率在 n2 时恒定是 0.5并不会随着 n 增大而衰减。第三个误区是混淆“最后一个座位提前被占的概率”和“最后一个乘客坐对的概率”。实际上这两个事件是等价的最后乘客坐对当且仅当 n 号座位在轮到他之前没有被占。所以算坐对概率本质上是在算 n 号座位在整条随机链条中“活到最后一刻”的概率。想清楚这一点后面理解 0.5 会容易很多。2. 从暴力枚举到递归方程让概率结构自己浮现2.1 状态定义F(n) 到底表示什么我设 F(n) 表示在一个规模为 n 的问题里第一个上飞机的乘客是“随机选择者”他会等概率选择任意一个座位后续乘客遵循“座位空着就坐自己的被占才随机”的规则最后一位乘客最终坐到自己座位的概率。这里的关键是这个状态只和当前问题的规模 n 有关和具体座位编号无关。初次接触递推的人会问如果中间某个座位被占了剩余空位并不是连续的编号怎么能保证还是同一个问题举个具体例子。n 5乘客 1 随机坐到了 3 号座那么乘客 2 上来时发现 2 号座空着会正常坐自己的座位。乘客 3 上来时才发现自己座位被占此时剩余空位是 1、4、5 号座。站在乘客 3 的视角看他是在 3 个空位里随机选。如果我们把 1 号座重新标记成“自己的座位”、4 号座标记成“下一个人的座位”、5 号座标记成“最后乘客的座位”就会发现这和原来问题的结构完全一致只是规模从 5 缩到了 3。这种方法叫相对编号真正影响概率的从来不是绝对座位号而是“还剩多少个位置处于同一套随机规则之下”。2.2 第一次随机选择的三种去向与递推方程第一个人选择座位时所有情况可以分成三类。第一类他选到了自己的 1 号座概率是 1/n。此时后面所有乘客都能按编号正常入座最后乘客必然坐到自己座位所以这类情况的成功概率是 1。第二类他选到了最后乘客的 n 号座概率也是 1/n。n 号座被占后最后乘客无论怎么选都不可能坐回自己的座位所以这类情况成功概率是 0。第三类他选到了某个中间座位 k其中 k 的范围是 2 到 n-1概率同样是 1/n。座位 k 被占后前面的乘客 2 到 k-1 都会正常入座轮到乘客 k 时他会成为新的“随机选择者”。正如上一节所说此时问题变成规模为 n-k1 的同构子问题所以这类情况对成功概率的贡献是 F(n-k1)。把这三类情况按全概率公式加起来F(n) (1/n) * [1 0 F(n-1) F(n-2) ... F(2)]更整洁一点可以写成F(n) (1 / n) * [1 F(2) F(3) ... F(n-1)]边界条件 F(1) 1。2.3 用记忆化搜索验证前几项这个递推方程本身就可以用代码验证。写一个简单的记忆化递归把前几项打印出来看看趋势。from functools import lru_cache lru_cache(maxsizeNone) def f(n: int) - float: if n 1: return 1.0 total 1.0 # 第一个乘客直接选1号座的情况 for j in range(2, n): total f(j) return total / n for n in range(1, 11): print(n, f(n))跑出来的结果非常整齐1 1.0 2 0.5 3 0.5 4 0.5 5 0.5 6 0.5 7 0.5 8 0.5 9 0.5 10 0.5从 n2 开始答案清一色是 0.5。这个结果看起来很“无聊”但正是这种无聊里藏着这道题最值得琢磨的地方为什么无论 n 多大概率都是一个常数这时候就该上数学归纳法了。3. 数学归纳法把 0.5 钉死边界证明比结论重要3.1 枚举前面的完整计算过程在正式归纳前先把 n2、3、4、5 的计算过程展开这样后面看归纳会更有体感。n2 时第一个乘客只有两个选择选 1 号座最后乘客成功选 2 号座最后乘客失败。所以 F(2) 1/2。n3 时第一个乘客选 1 号座概率 1/3直接成功选 3 号座概率 1/3直接失败选 2 号座概率 1/3此时乘客 2 在 1 号和 3 号之间随机成功失败各一半。所以 F(3) (1/3) * 1 (1/3) * F(2) (1 0.5) / 3 0.5。n4 时F(4) (1/4) * [1 F(2) F(3)] (1 0.5 0.5) / 4 0.5。n5 时F(5) (1/5) * [1 F(2) F(3) F(4)] (1 0.5 0.5 0.5) / 5 0.5。可以整理成一张表n计算过程F(n)1特殊情况121 / 20.53(1 0.5) / 30.54(1 0.5 0.5) / 40.55(1 0.5 0.5 0.5) / 50.53.2 归纳假设的坑为什么不能从 n1 开始很多人看到这张表会想F(1)1F(2) 开始都是 0.5那我证明“从第二项起全是 0.5”就是了。但实际操作中很容易出现一个不严谨的表述“假设 F(1) 到 F(n-1) 都为 0.5然后推出 F(n)0.5”。这个表述是错的因为 F(1) 是特例假设里不能包含它。正确做法是明确归纳命题只对 n 2 成立归纳起点是 F(2) 0.5。证明时只用 F(2) 到 F(n-1) 都等于 0.5完全不需要 F(1) 参与。这个细节看起来很小却是我见过很多人在推导时翻车的地方——结论本身没错但证明陈述不严谨面试官一追问就露怯。3.3 归纳证明全过程现在做完整归纳。基础情况已经验证 F(2) 0.5。假设对于某个 n 3所有 F(2)、F(3)、...、F(n-1) 都等于 0.5。根据递推方程F(n) (1/n) * [1 F(2) F(3) ... F(n-1)]把归纳假设代入方括号里除了开头的 1剩下 n-2 项都是 0.5F(n) (1/n) * [1 (n-2) * 0.5]继续化简F(n) (1/n) * [1 (n-2) / 2] (1/n) * [n / 2] 1/2归纳完成。也就是说从 n2 开始概率永远恒等于 0.5不存在其他隐藏状态。3.4 推导出 O(1) 结论后的代码形态递推归纳的最终结论落到代码上就是一道分叉判断class Solution: def nthPersonGetsNthSeat(self, n: int) - float: return 1.0 if n 1 else 0.5如果你只看结论这道题确实配得上“脑筋急转弯”这个标签。但推导过程的价值在于它让你有底气在面试时证明“我不是背答案我知道这个 0.5 是怎么撞出来的”。4. “劫持链条”直觉1号座位和n号座位在玩对称游戏4.1 链条如何传递从“乘客1坐错位置”说起数学证明严谨但对部分读者来说不够直观。这里分享一个我常用的“劫持链条”解释。把“某个人坐到了另一个人的座位上”看成一次劫持。乘客 1 是链条起点。如果他选了 1 号座链条当场结束所有人正常入座最后乘客成功如果他选了 n 号座链条也当场结束但最后乘客失败如果他选了中间某个座位 k乘客 k 的座位被劫持了下一个被劫持者就是乘客 k。当乘客 k 上飞机时他的座位已经没了只能随机选一个剩余空位。如果他随机选到 1 号座链条结束此时后面所有人包括被劫持过的乘客 k 自己都能找到自己的座位最后乘客成功如果他随机选到 n 号座链条结束最后乘客失败如果他随机选到另一个还没登机的人的座位那么劫持者身份继续转移。关键来了在链条没有结束的任何一个时刻1 号座和 n 号座都一定还是空着的。因为一旦这两个座位中的任何一个被选中链条就已经终止不会再有“下一次随机选择”。所以只要链条还在传递这两个座位就像两个并列的终止开关始终同时存在于下一轮随机选择的候选池里。4.2 两条吸收路径的对称性整个随机过程可以看成一条随机游走最终只有两种吸收结局某个时刻有人选了 1 号座或者有人选了 n 号座。这两种结局分别对应最后乘客成功与失败。在每个还没终止的节点上1 号座和 n 号座在候选集合里的地位完全对称它们被选中的概率始终相同而且一旦被选中就立刻决定结局。其他中间座位的选择只是把劫持者换成下一个人并不会直接决定成功或失败。既然每一步“选到 1 号座”和“选到 n 号座”的概率都相等那么整条随机链最终“先吸收到 1 号座”和“先吸收到 n 号座”的概率也相等。二者概率之和为 1所以各占 1/2。这个直觉比数学归纳法更适合在面试中口头表述。它不会替代证明但它能帮你快速建立一个“正确答案就该是 0.5”的方向感。4.3 用 n3 和 n4 的路径表验证直觉对称性听起来有点玄我们用小规模路径验证一下。n3 时把乘客 1 的所有选择和后续发展列出来乘客1的行为概率后续最后乘客成功概率贡献选1号座1/3全部正常入座1/3选3号座1/3最后乘客座位被占0选2号座1/3乘客2在1号和3号间随机1/3 * 1/2 1/6成功概率合计 1/3 1/6 1/2。再看 n4乘客1的行为概率后续最后乘客成功概率贡献选1号座1/4全部正常入座1/4选4号座1/4最后乘客座位被占0选2号座1/4变成规模3的子问题成功概率0.51/4 * 1/2 1/8选3号座1/4变成规模2的子问题成功概率0.51/4 * 1/2 1/8成功概率合计 1/4 1/8 1/8 1/2。可以看到无论中间怎么绕最终都是“1 号座先被选中”和“n 号座先被选中”在竞争双方势均力敌。5. 变体题大赏条件稍微改一改题目还成立吗5.1 变体一第一个乘客坐到自己座位的概率这个问题可以作为热身第一个乘客在 n 个座位里均匀随机选坐到自己座位的概率当然是 1/n。它和原题放在一起看会产生一个非常反直觉的对比第一个乘客坐对的概率只有 1/n而离他最远的最后乘客反而有 0.5 的概率坐对。原题里最吃亏的反而是最初制造随机性的那个人因为他的座位没有被任何一个“正常乘客”保护纯粹是被自己随机掉的。这个变体经常被面试官当作追问的第一个台阶用来确认你是否真的理解随机链条的位置差异。5.2 变体二如果随机者不是第一个而是第 m 个乘客把题目改成前 m-1 个乘客都正常按规则入座第 m 个乘客才是丢登机牌的人他会在剩余空位中等概率随机选一个问最后乘客坐对的概率。前 m-1 个乘客都会坐自己的座位不会占用别人的位置所以轮到第 m 个乘客时1 到 m-1 号座位已经坐满剩余空位是 m、m1、...、n一共 n-m1 个。第 m 个乘客随机选完以后问题就等价于一个规模为 n-m1 的原版问题。直接套结论如果 n-m1 1也就是 m n答案就是 1因为最后一个乘客自己就是随机者他面前只剩自己的座位如果 n-m1 2答案就是 0.5。这个变体说明一个问题原题里的“随机者”和“最后乘客”的相对位置并不重要重要的是从随机者开始后面还剩多少个座位处于同构规则之下。5.3 变体三如果第一个乘客有一定概率坐对答案怎么变这是我在面试复盘中最喜欢抛给对方的一个扩展。假设第一个乘客有概率 p 会老老实实坐自己的 1 号座只有 1-p 的概率会随机乱坐那么最后乘客坐对的概率是多少当第一个乘客坐对时概率 p后面所有人都正常入座最后乘客成功当第一个乘客乱坐时概率 1-p整个问题退化成原题最后乘客成功概率是 0.5。因此P p * 1 (1-p) * 0.5 0.5 0.5pp 0 时就是原题答案 0.5p 1 时全员归位答案 1p 0.5 时答案就是 0.75。这个公式非常干净而且能看出原题 0.5 其实是 p0 的特例。5.4 变体四一道留给你自己推的思考题有个讨论度很高的改法如果前两位乘客都没有看座位号无论自己的座位空不空都在剩余空位里随机选问最后乘客坐对的概率。这道题比原题难不少因为它改变了“被占才随机”这个关键规则。定义状态时必须多引入一个维度还剩多少个“正常被动乘客”、还剩多少个“随机主动乘客”然后做二维递推。n3 时你可以手算出答案不是 0.5而是 1/3。这类思考题很适合用来检验自己是否真的理解了原题的结构。原题之所以能递归简化正是因为从第二个乘客开始几乎所有人都被“自己的座位空着就坐自己的”这条规则保护住随机性很难扩散而一旦有多名主动随机者保护层被打破概率结构会立刻变得复杂。6. 提交代码与面试复盘三个容易翻车的细节6.1 看似能用的 DP 方案为什么过不了看到递推方程的第一反应通常是开一个长度为 n 的 DP 数组从小到大算一遍。这个思路没有错但 LeetCode 1227 的 n 上限是 10^9至少是远超 DP 数组可接受范围的量级开 O(n) 数组在内存上完全不可行递归写法在数据量大时也必然爆栈。所以这道题真正的工程解必须落在 O(1) 时间和 O(1) 空间上。数学结论在这里不是“投机取巧”而是经过推导后唯一合理的实现方式。6.2 返回值类型、n1 边界、O(1) 编码三个细节最终提交代码很短但越短的代码越容易在细节上翻车。第一n1 必须特判。原题 n1 时答案是 1不能直接返回 0.5。很多人背答案背成“直接 return 0.5”结果在 n1 这个用例上 WA 一次。第二确认返回类型是浮点数。LeetCode 的函数签名要求返回 double所以常量要写成 1.0、0.5不要贪方便写成 1 或者 0。Python 里影响不大但 C、Java 里类型不匹配或者隐式转换都容易引出不必要的问题。第三不要在最终代码里引入多余计算。有人会写成return n 1 ? 1.0 : (n 2 ? 0.5 : 0.5)之类虽然结果对但没有意义。记住这道题的结论是“n2 恒为 0.5”不需要再分 n 是否大于 2。一份完整的 C 实现可以是这样的class Solution { public: double nthPersonGetsNthSeat(int n) { return n 1 ? 1.0 : 0.5; } };Java 版本也几乎一样class Solution { public double nthPersonGetsNthSeat(int n) { return n 1 ? 1.0 : 0.5; } }6.3 面试考场上应该怎么讲这道题如果你在面试里遇到这道题最忌讳的就是上来直接给结论。面试官想看的不是“知道答案”而是“能不能把概率模型拆明白”。我建议按这个顺序讲先定义 F(n) 并解释状态含义然后分析第一个人的三种选择写出递推方程接着补一句“用数学归纳可以证明 n2 时 F(n)1/2”最后可以补上劫持链条的对称性直觉。这样一个回答同时覆盖了建模、推导和直观理解三个层次。如果时间紧张或者面试官只想要个解释可以只讲劫持链条除了 1 号座和 n 号座其他座位被选中都只是把劫持者换一个人整个过程只有“选到 1 号座”和“选到 n 号座”两种吸收结局而二者每一步被选中的概率都相等所以最终各占一半。这个解释虽然不如归纳法严格但足够让人快速接受 0.5 这个答案。力扣官方把这道题放在“脑筋急转弯”“数学”“动态规划”“概率与统计”这些标签下其实已经暗示了它有多种解题路径。你可以用 DP 推也可以用数学归纳证还可以用对称性解释。选择哪条路径取决于你面对的是笔试还是面试。我自己第一次刷这道题的时候完全是“O(1) 能过就过”的心态直到有次面试被追问“为什么”才发现自己虽然 AC 了却讲不清楚。后来再带人准备面试我都会要求对方先把 n3 的所有路径亲手写出来再把 1 号座和 n 号座的对称性讲明白。能做到这两步LeetCode 1227 对你来说就不再是一个“背答案的脑筋急转弯”而是一道能展示概率建模能力的漂亮题目。