千问 LeetCode 1359.有效的快递序列数目 public int countOrders(int n)
这道题要求计算 n 个订单所有有效的收件/配送序列数目，其中每个订单的配送（Delivery）必须在其收件（Pickup）之后。
这是一个经典的组合数学问题，可以通过递推的方法来解决。
💡 解题思路
我们可以从 n-1 个订单的合法序列，推导出 n 个订单的合法序列数量。
1. 基础情况：当 n=1 时，只有一个订单，序列只能是 (P1, D1)，所以只有 1 种有效序列。
2. 递推关系：假设我们已经有了 n-1 个订单的所有合法序列。现在要加入第 n 个订单的 (Pn, Dn)。
* n-1 个订单会形成一个长度为 2 * (n-1) 的序列。
* 这个序列中有 2 * (n-1) + 1 个“空位”可以用来插入新的元素（包括序列开头、结尾和任意两个元素之间）。
* 我们需要将 Pn 和 Dn 放入这些空位中，并且保证 Pn 在 Dn 之前。
* 我们可以这样考虑：
* 首先放置 Pn。它有 2 * (n-1) + 1 个位置可选。
* 假设 Pn 已经放在了某个位置，那么 Dn 只能放在 Pn 之后的空位里。
* 如果 Pn 放在第 1 个空位，Dn 有 2 * (n-1) + 1 个后续空位可选。
* 如果 Pn 放在第 2 个空位，Dn 有 2 * (n-1) 个后续空位可选。
* ...
* 如果 Pn 放在最后一个空位，Dn 只有 1 个后续空位可选。
* 因此，对于每一个 n-1 订单的序列，插入第 n 个订单的总方法数是：
(2n-1) + (2n-2) + ... + 1
* 这是一个等差数列求和，结果为 (2n-1) * 2n / 2 = n * (2n-1)。
所以，我们得到了递推公式：f(n) = f(n-1) * n * (2n - 1)。
💻 Java 代码实现
根据上面的递推公式，我们可以写出简洁的递归或迭代代码。
方法一：递归实现
class Solution {
private static final int MOD = 1000000007;
public int countOrders(int n) {
// 基础情况：1个订单只有1种序列
if (n == 1) {
return 1;
}
// 递推公式：f(n) = f(n-1) * n * (2n - 1)
// 注意使用 long 防止乘法溢出
return (int) (((long) countOrders(n - 1) * n % MOD) * (2 * n - 1) % MOD);
}
}
方法二：迭代实现 (更优)
迭代方法避免了递归的函数调用开销，效率更高。
class Solution {
public int countOrders(int n) {
long res = 1; // 使用 long 防止中间结果溢出
int MOD = 1000000007;
// 从 i=2 开始迭代计算到 n
for (int i = 2; i <= n; i++) {
// 每次乘以 i * (2*i - 1) 并取模
res = res * i % MOD;
res = res * (2 * i - 1) % MOD;
}
return (int) res;
}
}
📊 复杂度分析
* 时间复杂度：O(n)。无论是递归还是迭代，都需要进行 n 次计算。
* 空间复杂度：
* 递归方法：O(n)，因为递归调用栈的深度为 n。
* 迭代方法：O(1)，只使用了常数级别的额外空间。
因此，迭代方法是更优的选择。