企业官网建设流程全解析

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”。这个直觉来自“座位可能被前面任意一个人占掉”，但只要认真算就会发现，倒数第一个乘客的成功率在 n>=2 时恒定是 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-k+1 的同构子问题，所以这类情况对成功概率的贡献是 F(n-k+1)。

把这三类情况按全概率公式加起来：

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(maxsize=None) 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

从 n=2 开始，答案清一色是 0.5。这个结果看起来很“无聊”，但正是这种无聊里藏着这道题最值得琢磨的地方：为什么无论 n 多大，概率都是一个常数？这时候就该上数学归纳法了。

3. 数学归纳法把 0.5 钉死：边界证明比结论重要

3.1 枚举前面的完整计算过程

在正式归纳前，先把 n=2、3、4、5 的计算过程展开，这样后面看归纳会更有体感。

n=2 时，第一个乘客只有两个选择：选 1 号座，最后乘客成功；选 2 号座，最后乘客失败。所以 F(2) = 1/2。

n=3 时，第一个乘客选 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。

n=4 时，F(4) = (1/4) * [1 + F(2) + F(3)] = (1 + 0.5 + 0.5) / 4 = 0.5。

n=5 时，F(5) = (1/5) * [1 + F(2) + F(3) + F(4)] = (1 + 0.5 + 0.5 + 0.5) / 5 = 0.5。

可以整理成一张表：

3.2 归纳假设的坑：为什么不能从 n=1 开始

很多人看到这张表会想：F(1)=1，F(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.5：

F(n) = (1/n) * [1 + (n-2) * 0.5]

继续化简：

F(n) = (1/n) * [1 + (n-2) / 2] = (1/n) * [n / 2] = 1/2

归纳完成。也就是说，从 n=2 开始，概率永远恒等于 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 用 n=3 和 n=4 的路径表验证直觉

对称性听起来有点玄，我们用小规模路径验证一下。

n=3 时，把乘客 1 的所有选择和后续发展列出来：

成功概率合计 1/3 + 1/6 = 1/2。

再看 n=4：

成功概率合计 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、m+1、...、n，一共 n-m+1 个。第 m 个乘客随机选完以后，问题就等价于一个规模为 n-m+1 的原版问题。

直接套结论：如果 n-m+1 = 1，也就是 m = n，答案就是 1，因为最后一个乘客自己就是随机者，他面前只剩自己的座位；如果 n-m+1 >= 2，答案就是 0.5。

这个变体说明一个问题：原题里的“随机者”和“最后乘客”的相对位置并不重要，重要的是从随机者开始，后面还剩多少个座位处于同构规则之下。

5.3 变体三：如果第一个乘客有一定概率坐对，答案怎么变

这是我在面试复盘中最喜欢抛给对方的一个扩展。假设第一个乘客有概率 p 会老老实实坐自己的 1 号座，只有 1-p 的概率会随机乱坐，那么最后乘客坐对的概率是多少？

当第一个乘客坐对时，概率 p，后面所有人都正常入座，最后乘客成功；当第一个乘客乱坐时，概率 1-p，整个问题退化成原题，最后乘客成功概率是 0.5。因此：

P = p * 1 + (1-p) * 0.5 = 0.5 + 0.5p

p = 0 时就是原题，答案 0.5；p = 1 时全员归位，答案 1；p = 0.5 时，答案就是 0.75。这个公式非常干净，而且能看出原题 0.5 其实是 p=0 的特例。

5.4 变体四：一道留给你自己推的思考题

有个讨论度很高的改法：如果前两位乘客都没有看座位号，无论自己的座位空不空都在剩余空位里随机选，问最后乘客坐对的概率。

这道题比原题难不少，因为它改变了“被占才随机”这个关键规则。定义状态时必须多引入一个维度：还剩多少个“正常被动乘客”、还剩多少个“随机主动乘客”，然后做二维递推。n=3 时你可以手算出答案不是 0.5，而是 1/3。

这类思考题很适合用来检验自己是否真的理解了原题的结构。原题之所以能递归简化，正是因为从第二个乘客开始，几乎所有人都被“自己的座位空着就坐自己的”这条规则保护住，随机性很难扩散；而一旦有多名主动随机者，保护层被打破，概率结构会立刻变得复杂。

6. 提交代码与面试复盘：三个容易翻车的细节

6.1 看似能用的 DP 方案为什么过不了

看到递推方程的第一反应通常是开一个长度为 n 的 DP 数组，从小到大算一遍。这个思路没有错，但 LeetCode 1227 的 n 上限是 10^9（至少是远超 DP 数组可接受范围的量级），开 O(n) 数组在内存上完全不可行，递归写法在数据量大时也必然爆栈。

所以这道题真正的工程解必须落在 O(1) 时间和 O(1) 空间上。数学结论在这里不是“投机取巧”，而是经过推导后唯一合理的实现方式。

6.2 返回值类型、n=1 边界、O(1) 编码三个细节

最终提交代码很短，但越短的代码越容易在细节上翻车。

第一，n=1 必须特判。原题 n=1 时答案是 1，不能直接返回 0.5。很多人背答案背成“直接 return 0.5”，结果在 n=1 这个用例上 WA 一次。

第二，确认返回类型是浮点数。LeetCode 的函数签名要求返回 double，所以常量要写成 1.0、0.5，不要贪方便写成 1 或者 0。Python 里影响不大，但 C++、Java 里类型不匹配或者隐式转换都容易引出不必要的问题。

第三，不要在最终代码里引入多余计算。有人会写成return n == 1 ? 1.0 : (n == 2 ? 0.5 : 0.5)之类，虽然结果对，但没有意义。记住这道题的结论是“n>=2 恒为 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) 并解释状态含义，然后分析第一个人的三种选择，写出递推方程，接着补一句“用数学归纳可以证明 n>=2 时 F(n)=1/2”，最后可以补上劫持链条的对称性直觉。这样一个回答同时覆盖了建模、推导和直观理解三个层次。

如果时间紧张或者面试官只想要个解释，可以只讲劫持链条：除了 1 号座和 n 号座，其他座位被选中都只是把劫持者换一个人，整个过程只有“选到 1 号座”和“选到 n 号座”两种吸收结局，而二者每一步被选中的概率都相等，所以最终各占一半。这个解释虽然不如归纳法严格，但足够让人快速接受 0.5 这个答案。

力扣官方把这道题放在“脑筋急转弯”“数学”“动态规划”“概率与统计”这些标签下，其实已经暗示了它有多种解题路径。你可以用 DP 推，也可以用数学归纳证，还可以用对称性解释。选择哪条路径取决于你面对的是笔试还是面试。

我自己第一次刷这道题的时候，完全是“O(1) 能过就过”的心态，直到有次面试被追问“为什么”，才发现自己虽然 AC 了却讲不清楚。后来再带人准备面试，我都会要求对方先把 n=3 的所有路径亲手写出来，再把 1 号座和 n 号座的对称性讲明白。能做到这两步，LeetCode 1227 对你来说就不再是一个“背答案的脑筋急转弯”，而是一道能展示概率建模能力的漂亮题目。