Leetcode 1359:有效的快递序列数目(超详细的解法!!!)
发布日期:2021-06-29 15:58:37
浏览次数:2
分类:技术文章
本文共 804 字,大约阅读时间需要 2 分钟。
给你 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
提示:
1 <= n <= 500
解题思路
实际上就是一个排列组合问题,假设当前n-1
对数都排好了,现在考虑第n
对数。第一个数有2n-1
个空位可以插入,第二个数有2n
个空位可以插入,所以总共有2n*(2n-1)
种组合。对于第n
对数种,我们希望p
排在d
的前面,由于p
在d
前和d
在p
前是两种对称的关系,所有每一种包含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)
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/104461735 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月09日 04时25分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
EasyDSS平台接入设备量过多的情况下如何进行批量推流测试?
2019-04-29
mysql数据库操作基础
2019-04-29
Mariadb基础管理
2019-04-29
awk 的内置变量 NF、NR、FNR、FS、OFS、RS、ORS
2019-04-29
CentOS系统内核升级攻略
2019-04-29
linux系统时区修改(Debian的主机和docker)
2019-04-29
docker-compose 安装
2019-04-29
crontab 定时任务
2019-04-29
查看docker veth pair与宿主机上网卡的对应关系
2019-04-29
使用 GitLab CI 进行持续集成的一些踩坑
2019-04-29
企业云盘给贸易业带来新的效益
2019-04-29
Linux入门常用命令
2019-04-29
Spring整理
2019-04-29
SpringMvc加强
2019-04-29
初识Vue全家桶 Nuxt.js(一)
2019-04-29
基本路由及动态路由(二)
2019-04-29