平面设计可以做网站,旅游网站规划设计方案,宠物用品网站开发背景,做网站需要注册什么类型的公司给你一个下标从 0 开始的整数数组 nums #xff0c;它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件#xff0c;我们称它是一个特别的排列#xff1a; 对于 0 i n - 1 的下标 i #xff0c;要么 nums[i] % nums[i1] 0 #xff0c;要么 nums[…给你一个下标从 0 开始的整数数组 nums 它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件我们称它是一个特别的排列 ·对于 0 i n - 1 的下标 i 要么 nums[i] % nums[i1] 0 要么 nums[i1] % nums[i] 0 。
请你返回特别排列的总数目由于答案可能很大请将它对 109 7 取余 后返回。
示例 1
输入nums [2,3,6]
输出2
解释[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。示例 2
输入nums [1,4,3]
输出2
解释[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。提示 ·2 nums.length 14 ·1 nums[i] 109
题目大意在只有可整除的数字能相邻的情况下计算所有合法排列的数量。
分析
1由于可整除的数字可以相邻因此可整除的两个数之间可以视为有一条无向边用图的思想处理本题将每个数字视为一个结点。分别从数组中的每个结点开始进行一次深度优先遍历计算可以连接所有结点的路径的个数sum得到的sum即为所求的合法排列的数量
2由于长度为N的数组有N!种排列用枚举的方式搜索会超时因此采用记忆化搜索加速计算。设当前遍历的结点为i当前的状态为flag状态flag表示已遍历的结点和未遍历的结点如flag0b011001时表示第2、3、6个结点已被遍历而第1、4、5个结点还没有遍历。因为在相同状态flag下遍历i结点返回的合法排列数量是相同的所以建立二维数组dp其中dp[i][flag]表示在状态flag的情况下遍历i结点可获得的合法排列数量以此记录已遍历过的情况加速深度优先搜索。
class Solution {
public:int specialPerm(vectorint nums) {int Nnums.size(),flag(1N)-1,ans0;vectorvectorint dp(N,vectorint(1N,-1));functionint(int) dfs[](int root){if(dp[root][flag]!-1) return dp[root][flag];int sum0;for(int i0,f1;iN;i,f1){if(root!i(flagf)!(nums[i]%nums[root]nums[root]%nums[i])){flag^f;sum(sumdfs(i))%1000000007;flag^f;}}return dp[root][flag]sum;};for(int i0;iN;i) dp[i][0]1;for(int i0,f1;iN;i,f1){flag^f;ans(ansdfs(i))%1000000007;flag^f;}return ans;}
};
