数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找数组的错位排列
假设我们有一个数组，包含从 1 到 n 的 n 个数字，并且按升序排列，我们需要找到它可以生成的错位排列的数量。
我们知道，在组合数学中，错位排列是指集合元素的一种排列，其中没有元素出现在其原始位置。答案可能非常大，因此返回输出模 10^9 + 7。
因此，如果输入为 3，则输出将为 2，因为原始数组为 [1,2,3]。两个错位排列为 [2,3,1] 和 [3,1,2]。
为了解决这个问题，我们将遵循以下步骤 -
m := 10^9 + 7
定义一个函数 add()，它将接收 a、b，
返回 ((a mod m) + (b mod m)) mod m
定义一个函数 mul()，它将接收 a、b，
返回 ((a mod m) * (b mod m)) mod m
从主方法执行以下操作
ret := 0
如果 n 等于 1，则 -
返回 0
如果 n 等于 2，则 -
返回 1
定义一个大小为 (n + 1) 的数组 dp
dp[2] := 1
从初始化 i := 3，当 i <= n 时，更新（i 增加 1），执行 -
dp[i] := mul(i - 1, add(dp[i - 2], dp[i - 1]))
返回 dp[n]
示例
让我们看看下面的实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
class Solution {
public:
int findDerangement(int n) {
int ret = 0;
if (n == 1)
return 0;
if (n == 2)
return 1;
vector dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
}
return dp[n];
}
};
main(){
Solution ob;
cout<<(ob.findDerangement(3));
}输入
3
输出
2
更新于: 2020-11-16
291 次查看
广告