算法题解

力扣（LeetCode）2741. 特别的排列。记忆化搜索，使用位运算进行状态压缩-JavaScript解答

/** 暴力法 */ var specialPerm = function(nums) { const len = nums.length; const dfs = function(u,i){ if(u === 0) return 1;//空集，说明能走到最后 

 /** 暴力法 */
var specialPerm = function(nums) {
    const len = nums.length;
    const dfs = function(u,i){
        if(u === 0) return 1;//空集，说明能走到最后
        let res = 0;
        for(let j = 0; j < len; j++){
            if(u&(1<<j) && (nums[i]%nums[j]===0||nums[j]%nums[i]===0)){
                res+=dfs(u^(1<<j),j); 
            }
        }
        return res;
    }
    let res = 0;
    for(let i = 0; i < len; i++){
       res +=  dfs(((1<<len)-1)^(1<<i),i);
    }
    return res % (10**9 + 7);
};

递归 + 哈希表 = 记忆化搜索

 /** 递归 + 哈希表 = 记忆化搜索  */
var specialPerm = function(nums) {
    const len = nums.length;
    const map = new Map();
    const dfs = function(u,i){
        if(u === 0) return 1;//空集，说明能走到最后
        if(map.has(u+"#"+i)) return map.get(u+"#"+i)
        let res = 0;
        for(let j = 0; j < len; j++){
            if(u&(1<<j) && (nums[i]%nums[j]===0||nums[j]%nums[i]===0)){
                res+=dfs(u^(1<<j),j); 
            }
        }
        map.set(u+"#"+i,res);
        return res;
    }
    let res = 0;
    for(let i = 0; i < len; i++){
       res +=  dfs(((1<<len)-1)^(1<<i),i);
    }
    return res % (10**9 + 7);
};

作者：__sgf__

链接：https://leetcode.cn/problems/special-permutations/solutions/

来源：力扣（LeetCode）

Comment