Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

describe

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 1:

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

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.
Copy the code

Example 3:

Input: n = 3
Output: 90
Copy the code

Note:

1 <= n <= 500
Copy the code

parsing

Given n orders, each order contains a pickup and delivery service. Calculates all valid pickup/delivery possible sequences so that delivery(I) is always after pickup(I). Because the answer may be too large, the result is returned modulo 10^9 + 7.

In fact, as soon as I read this problem, I know that I’m looking at mathematical logic, because this is a permutation and combination problem. We have defined that the pick up action must precede the delivery action, so:

1. When n=1, there can only be one delivery method (P1, D1) when we have a parcel.

2. When n=2, when we have two packages, the pick-up action has two P1 and P2, and the delivery action has two D1 and D2:

  • If we insert P2 and D2 as a whole in the fixed case of n=1 (P1, D1), then there are three ways: __P1D1, P1__D1, P1D1__;
  • When P2 and D2 are not next to each other, we assume that P2 is before P1, then there are two ways: P2P1_D1, P2P1D1_;
  • When P2 and D2 are not next to each other, let’s assume P2 is after P1, then there is one way: P1P2D1_, so there are 3+2+1 =6 different ways to send.

3. When n=3, we have already had 6 ways in the case of n=2. We choose any P1P2D1D2 to explain, and arrange P3 and D3 based on P1P2D1D2:

  • To insert P3 and D3 as a whole, there are 5 methods: __P1P2D1D2, P1__P2D1D2, P1P2__D1D2, P1P2D1__D2, P1P2D1__D2;
  • Then when P3 and D3 are not next to each other, we assume that P3 precedes P1 in four ways: P3P1_P2D1D2, P3P1P2_D1D2, P3P1P2D1_D2, P3P1P2D1D2_
  • Then when P3 and D3 are not next to each other, we assume that P3 precedes P2 in three ways: P1P3P2_D1D2, P1P3P2D1_D2, and P1P3P2D1D2_
  • Then when P3 and D3 are not next to each other, we assume that P3 follows P2 in two ways: P1P2P3D1_D2, P1P2P3D1D2_
  • Then when P3 and D3 are not next to each other, we assume that P3 follows D1 in one way: P1P2D1P3D2_

So when we have 5 plus 4 plus 3 plus 2 plus 1 is equal to 15 ways, and because we have 6 ways when n is equal to 2, we have a total of 15 times 6 is equal to 90 ways

When n=4, there should be 90x(7+6+5+4+3+2+1)=2520 ways.

By analogy, we know the rule. When there are n (>=2) packages, we know that the combination of n-1 has been calculated as num. We need to arrange new combinations according to each case of n-1, and each previous combination can form a new combination in total (1+2+3… +(2*n-2)+1), after simplification, is (2*n-1)*n, and then multiply by num to get the delivery method of N packages.

The time complexity is O(N), and the space complexity is O(1).

answer

class Solution(object):
    def countOrders(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 1
        for i in range(2, n+1):
            result *= (2*i-1)*i
        return result % (10**9 + 7)
        	      
		
Copy the code

The results

Runtime: 10 ms, faster than 29.63% of Python online submissions for Count All Valid Pickup and Delivery Options. Memory Usage: Submissions in Python online submissions for Count All Valid Pickup and Delivery Options.Copy the code

The original link

Leetcode.com/problems/co…

Your support is my biggest motivation