1227. Airplane Seat Assignment Probability

Oct 11, 2020

今天的题目是1227. Airplane Seat Assignment Probability

比较简单的题目,我的思路大概是这样的。

先假设f(n)为有 n 个人时,第 n 个人坐到自己位置的概率。

首先,第 1 个人随机选位置的时候,可能有三种情况:

  1. 选到了自己的位置,那么后面就不会有人发现自己座位被做了,此时第 n 个人一定会坐到自己的位置。
  2. 选到了第 n 个人的位置,这时第 n 个人就会坐到第 1 个人的位置上。
  3. 选到了第 k 个人位置,这时,第 k 个人前面的(除了第一个人)都坐到了自己的位置,直到第 k 个人时,问题转化求解f(n-k+1)

因此,我们可以列出下面的递推公式:

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \
\frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) &, & n!=1 \end{aligned} \right. $$

对第二个公式进一步化简得到:

$$ \begin{aligned} f(n) = & \frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) \
= & \frac 1 n (f(1) + \sum_{k=2}^{n-1}f(k)) \
= & \frac{1}{n} \sum_{k=1}^{n-1}f(k) \end{aligned} $$

因此递推公式可以写成:

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \
\frac{1}{n} \sum_{k=1}^{n-1}f(k) &, & n!=1 \end{aligned} \right. $$

根据递推公式可以写出如下代码:

double nthPersonGetsNthSeat(int n) {
	double sum = 1.0;
	for(int k = 2;k <= n;k++) {
		res = sum / k;
		sum += res;
	}
	return res;
}

我们将一些值代入到公式中可以发现这样一个事情:

$$ \begin{aligned} f(2) & = \frac{1}{2} f(1) \
f(3) & = \frac{1}{3} (f(1) + f(2)) = \frac{1}{2} f(1) \
… & \
f(n) & = \frac{1}{n} (f(1) + f(2) + … + f(n-1) ) \
& = \frac{1}{n} (f(1) + \frac{1}{2}f(1) + … + \frac{1}{2}f(1)) \
& = \frac{1}{n} (f(1) + \frac{n-2}{2}f(1)) \
& = \frac{1}{2} f(1) \end{aligned} $$

因此递推公式进一步简化成:

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \
\frac{1}{2} f(1) &, & n!=1 \end{aligned} \right. $$

因此,代码如下:

double nthPersonGetsNthSeat(int n) {
	return n > 1 ? 0.5 : 1.0;
}
LeetCodeBrainteaserMathDynamic ProgrammingLeetCode

116. Populating Next Right Pointers in Each Node

1019. Next Greater Node In Linked List

comments powered by Disqus