Leetcode 1359:有效的快递序列数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1359:有效的快递序列数目(超详细的解法!!!)

in leetcode with 0 comment

给你 n 笔订单,每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目,确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大,请返回答案对 10^9 + 7 取余的结果。

示例 1:

输入:n = 1
输出:1
解释:只有一种序列 (P1, D1),物品 1 的配送服务(D1)在物品 1 的收件服务(P1)后。

示例 2:

输入:n = 2
输出:6
解释:所有可能的序列包括:
(P1,P2,D1,D2),(P1,P2,D2,D1),(P1,D1,P2,D2),(P2,P1,D1,D2),(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列,因为物品 2 的收件服务(P2)不应在物品 2 的配送服务(D2)之后。

示例 3:

输入:n = 3
输出:90

提示:

解题思路

实际上就是一个排列组合问题,假设当前n-1对数都排好了,现在考虑第n对数。第一个数有2n-1个空位可以插入,第二个数有2n个空位可以插入,所以总共有2n*(2n-1)种组合。对于第n对数种,我们希望p排在d的前面,由于pd前和dp前是两种对称的关系,所有每一种包含n*(2n-1)种组合。

对于第n-1对数采用同样的方式计算出来,得到(n-1)*(2(n-1)-1)种组合。那么最后的结果就是2n*(2n-1)*(2n-2)*(2n-3).../(2^n)=2n!/(2^n)

class Solution:
    def countOrders(self, n: int) -> int:
        return (math.factorial(n * 2) >> n) % (10**9 + 7)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses