jjzjj

LeetCode #1359 Count All Valid Pickup and Delivery Options 有效的快递序列数目

air_melt 2023-09-23 原文

1359 Count All Valid Pickup and Delivery Options 有效的快递序列数目

Description:

Given n orders, each order consist in pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

Since the answer may be too large, return it modulo 10^9 + 7.

Example:

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders:
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

题目描述：

给你 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

思路：

数学
设 f(n) 表示 n 件快递的排列数
f(n) 可由 f(n - 1) 加上第 n 件快递得到
前 n - 1 件快递一共有 2(n - 1) 个序列
由于发件一定要在收件之后
要么两个次序在一起, 要么被 2(n - 1) 个序列分开
前者 2(n - 1) 加上一头一尾两个位置, 一共有 2n - 1 个位置能放
后者相当于在上面的 2n - 1 个位置中选出 2 个不相邻的位置, 共有 (2n - 1)(2n - 2) / 2 种方式
综上所述, f(n) = n(2n - 1)f(n - 1)
时间复杂度为 O(n), 空间复杂度为 O(1)

代码:

C++:

class Solution 
{
public:
    int countOrders(int n) 
    {
        return n == 1 ? 1 : (int64_t)countOrders(n - 1) * ((n << 1) - 1) * n % (int)(1e9 + 7);
    }
};

Java:

class Solution {
    public int countOrders(int n) {
        long result = 1, mod = 1_000_000_007;
        for (int i = 2; i <= n; i++) result = result * ((i << 1) - 1) % mod * i % mod;
        return (int)result;
    }
}

Python:

class Solution:
    def countOrders(self, n: int) -> int:
        return 1 if n == 1 else self.countOrders(n - 1) * ((n << 1) - 1) * n % (10 ** 9 + 7)
数目LeetCodestrongbr收件

有关LeetCode #1359 Count All Valid Pickup and Delivery Options 有效的快递序列数目的更多相关文章

  1. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2

    是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。 最佳答案

  4. ruby - 为什么这个救援语法有效？ - 2

    好的，所以我有了我正在使用的应用程序的这种方法，它可以在生产中使用。我的问题为什么这行得通？这是新的Ruby语法吗？defeditload_elements(current_user)unlesscurrent_user.role?(:admin)respond_todo|format|format.json{render:json=>@user}format.xml{render:xml=>@user}format.htmlendrescueActiveRecord::RecordNotFoundrespond_to_not_found(:json,:xml,:html)end

  5. ruby - 奇怪的 ruby​​ for 循环行为(为什么这样做有效) - 2

    defreverse(ary)result=[]forresult[0,0]inaryendresultendassert_equal["baz","bar","foo"],reverse(["foo","bar","baz"])这行得通，我想了解原因。有什么解释吗？ 最佳答案 如果我使用each而不是for/in重写它，它看起来像这样:defreverse(ary)result=[]#forresult[0,0]inaryary.eachdo|item|result[0,0]=itemendresultendforainb基本上就

  6. arrays - 在两个数组中查找不相交元素的有效方法是什么？ - 2

    我有以下数组:A=[1,2,3,4,5]B=[2,6,7,1]我想找到不相交的元素，如下:output=[3,4,5,6,7]我是这样实现的，output=A+B-(A&B)但它效率低下，因为我添加了两个数组，然后删除了公共(public)元素。它类似于查找不相交的元素。我能做得比这更好吗？如果是，怎么办？ 最佳答案 如何只选择A中的元素而不是B中的元素以及B中的元素而不是A中的元素。(A-B)+(B-A) 关于arrays-在两个数组中查找不相交元素的有效方法是什么？，我们在Stack

  7. ruby - 为什么 `middleman serve` 有效，但是 `middleman build` 编译这个 Sass 失败？ - 2

    当我刚刚运行middleman时服务，all.css编译得很好，只包含对+box-shadow(none)的调用:/*line1,/home/yang/asdf/source/stylesheets/content.css.sass*/div{-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;}但是当我构建网站时，我得到了这个Sass/Compass错误:$middlemanbuildSlim::EmbeddedEngineisdeprecated,itiscalledSlim::EmbeddedinSlim2.0

  8. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  9. ruby - 在公差范围内确定两条线段是否属于同一线段的最有效方法是什么？ - 2

    编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01

  10. ruby - 如何检查一个值是否是 Integer()、Float() 或 Rational() 的有效输入？ - 2

    这大致基于“HowtoconvertaStringtoIntegerorFloat”。如果我想使用Ruby的内置转换机制将数字字符串输入转换为其“最合适的类型”，我可以这样做:defconvert(input)value=Integer(input)rescuenilvalue||=Float(input)rescuenilvalue||=Rational(input)rescuenilvalueendconvert('1')#=>1convert('1_000')#=>1000convert('0xff')#=>255convert('0.5')#=>0.5convert('1e2'

随机推荐