2025-01-23：统计逆序对的数目。用go语言，给定一个整数 n 和一个二维数组 requirem)ents，其中每个元素 requirements[i] = [endi, cnti] 表示在要求中末尾的下标以及逆序对的数量。

在一个整数数组 nums 中，如果存在一个下标对 (i, j)，使得 i < j 且 nums[i] > nums[j]，则称这对 (i, j) 为逆序对。

任务是返回所有可能的数组排列 perm = [0, 1, 2, ..., n - 1] 的数量，使得对于所有的 requirements，都满足 perm[0..endi] 中恰好有 cnti 个逆序对。

由于结果可能会非常大，请将结果对 1000000007 取余后返回。

2 <= n <= 300。

1 <= requirements.length <= n。

requirements[i] = [endi, cnti]。

0 <= endi <= n - 1。

0 <= cnti <= 400。

输入保证至少有一个 i 满足 endi == n - 1 。

输入保证所有的 endi 互不相同。

输入：n = 3, requirements = [[2,2],[0,0]]。

输出：2。

解释：

两个排列为：

[2, 0, 1]

前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。

前缀 [2] 的逆序对数目为 0 个。

[1, 2, 0]

前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。

前缀 [1] 的逆序对数目为 0 个。

答案2025-01-23：

chatgpt[1]

题目来自leetcode3193。

大体步骤如下：

1.定义常量 MOD，表示取余值为 1e9 + 7。

2.编写函数 numberOfPermutations(n, requirements) 来计算符合要求的排列数量。

3.初始化一个要求映射 reqMap，记录每个末尾下标及其逆序对数量的要求。同时找出最大的逆序对数量 maxCnt。

4.构建动态规划数组 dp，用于存储计算结果，其中 dp[i][j] 表示前 i 个数中逆序对数量为 j 的排列数。

5.定义递归函数 dfs(end, cnt) 来计算符合要求的排列数量。

6.在 dfs 函数中，首先处理边界情况，然后根据当前位置是否存在逆序对要求进行不同的处理。

7.在主函数 main 中，给定 n = 3 和 requirements = [[2,2],[0,0]]，调用 numberOfPermutations 函数计算结果并打印输出。

总的时间复杂度：

• 针对每个位置及逆序对情况进行递归计算，时间复杂度为 O(n * maxCnt)。• 最终结果取模操作的时间复杂度为 O(1)。

总的额外空间复杂度：

• 使用了 reqMap 来存储逆序对的要求，空间复杂度为 O(n)。• 动态规划数组 dp 使用了二维数组来存储计算结果，空间复杂度为 O(n * maxCnt)。

因此，总的时间复杂度为 O(n * maxCnt)，总的额外空间复杂度为 O(n * maxCnt)。

Go完整代码如下：package mainimport ( "fmt")const MOD int64 = 1e9 + 7func numberOfPermutations(n int, requirements [][]int) int { reqMap := make(map[int]int) reqMap[0] = 0 maxCnt := 0 for _, req := range requirements { reqMap[req[0]] = req[1] if req[1] > maxCnt { maxCnt = req[1] } } if reqMap[0] != 0 { return 0 } dp := make([][]int64, n) for i := range dp { dp[i] = make([]int64, maxCnt + 1) for j := range dp[i] { dp[i][j] = -1 } } var dfs func(int, int) int64 dfs = func(end, cnt int) int64 { if cnt < 0 { return 0 } if end == 0 { return 1 } if dp[end][cnt] != -1 { return dp[end][cnt] } if r, exists := reqMap[end - 1]; exists { if r <= cnt && cnt <= end + r { dp[end][cnt] = dfs(end - 1, r) return dp[end][cnt] } return 0 } else { if cnt > end { dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt) + MOD) % MOD } else { dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD } return dp[end][cnt] } } return int(dfs(n - 1, reqMap[n - 1]))}func main() { n := 3 requirements := [][]int{{2,2},{0,0}} result := numberOfPermutations(n,requirements) fmt.Println(result)}

在这里插入图片描述

Rust完整代码如下：use std::collections::HashMap;const MOD: i64 = 1_000_000_007;fn number_of_permutations(n: usize, requirements: Vec<Vec<i32>>) -> i64 { let mut req_map: HashMap<i32, i32> = HashMap::new(); req_map.insert(0, 0); let mut max_cnt = 0; for req in requirements { req_map.insert(req[0], req[1]); if req[1] > max_cnt { max_cnt = req[1]; } } if *req_map.get(&0).unwrap() != 0 { return 0; } let mut dp = vec![vec![-1; (max_cnt + 1) as usize]; n]; fn dfs(end: usize, cnt: i32, req_map: &HashMap<i32, i32>, dp: &mut Vec<Vec<i64>>) -> i64 { if cnt < 0 { return 0; } if end == 0 { return 1; } if dp[end][cnt as usize] != -1 { return dp[end][cnt as usize]; } if let Some(&r) = req_map.get(&(end as i32 - 1)) { if r <= cnt && cnt <= end as i32 + r { dp[end][cnt as usize] = dfs(end - 1, r, req_map, dp); } else { return 0; } } else { if cnt > end as i32 { dp[end][cnt as usize] = (dfs(end, cnt - 1, req_map, dp) - dfs(end - 1, cnt - 1 - end as i32, req_map, dp) + dfs(end - 1, cnt, req_map, dp) + MOD) % MOD; } else { dp[end][cnt as usize] = (dfs(end, cnt - 1, req_map, dp) + dfs(end - 1, cnt, req_map, dp)) % MOD; } } dp[end][cnt as usize] } return dfs(n - 1, *req_map.get(&(n as i32 - 1)).unwrap(), &req_map, &mut dp);}fn main() { let n = 3; let requirements = vec![vec![2, 2], vec![0, 0]]; let result = number_of_permutations(n, requirements); println!("{}", result);}

在这里插入图片描述

Python完整代码如下：# -*-coding:utf-8-*-MOD = 10**9 + 7def number_of_permutations(n, requirements): req_map = {0: 0} max_cnt = 0 for req in requirements: req_map[req[0]] = req[1] if req[1] > max_cnt: max_cnt = req[1] if req_map[0] != 0: return 0 # 初始化动态规划表 dp = [[-1] * (max_cnt + 1) for _ in range(n)] def dfs(end, cnt): if cnt < 0: return 0 if end == 0: return 1 if dp[end][cnt] != -1: return dp[end][cnt] if end - 1 in req_map: r = req_map[end - 1] if r <= cnt <= end + r: dp[end][cnt] = dfs(end - 1, r) return dp[end][cnt] return 0 else: if cnt > end: dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt)) % MOD else: dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD return dp[end][cnt] return int(dfs(n - 1, req_map[n - 1]))def main(): n = 3 requirements = [[2, 2], [0, 0]] result = number_of_permutations(n, requirements) print(result)if __name__ == "__main__": main()

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP