[leetcode] 1227. Airplane Seat Assignment Probability

[leetcode] 1227. Airplane Seat Assignment Probability

Description

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:

Take their own seat if it is still available,Pick other seats randomly when they find their seat occupied

What is the probability that the n-th person can get his own seat?

Example 1:

Input: n = 1Output: 1.00000Explanation: The first person can only get the first seat.

Example 2:

Input: n = 2Output: 0.50000Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Constraints:

1 <= n <= 10^5

分析

题目的意思是：求出第n个人能够正确坐到第n个座位的概率。这是一道数学推论的问题： 对于n1的情况，概率p=1 对于n2的情况，概率p=1/20+1/21=1/2 对于n==3的情况，概率p=1/31+1/3(1/2+0)+1/30=1/2 可以推出公式： dp[n]=1/n+1/ndp[n-1]+1/ndp[n-2]+…+1/n0 又因为：dp[i]=1/2 dp[n]=1/2 对于n=3情况的解释：

如果第一个人占了自己的位置，因为题目说，从第二个人开始，如果发现自己座位是空的，就会乖乖坐自己的作为，因此这种情况下第n个人肯定可以坐到自己的座位上，这种概率发生的可能性为1/3如果第一个人占了第二个人的位置（1/3），因为题目说，从第二个人开始，如果发现自己的座位被占用了，就会继续随机挑选一个座位，这种情况下：

第二个人如果占了剩下座位的原本第一个人的座位，那么第三个人就能正确做下如果第二个人占了剩下作为的第三个人的座位，那么第三个人就没办法坐下来了因此整个第二大点最后一个人坐到自己座位这种事件的发生概率是1/3 * 1/2 + 1/3 * 0

如果第一个人占了第三个人的座位，那么第三个人肯定没办法坐到自己的作为了，这时候第三个人坐到自己座位的概率为0上述三种大情况，我们可以算出来最后的概率 P(3) = 1/3 * 1 + 1/3 * (1/2 + 0) + 1/3 * 0 = 1/2

代码

class Solution: def nthPersonGetsNthSeat(self, n: int) -> float: return 1 if n==1 else 0.5

参考文献

​​[LeetCode] 数学推论​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。