跳转至

LeetCode: 1227. 飞机座位分配概率

1、题目描述

n 位乘客即将登机,飞机正好有 n 个座位。第一位乘客的票丢了,他随便选了一个座位坐下。

剩下的乘客将会:

如果他们自己的座位还空着,就坐到自己的座位上,

当他们自己的座位被占用时,随机选择其他座位 第 n 位乘客坐在自己的座位上的概率是多少?

示例 1:

输入:n = 1
输出:1.00000
解释:第一个人只会坐在自己的位置上。

示例 2:

输入: n = 2
输出: 0.50000
解释:在第一个人选好座位坐下后,第二个人坐在自己的座位上的概率是 0.5。

提示:

  • 1 <= n <= 10^5

2、解题思路

  • 找出规律
dp[i]表示 第i个人坐位置i的概率
  • 人数:1
只有一个座,因此做到自己座位概率是1
  • 人数:2
dp[1] = 1/2
dp[2] = 1/2
  • 人数:3
dp[1] = 1/3
dp[2] = 1/6
dp[3] = 1/2
dp[n] = 1-sum(dp[:i])

当n大于1,恒等于0.5

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