2023-12-30：用go语言，给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数，
如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列。
对于 0 <= i < n - 1 的下标 i：
要么 nums[i] % nums[i+1] == 0，
要么 nums[i+1] % nums[i] == 0。
请你返回特别排列的总数目，由于答案可能很大，请将它对 1000000007 取余 后返回。
输入：nums = [2,3,6]。
输出：2。
来自力扣2741. 特别的排列。
答案2023-12-30：
来自左程云。
灵捷3.5
大体步骤如下：
1.在main函数中，我们调用了specialPerm函数，并传入nums数组。在这个函数内部，首先计算了nums数组的长度n，然后初始化了一个二维数组dp，用于记录状态的转移。
2.specialPerm函数返回调用process函数的结果，传入了nums、n、0、0和dp作为参数。
3.process函数用于计算满足特殊条件的排列总数。首先，它检查dp数组中是否已经计算了当前状态s和位置p的结果，如果是，则直接返回该结果。
4.接下来，如果状态s表示所有的数字都被使用过，那么将结果设为1，表示找到了一个满足条件的排列。
5.否则，对于给定位置p，遍历每个数字i，如果当前状态s中没有包含数字i，且a[p]能整除a[i]或者a[i]能整除a[p]，则递归调用process函数，并将结果加到ans上。
6.最后，将得到的ans存入dp数组中，并返回结果。
整体的时间复杂度：O(n*2^n)，其中n是nums数组的长度。对于process函数中的每个状态s以及位置p，最坏情况下都要回溯所有的n个数字，因此是指数级的复杂度。
额外空间复杂度：O(2^n * n)，其中dp数组占据了主要的空间，它是一个大小为2^n * n的二维数组。
go完整代码如下：
packagemain
import"fmt"
varmod=1000000007
funcspecialPerm(nums[]int)int{
n:=len(nums)
dp:=make([][]int,1<fori:=rangedp{
dp[i]=make([]int,n)
forj:=rangedp[i]{
dp[i][j]=-1
}
}
returnprocess(nums,n,0,0,dp)
}
funcprocess(a[]int,n,s,pint,dp[][]int)int{
ifdp[s][p]!=-1{
returndp[s][p]
}
varansint
ifs==(1<ans=1
}else{
fori:=0;iifs==0||(s&(1<ans=(ans+process(a,n,s|(1<}
}
}
dp[s][p]=ans
returnans
}
funcmain(){
nums:=[]int{2,3,6}
result:=specialPerm(nums)
fmt.Println("Result:",result)
}
rust完整代码如下：
fnspecial_perm(nums:Vec)->i32{
letn=nums.len();
letmod_num=1000000007;
letmutdp=vec![vec![-1;n];1<process(&nums,n,0,0,&mutdp,mod_num)
}
fnprocess(a:&Vec,n:usize,s:usize,p:usize,dp:&mutVec>,mod_num:i32)->i32{
ifdp[s][p]!=-1{
returndp[s][p];
}
letans:i32;
ifs==(1<ans=1;
}else{
ans=(0..n).fold(0,|accum,i|{
ifs==0||(s&(1<(accum+process(a,n,s|(1<}else{
accum
}
});
}
dp[s][p]=ans;
ans
}
fnmain(){
letnums=vec![2,3,6];
letresult=special_perm(nums);
println!("Result:{}",result);
}
c++完整代码如下：
#include
#include
#include
usingnamespacestd;
constintmod=1000000007;
intprocess(constvector&a,intn,ints,intp,unordered_map>&dp){
if(dp.count(s)&&dp[s].count(p)!=0){
returndp[s][p];
}
intans=0;
if(s==(1<ans=1;
}
else{
for(inti=0;iif(s==0||(s&(1<ans=(ans+process(a,n,s|(1<}
}
}
dp[s][p]=ans;
returnans;
}
intspecialPerm(constvector&nums){
intn=nums.size();
unordered_map>dp;
returnprocess(nums,n,0,0,dp);
}
intmain(){
vectornums={2,3,6};
intresult=specialPerm(nums);
cout<<"Result:"<return0;
}
c完整代码如下：
#include
#include
#defineMOD1000000007
intprocess(int*a,intn,ints,intp,int**dp);
intspecialPerm(int*nums,intnumsSize){
intn=numsSize;
int**dp=(int**)malloc((1<for(inti=0;i<(1<dp[i]=(int*)malloc(n*sizeof(int));
for(intj=0;jdp[i][j]=-1;
}
}
returnprocess(nums,n,0,0,dp);
}
intprocess(int*a,intn,ints,intp,int**dp){
if(dp[s][p]!=-1){
returndp[s][p];
}
intans=0;
if(s==(1<ans=1;
}
else{
for(inti=0;iif(s==0||((s&(1<ans=(ans+process(a,n,s|(1<}
}
}
dp[s][p]=ans;
returnans;
}
intmain(){
intnums[]={2,3,6};
intresult=specialPerm(nums,sizeof(nums)/sizeof(nums[0]));
printf("Result:%d\n",result);
return0;
}
热门跟贴