Java实现 LeetCode 1227 飞机座位分配概率

1227. 飞机座位分配概率

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

剩下的乘客将会：

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

当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

输入：n = 1

输出：1.00000

解释：第一个人只会坐在自己的位置上。

示例 2：

输入: n = 2

输出: 0.50000

解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

提示：

1 <= n <= 10^5

PS：

	  分析：(头和尾属于特殊乘客我们单独分析)

  如果 n = 5，中间的 3 个人至少有 2 个人会坐在自己的座位上

  如果 n = 9，中间的 7 个人至少有 6 个人会坐在自己的座位上

  因为第一个丢票的人，最多只能占据中间有票的一个座位

  所以在 3 以上的情况无论 n = ?，都简化为了 n = 3，求下面三种情况的概率之和

  1.如果第一个人坐在自己的座位上

    - 第一个人坐在自己的座位上的概率为 1/3，接着第二个人的座位是空的，这时候，第二个人会坐到自己的座位上，所以最后一个乘客坐到自己的座位的概率是 1/1，这种情况的概率是 1/3 * 1/1

  2.如果第一个人坐在第二个有票乘客的座位上

    - 第一个人坐在第二个乘客的座位上的概率为 1/3，这时候第二个乘客的座位是空的，他会随便坐，他没有坐到最后一个乘客座位的概率是 1/2，这时候，最后一个乘客只有一个自己的座位了，可以坐上，这种情况的概率是 1/3 * 1/2

  3.如果第一个人坐在第三个乘客的座位上

    - 第一个人坐在第三个有票乘客的座位上的概率为 1/3，这时候可以确定最后一个乘客一定不会坐到自己的座位上了，这种情况的概率是 1/3 * 0

  将以上情况的概率相加即为 n = 3 以上情况的答案：

  1/3 * 1/1 + 1/3 * 1/2 + 1/3 * 0 = 0.5

class Solution {

     public double nthPersonGetsNthSeat(int n) {

         return n == 1 ? 1:0.5;

    }

}

巴特西

Java实现 LeetCode 1227 飞机座位分配概率

1227. 飞机座位分配概率

最新文章

热门文章