题目地址(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)。
此时的问题转化关系如图:
(红色表示票丢的人)
整个过程分析:
代码
代码支持 Python3:
Python3 Code:
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:
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:
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:
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:
class Solution: def nthPersonGetsNthSeat(self, n: int) -> float: return 1 if n == 1 else .5
关键点
- 概率分析
- 数学推导
- 动态规划
- 递归 + mapper
- 栈限制大小
- 尾递归
我有一个游戏循环class Game extends Runnable { private boolean running = false; @Override public void run() { running = true; while(running) { //... } } } 我在想,在此之前(在游戏循环中)直接分配给变量或带有if的控件是否更…
LeetCode题解堆排序和快速排序堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…
LeetCode题解砝码的最小数量假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…
LeetCode题解93. 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…