千问 LeetCode 1359.有效的快递序列数目 public int countOrders(int n)

这道题要求计算 n 个订单所有有效的收件/配送序列数目其中每个订单的配送Delivery必须在其收件Pickup之后。这是一个经典的组合数学问题可以通过递推的方法来解决。 解题思路我们可以从 n-1 个订单的合法序列推导出 n 个订单的合法序列数量。1. 基础情况当 n1 时只有一个订单序列只能是 (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;// 从 i2 开始迭代计算到 nfor (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)只使用了常数级别的额外空间。因此迭代方法是更优的选择。