算法编程题-区间列表的交集、飞机座位分配概率
摘要：本文将介绍两道LeetCode原题，一道是区间列表交集，另外一道则是飞机座位分配概率，实质上是一道常考的智力题。本文将给出基于golang语言的实现，代码实现通过了所有测试用例，最后给出相关的复杂度分析。
关键词：LeetCode，golang，面试，智力题
区间列表的交集
原题描述
给定两个区间列表，每一个区间用[left, right]来描述，表示所有范围在left <= x <= right的x的集合，每一个区间列表内部两两之间不交叉，且按照从小到大的顺序排列，现在要求出这两个区间列表的交叉集合。
思路简述
整体实现思路类似于有序数组合并，维护两个指针指向两个区间列表的某个区间，首先判断两个区间是否有交叉，交叉只有两种情况，A列表的区间整体在B列表的区间的前面或者后面，那么此时将整体在后面的区间所在列表的指针往后移一位。否则就是有交叉，且交叉区域[left, right]， 其中left等于两个区间左端点的最大值，right等于两个区间右端点的最小值，然后将右端点小的区间所在的列表的指针往后移一位。
代码实现
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
res := make([][]int, 0)
i := 0
j := 0
m := len(firstList)
n := len(secondList)
for i < m && j < n {
if firstList[i][1] < secondList[j][0] {
i++
} else if firstList[i][0] > secondList[j][1] {
j++
} else { // 有交叉
res = append(res, []int{max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])})
if firstList[i][1] >= secondList[j][1] {
j++
} else {
i++
}
}
}
return res
}
LeetCode运行截图如下所示
复杂度分析
- 时间复杂度： O ( m + n ) O(m+n) O(m+n)，其中m和n分别为两个区间列表的长度
- 空间复杂度： O ( m + n ) O(m+n) O(m+n)
飞机座位分配概率
原题描述
在飞机上有n个座位，现在有n个乘客按照顺序上飞机，但是第一个乘客的票丢了或者他疯了，会随机找一个位置坐下，后面的乘客都是正常人，如果自己的座位是空的，就会做自己的位置，否则也会随机找一个位置坐下，现在要求出最后一个人能做到自己的位置上的概率。
思路简述
非常经典的智力题，怎么去想这一个问题？可以这样去思考，第一个人他随机选择位置有三种情况，第一种情况，他选择了第一个座位，那么后面的所有人都能做到自己的位置上，这种情况下最后一个人做到自己位置上的概率为
P
1
=
1
n
P_1=\frac{1}{n}
P1=n1；第二种情况，他选择了第2个位置到第n-1个位置中的一个，假设为m，则从第2个人到第m-1个人都能正确选择自己的位置。到了第m个人，由于其位置被占了，此时可以认为第一个位置就是他的位置，因为只要他做了第一个位置，后面所有人都能正常做，所以相当于这变成了一个子问题，在n-m+1个座位下的子问题，考虑所有的m，这种情况下最后一个人成功做的概率如下：
p
2
=
1
n
∑
m
=
2
m
=
n
−
1
f
(
n
−
m
+
1
)
p_2=\frac{1}{n}\sum_{m=2}^{m=n-1}f(n-m+1)
p2=n1m=2∑m=n−1f(n−m+1)
最后来看第三种情况，第一个人随机做到了最后一个位置，显然最后一个人无法做到自己的位置了，所以
p
3
=
0
p_3=0
p3=0。
综上所述，最后一个人能做到自己位置的概率为
p
=
p
1
+
p
2
=
1
n
+
1
n
∑
m
=
2
m
=
n
−
1
f
(
n
−
m
+
1
)
=
1
n
∑
i
=
1
n
−
1
f
(
i
)
p=p_1+p_2 = \frac{1}{n} + \frac{1}{n}\sum_{m=2}^{m=n-1}f(n-m+1)= \frac{1}{n}\sum_{i=1}^{n-1}f(i)
p=p1+p2=n1+n1m=2∑m=n−1f(n−m+1)=n1i=1∑n−1f(i)
可以从直观的感觉上讲，上述概率就是0.5，因为第二种情况下是变成了一个子问题，而第一种情况和第三种情况是等可能的。
或者使用数学归纳法对这个问题进行证明，如下：
$$
∀
i
∈
[
2
,
n
−
1
]
，都有
f
(
i
)
=
0.5
\forall i \in [2, n-1]，都有f(i)=0.5\atop
∀i∈[2,n−1]，都有f(i)=0.5
∴
\therefore
∴
f
(
n
)
=
1
n
∑
i
=
1
n
−
1
f
(
i
)
=
1
n
(
1
+
1
2
(
n
−
2
)
)
=
1
2
f(n)=\frac{1}{n}\sum_{i=1}^{n-1}f(i)=\frac{1}{n} (1+\frac{1}{2}(n-2))=\frac{1}{2}
f(n)=n1∑i=1n−1f(i)=n1(1+21(n−2))=21
$$
或者上述的过程可以用程序去实现，来进一步证明。
代码实现
func nthPersonGetsNthSeat(n int) float64 {
if n == 1 {
return 1
}
return 0.5
}
以上的代码是已知了结论所以直接输出答案即可，或者进行一定的推导，如下：
func nthPersonGetsNthSeat(n int) float64 {
if n == 1 {
return 1
}
if n == 2 {
return 0.5
}
ps := make([]float64, n)
ps[0] = 1.0
ps[1] = 0.5
sum := 1.5
for i := 2; i < n; i++{
ps[i] = 1.0 / float64(i + 1) * sum
sum += ps[i]
}
return ps[n - 1]
}
LeetCode运行截图如下：
复杂度分析
- 时间空间度：直接公式法 O ( 1 ) O(1) O(1)，推导法 O ( n ) O(n) O(n)
- 空间复杂度：直接公式法 O ( 1 ) O(1) O(1)，推导法 O ( n ) O(n) O(n)