列表

详情

100333. 统计逆序对的数目

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：

请你返回 [0, 1, 2, ..., n - 1] 的 排列 perm 的数目，满足对 所有 的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。

由于答案可能会很大，将它对 109 + 7 取余 后返回。

 

示例 1：

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

输出：2

解释：

两个排列为：

示例 2：

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

输出：1

解释：

唯一满足要求的排列是 [2, 0, 1] ：

示例 3：

输入：n = 2, requirements = [[0,0],[1,0]]

输出：1

解释：

唯一满足要求的排列为 [0, 1] ：

 

 

提示：

相似题目

K 个逆序对数组

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int numberOfPermutations(int n, vector<vector<int>>& requirements) { } };

rust 解法, 执行用时: 333 ms, 内存消耗: 3.2 MB, 提交时间: 2024-10-17 09:06:28 

use std::collections::HashMap;
const MOD: i64 = 1_000_000_007;

impl Solution {
    pub fn number_of_permutations(n: i32, requirements: Vec<Vec<i32>>) -> i32 {
        let mut req_map = HashMap::new();
        req_map.insert(0, 0);
        let mut max_cnt = 0;
        for i in 0..requirements.len() {
            let end = requirements[i][0];
            let cnt = requirements[i][1];
            req_map.insert(end, cnt);
            if cnt > max_cnt {
                max_cnt = cnt;
            }
        }
        if *req_map.get(&0).unwrap() != 0 {
            return 0;
        }
        let mut dp = vec![vec![-1; max_cnt as usize + 1]; n as usize];

        fn dfs(end: usize, cnt: usize, req_map: &HashMap<i32, i32>, dp: &mut Vec<Vec<i64>>) -> i64 {
            if end == 0 {
                return 1;
            }
            if dp[end][cnt] != -1 {
                return dp[end][cnt];
            }
            if let Some(&r) = req_map.get(&(end as i32 - 1)) {
                if r as usize <= cnt && cnt <= end + r as usize {
                    dp[end][cnt] = dfs(end - 1, r as usize, req_map, dp);
                    return dp[end][cnt];
                }
                return 0;
            }
            let mut tot_sum = 0;
            for i in 0..=cnt.min(end) {
                tot_sum = (tot_sum + dfs(end - 1, cnt - i, req_map, dp)) % MOD;
            }
            dp[end][cnt] = tot_sum;
            tot_sum
        }

        dfs(n as usize - 1, *req_map.get(&(n - 1)).unwrap() as usize, &req_map, &mut dp) as i32
    }
}

java 解法, 执行用时: 405 ms, 内存消耗: 44.3 MB, 提交时间: 2024-06-28 17:55:43 

public class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        int[] req = new int[n];
        Arrays.fill(req, -1);
        req[0] = 0;
        int m = 0;
        for (int[] p : requirements) {
            req[p[0]] = p[1];
            m = Math.max(m, p[1]);
        }
        if (req[0] > 0) {
            return 0;
        }

        int[][] memo = new int[n][m + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        return dfs(n - 1, req[n - 1], req, memo);
    }

    private int dfs(int i, int j, int[] req, int[][] memo) {
        if (i == 0) {
            return 1;
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }
        int res = 0;
        int r = req[i - 1];
        if (r >= 0) {
            if (j >= r && j - i <= r) {
                res = dfs(i - 1, r, req, memo);
            }
        } else {
            for (int k = 0; k <= Math.min(i, j); k++) {
                res = (res + dfs(i - 1, j - k, req, memo)) % 1_000_000_007;
            }
        }
        return memo[i][j] = res; // 记忆化
    }
}

java 解法, 执行用时: 391 ms, 内存消耗: 43.9 MB, 提交时间: 2024-06-28 17:55:31 

public class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        final int MOD = 1_000_000_007;
        int[] req = new int[n];
        Arrays.fill(req, -1);
        req[0] = 0;
        int m = 0;
        for (int[] p : requirements) {
            req[p[0]] = p[1];
            m = Math.max(m, p[1]);
        }
        if (req[0] > 0) {
            return 0;
        }

        int[][] f = new int[n][m + 1];
        f[0][0] = 1;
        for (int i = 1; i < n; i++) {
            int mx = req[i] < 0 ? m : req[i];
            int r = req[i - 1];
            if (r >= 0) {
                for (int j = r; j <= Math.min(i + r, mx); j++) {
                    f[i][j] = f[i - 1][r];
                }
            } else {
                for (int j = 0; j <= mx; j++) {
                    for (int k = 0; k <= Math.min(i, j); k++) {
                        f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
                    }
                }
            }
        }
        return f[n - 1][req[n - 1]];
    }
}

golang 解法, 执行用时: 222 ms, 内存消耗: 6.7 MB, 提交时间: 2024-06-28 17:55:04 

func numberOfPermutations(n int, requirements [][]int) int {
	const mod = 1_000_000_007
	req := make([]int, n)
	for i := 1; i < n; i++ {
		req[i] = -1
	}
	for _, p := range requirements {
		req[p[0]] = p[1]
	}
	if req[0] > 0 {
		return 0
	}

	m := slices.Max(req)
	memo := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, m+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) (res int) {
		if i == 0 {
			return 1
		}
		p := &memo[i][j]
		if *p != -1 {
			return *p
		}
		defer func() { *p = res }()
		if r := req[i-1]; r >= 0 {
			if j < r || j-i > r {
				return 0
			}
			return dfs(i-1, r)
		}
		for k := 0; k <= min(i, j); k++ {
			res += dfs(i-1, j-k)
		}
		return res % mod
	}
	return dfs(n-1, req[n-1])
}

// 1:1递推
func numberOfPermutations2(n int, requirements [][]int) int {
	const mod = 1_000_000_007
	req := make([]int, n)
	for i := 1; i < n; i++ {
		req[i] = -1
	}
	for _, p := range requirements {
		req[p[0]] = p[1]
	}
	if req[0] > 0 {
		return 0
	}

	m := slices.Max(req)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, m+1)
	}
	f[0][0] = 1
	for i := 1; i < n; i++ {
		mx := m
		if req[i] >= 0 {
			mx = req[i]
		}
		if r := req[i-1]; r >= 0 {
			for j := r; j <= min(i+r, mx); j++ {
				f[i][j] = f[i-1][r]
			}
		} else {
			for j := 0; j <= mx; j++ {
				for k := 0; k <= min(i, j); k++ {
					f[i][j] = (f[i][j] + f[i-1][j-k]) % mod
				}
			}
		}
	}
	return f[n-1][req[n-1]]
}

cpp 解法, 执行用时: 429 ms, 内存消耗: 31.9 MB, 提交时间: 2024-06-28 17:54:27 

class Solution {
    const int MOD = 1'000'000'007;
public:
    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
        vector<int> req(n, -1);
        req[0] = 0;
        for (auto& p : requirements) {
            req[p[0]] = p[1];
        }
        if (req[0]) {
            return 0;
        }

        int m = ranges::max(req);
        vector<vector<int>> f(n, vector<int>(m + 1));
        f[0][0] = 1;
        for (int i = 1; i < n; i++) {
            int mx = req[i] < 0 ? m : req[i];
            if (int r = req[i - 1]; r >= 0) {
                for (int j = r; j <= min(i + r, mx); j++) {
                    f[i][j] = f[i - 1][r];
                }
            } else {
                for (int j = 0; j <= mx; j++) {
                    for (int k = 0; k <= min(i, j); k++) {
                        f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
                    }
                }
            }
        }
        return f[n - 1][req[n - 1]];
    }


    int numberOfPermutations2(int n, vector<vector<int>>& requirements) {
        vector<int> req(n, -1);
        req[0] = 0;
        for (auto& p : requirements) {
            req[p[0]] = p[1];
        }
        if (req[0]) {
            return 0;
        }

        int m = ranges::max(req);
        vector<vector<int>> memo(n, vector<int>(m + 1, -1)); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int i, int j) -> int {
            if (i == 0) {
                return 1;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            if (int r = req[i - 1]; r >= 0) {
                if (j >= r && j - i <= r) {
                    res = dfs(dfs, i - 1, r);
                }
            } else {
                for (int k = 0; k <= min(i, j); k++) {
                    res = (res + dfs(dfs, i - 1, j - k)) % MOD;
                }
            }
            return res;
        };
        return dfs(dfs, n - 1, req[n - 1]);
    }
};

python3 解法, 执行用时: 6575 ms, 内存消耗: 47.5 MB, 提交时间: 2024-06-28 17:53:54 

class Solution:
    # 记忆化搜索
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 1_000_000_007
        req = [-1] * n
        req[0] = 0
        for end, cnt in requirements:
            req[end] = cnt
        if req[0]:
            return 0

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i == 0:
                return 1
            r = req[i - 1]
            if r >= 0:
                return dfs(i - 1, r) if r <= j <= i + r else 0
            return sum(dfs(i - 1, j - k) for k in range(min(i, j) + 1)) % MOD
        return dfs(n - 1, req[-1])
        
    # 1:1递推
    def numberOfPermutations2(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 1_000_000_007
        req = [-1] * n
        req[0] = 0
        for end, cnt in requirements:
            req[end] = cnt
        if req[0]:
            return 0

        m = max(req)
        f = [[0] * (m + 1) for _ in range(n)]
        f[0][0] = 1
        for i in range(1, n):
            mx = m if req[i] < 0 else req[i]
            r = req[i - 1]
            if r >= 0:
                for j in range(r, min(i + r, mx) + 1):
                    f[i][j] = f[i - 1][r]
            else:
                for j in range(mx + 1):
                    f[i][j] = sum(f[i - 1][j - k] for k in range(min(i, j) + 1)) % MOD
        return f[-1][req[-1]]

上一题

© 2024 leetcode.cn