feat: #1227

lucifer · lucifer · commit 980d576f9190 · 2020-01-19T18:32:04.000+08:00
diff --git a/README.md b/README.md
@@ -233,7 +233,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [1131.maximum-of-absolute-value-expression](./problems/1131.maximum-of-absolute-value-expression.md) 🆕
 - [1186.maximum-subarray-sum-with-one-deletion](./problems/1186.maximum-subarray-sum-with-one-deletion.md) 🆕
 - [1218.longest-arithmetic-subsequence-of-given-difference](./problems/1218.longest-arithmetic-subsequence-of-given-difference.md) 🆕
-
+- [1227.airplane-seat-assignment-probability](./problems/1227.airplane-seat-assignment-probability.md) 🆕
 - [1261.find-elements-in-a-contaminated-binary-tree](./problems/1261.find-elements-in-a-contaminated-binary-tree.md) 🆕
 - [1262.greatest-sum-divisible-by-three](./problems/1262.greatest-sum-divisible-by-three.md) 🆕
 - [1297.maximum-number-of-occurrences-of-a-substring](./problems/1297.maximum-number-of-occurrences-of-a-substring.md) 🆕
diff --git a/problems/1227.airplane-seat-assignment-probability.md b/problems/1227.airplane-seat-assignment-probability.md
@@ -0,0 +1,249 @@
+## 题目地址（1227. 飞机座位分配概率）
+
+https://leetcode-cn.com/problems/airplane-seat-assignment-probability/description/
+
+## 题目描述
+
+```
+
+有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
+
+剩下的乘客将会：
+
+如果他们自己的座位还空着，就坐到自己的座位上，
+
+当他们自己的座位被占用时，随机选择其他座位
+第 n 位乘客坐在自己的座位上的概率是多少？
+
+ 
+
+示例 1：
+
+输入：n = 1
+输出：1.00000
+解释：第一个人只会坐在自己的位置上。
+示例 2：
+
+输入: n = 2
+输出: 0.50000
+解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
+ 
+
+提示：
+
+1 <= n <= 10^5
+
+
+```
+
+## 暴力递归
+
+这是一道 LeetCode 为数不多的概率题，我们来看下。
+
+### 思路
+
+我们定义原问题为 f(n)。对于第一个人来说，他有 n 中选择，就是分别选择 n 个座位中的一个。由于选择每个位置的概率是相同的，那么选择每个位置的概率应该都是 1 / n。
+
+我们分三种情况来讨论：
+
+- 如果第一个人选择了第一个人的位置（也就是选择了自己的位置），那么剩下的人按照票上的座位做就好了，这种情况第 n 个人一定能做到自己的位置
+- 如果第一个人选择了第 n 个人的位置，那么第 n 个人肯定坐不到自己的位置。
+- 如果第一个人选择了第 i (1 < i < n)个人的位置，那么第 i 个人就相当于变成了“票丢的人”，此时问题转化为 f(n - i + 1)。
+
+此时的问题转化关系如图：
+
+![](https://tva1.sinaimg.cn/large/006tNbRwly1gb12n0omuuj31bc0ju405.jpg)
+（红色表示票丢的人）
+
+整个过程分析：
+
+![](https://tva1.sinaimg.cn/large/006tNbRwly1gb12nhestaj318u0bg76f.jpg)
+
+### 代码
+
+代码支持 Python3:
+
+Python3 Code:
+
+```python
+class Solution:
+    def nthPersonGetsNthSeat(self, n: int) -> float:
+        if n == 1:
+            return 1
+        if n == 2:
+            return 0.5
+        res = 1 / n
+        for i in range(2, n):
+            res += self.nthPersonGetsNthSeat(n - i + 1) * 1 / n
+        return res
+```
+
+上述代码会栈溢出。
+
+## 暴力递归 + hashtable
+
+### 思路
+
+我们考虑使用记忆化递归来减少重复计算，虽然这种做法可以减少运行时间，但是对减少递归深度没有帮助。还是会栈溢出。
+
+### 代码
+
+代码支持 Python3:
+
+Python3 Code:
+
+```python
+class Solution:
+    seen = {}
+
+    def nthPersonGetsNthSeat(self, n: int) -> float:
+        if n == 1:
+            return 1
+        if n == 2:
+            return 0.5
+        if n in self.seen:
+            return self.seen[n]
+        res = 1 / n
+        for i in range(2, n):
+            res += self.nthPersonGetsNthSeat(n - i + 1) * 1 / n
+        self.seen[n] = res
+        return res
+```
+
+## 动态规划
+
+### 思路
+
+上面做法会栈溢出。其实我们根本不需要运行就应该能判断出栈溢出，题目已经给了数据规模是 1 <= n <= 10 \*\* 5。 这个量级不管什么语言，除非使用尾递归，不然一般都会栈溢出，具体栈深度大家可以查阅相关资料。
+
+既然是栈溢出，那么我们考虑使用迭代来完成。 很容易想到使用动态规划来完成。其实递归都写出来，写一个朴素版的动态规划也难不到哪去，毕竟动态规划就是记录子问题，并建立子问题之间映射而已，这和递归并无本质区别。
+
+### 代码
+
+代码支持 Python3:
+
+Python3 Code:
+
+```python
+class Solution:
+    def nthPersonGetsNthSeat(self, n: int) -> float:
+        if n == 1:
+            return 1
+        if n == 2:
+            return 0.5
+
+        dp = [1, .5] * n
+
+        for i in range(2, n):
+            dp[i] = 1 / n
+            for j in range(2, i):
+                dp[i] += dp[i - j + 1] * 1 / n
+        return dp[-1]
+```
+
+这种思路的代码超时了，并且仅仅执行了 35/100 testcase 就超时了。
+
+## 数学分析
+
+### 思路
+
+我们还需要进一步优化时间复杂度，我们需要思考是否可以在线形的时间内完成。
+
+我们继续前面的思路进行分析, 不难得出，我们不妨称其为等式 1：
+
+```
+f(n)
+= 1/n + 0 + 1/n * (f(n-1) + f(n-2) + ... + f(2))
+= 1/n * (f(n-1) + f(n-2) + ... + f(2) + 1)
+= 1/n * (f(n-1) + f(n-2) + ... + f(2) + f(1))
+```
+
+似乎更复杂了？没关系，我们继续往下看，我们看下 f(n - 1)，我们不妨称其为等式 2。
+
+```
+f(n-1) = 1/(n-1) * (f(n-2) + f(n-3) + ... + f(1))
+```
+
+我们将等式 1 和等式 2 两边分别同时乘以 n 和 n - 1
+
+```
+n * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1)
+(n-1) * f(n-1) = f(n-2) + f(n-3) + ... + f(1)
+```
+
+我们将两者相减：
+
+```
+n * f(n) - (n-1)*f(n-1) = f(n-1)
+```
+
+我们继续将 (n-1)\*f(n-1) 移到等式右边，得到：
+
+```
+n * f(n) = n * f(n-1)
+```
+
+也就是说:
+
+```
+f(n) = f(n - 1)
+```
+
+当然前提是 n 大于 2。
+
+既然如此，我们就可以减少一层循环， 我们用这个思路来优化一下上面的 dp 解法。这种解法终于可以 AC 了。
+
+### 代码
+
+代码支持 Python3:
+
+Python3 Code:
+
+```python
+class Solution:
+    def nthPersonGetsNthSeat(self, n: int) -> float:
+        if n == 1:
+            return 1
+        if n == 2:
+            return 0.5
+
+        dp = [1, .5] * n
+
+        for i in range(2, n):
+            dp[i] = 1/n+(n-2)/n * dp[n-1]
+        return dp[-1]
+```
+
+## 优化数学分析
+
+### 思路
+
+上面我们通过数学分析，得出了当 n 大于 2 时：
+
+```
+f(n) = f(n - 1)
+```
+
+那么是不是意味着我们随便求出一个 n 就好了？ 比如我们求出 n = 2 的时候的值，是不是就知道 n 为任意数的值了。 我们不难想出 n = 2 时候，概率是 0.5，因此只要 n 大于 1 就是 0.5 概率，否则就是 1 概率。
+
+### 代码
+
+代码支持 Python3:
+
+Python3 Code:
+
+```python
+class Solution:
+    def nthPersonGetsNthSeat(self, n: int) -> float:
+        return 1 if n == 1 else .5
+
+```
+
+## 关键点
+
+- 概率分析
+- 数学推导
+- 动态规划
+- 递归 + mapper
+- 栈限制大小
+- 尾递归
