运维开发网

一行代码就可以通过 LeetCode?来看下我是怎么做到的!

运维开发网 https://www.qedev.com 2021-01-12 08:24 出处:51CTO 作者:mb5ff981d806017
1227. 飞机座位分配概率这是一道 LeetCode 为数不多的概率题,我们来看下。原题地址:https://leetcode-cn.com/problems/airplane-seat-assignment-probability/description/题目描述暴力递归思路我们定义原问题为 f(n)。对于第一个人来说,他有 n 中选择,就是分别选择 n 个座位中的一个。由于选择每个位置的概率

1227. 飞机座位分配概率

这是一道 LeetCode 为数不多的概率题,我们来看下。原题地址:https://leetcode-cn.com/problems/airplane-seat-assignment-probability/description/

题目描述

一行代码就可以通过 LeetCode?来看下我是怎么做到的!

暴力递归

思路

我们定义原问题为 f(n)。对于第一个人来说,他有 n 中选择,就是分别选择 n 个座位中的一个。由于选择每个位置的概率是相同的,那么选择每个位置的概率应该都是 1 / n。

我们分三种情况来讨论:

  • 如果第一个人选择了第一个人的位置(也就是选择了自己的位置),那么剩下的人按照票上的座位做就好了,这种情况第 n 个人一定能做到自己的位置
  • 如果第一个人选择了第 n 个人的位置,那么第 n 个人肯定坐不到自己的位置。
  • 如果第一个人选择了第 i (1 < i < n)个人的位置,那么第 i 个人就相当于变成了“票丢的人”,此时问题转化为 f(n - i + 1)。

此时的问题转化关系如图:

(红色表示票丢的人)

整个过程分析:

代码

代码支持 Python3:

Python3 Code:

上述代码会栈溢出。

暴力递归 + hashtable

思路

我们考虑使用记忆化递归来减少重复计算,虽然这种做法可以减少运行时间,但是对减少递归深度没有帮助。还是会栈溢出。

代码

代码支持 Python3:

Python3 Code:

动态规划

思路

上面做法会栈溢出。其实我们根本不需要运行就应该能判断出栈溢出,题目已经给了数据规模是 1 <= n <= 10 ** 5。这个量级不管什么语言,除非使用尾递归,不然一般都会栈溢出,具体栈深度大家可以查阅相关资料。

既然是栈溢出,那么我们考虑使用迭代来完成。很容易想到使用动态规划来完成。其实递归都写出来,写一个朴素版的动态规划也难不到哪去,毕竟动态规划就是记录子问题,并建立子问题之间映射而已,这和递归并无本质区别。

代码

代码支持 Python3:

Python3 Code:

一行代码就可以通过 LeetCode?来看下我是怎么做到的!

这种思路的代码超时了,并且仅仅执行了 35/100 testcase 就超时了。

数学分析

思路

我们还需要进一步优化时间复杂度,我们需要思考是否可以在线性的时间内完成。

我们继续前面的思路进行分析, 不难得出,我们不妨称其为等式 1:

f(n)

= 1/n + 0 + 1/n * (f(n-1) + f(n-2) + ... + f(2))

= 1/n * (f(n-1) + f(n-2) + ... + f(2) + 1)

= 1/n * (f(n-1) + f(n-2) + ... + f(2) + f(1))

似乎更复杂了?没关系,我们继续往下看,我们看下 f(n - 1),我们不妨称其为等式 2。

f(n-1) = 1/(n-1) * (f(n-2) + f(n-3) + ... + f(1))

我们将等式 1 和等式 2 两边分别同时乘以 n 和 n - 1

n * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1)

(n-1) * f(n-1) = f(n-2) + f(n-3) + ... + f(1)

我们将两者相减:

n * f(n) - (n-1)*f(n-1) = f(n-1)

我们继续将 (n-1)*f(n-1) 移到等式右边,得到:

n * f(n) = n * f(n-1)

也就是说:

f(n) = f(n - 1)

当然前提是 n 大于 2。

既然如此,我们就可以减少一层循环, 我们用这个思路来优化一下上面的 dp 解法。这种解法终于可以 AC 了。

代码

代码支持 Python3:

Python3 Code:

一行代码就可以通过 LeetCode?来看下我是怎么做到的!

优化数学分析

思路

上面我们通过数学分析,得出了当 n 大于 2 时:

f(n) = f(n - 1)

那么是不是意味着我们随便求出一个 n 就好了?比如我们求出 n = 2 的时候的值,是不是就知道 n 为任意数的值了。我们不难想出 n = 2 时候,概率是 0.5,因此只要 n 大于 1 就是 0.5 概率,否则就是 1 概率。

代码

代码支持 Python3:

Python3 Code:

一行代码就可以通过 LeetCode?来看下我是怎么做到的!

关键点

  • 概率分析
  • 数学推导
  • 动态规划
  • 递归 + mapper
  • 栈限制大小
  • 尾递归

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号