2 篇博文 含有标签「状态压缩」

1、题干​

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

• 玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
• 可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
• 单词表 words 中每个单词只能计分（使用）一次。
• 根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
• 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

提示：

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i] 和 letters[i] 只包含小写的英文字母。

2、思路​

回溯，枚举所有情况计算最高得分。未优化，存在重复计算，效率不高。

3、代码​

function maxScoreWords(words: string[], letters: string[], score: number[]): number {
    const wordScore = new Array(words.length).fill(0);
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words[i].length; j++) {
            wordScore[i] += score[words[i][j].charCodeAt(0) - 97];
        }
    }

    const letterDict = new Array(26).fill(0);
    for (let i = 0; i < letters.length; i++) {
        letterDict[letters[i].charCodeAt(0) - 97] += 1;
    }

    let ans = 0;
    function dfs(sc: number, visited: Set<number>) {
        for (let i = 0; i < words.length; i++) {
            if (visited.has(i)) continue;

            let valid = true;
            for (let j = 0; j < words[i].length; j++) {
                const c = words[i][j].charCodeAt(0) - 97;
                letterDict[c]--;
                if (letterDict[c] < 0) valid = false;
            }

            if (valid) {
                ans = Math.max(ans, sc + wordScore[i]);

                visited.add(i);
                dfs(sc + wordScore[i], visited);
                visited.delete(i);
            }

            for (let j = 0; j < words[i].length; j++) {
                letterDict[words[i][j].charCodeAt(0) - 97]++;
            }
        }
    }

    return dfs(0, new Set()), ans;
};

4、执行结果​

1、题干​

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

• 比方说，如果 nums = [1, 2, 3, 4] ：
  • [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
  • [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。

请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

示例 1：

输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：

输入：nums = [4,2,3,15]
输出：5
解释：好子集为：
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 30

2、解题思路​

• 状态压缩：对数组 nums 使用哈希表计数，所有的键都会集中在 $[1,30]$ 这个区间
• 从哈希表中剔除存在多个相同因子的数，比如4,8,12
• 使用 BFS 思路对符合要求的数字进行好子集组合，第一层为1个数的组合，第二层为2个数的组合，以此类推
• 组合过程中记得剔除掉存在最大公约数不为1的情况，另外注意去重
• 计算每层好子集数量并累加
  • 好子集数量等于子集各元素个数相乘
  • 若子集中存在 $1$，不是乘以 $1$ 的数量 $c1$，而应该乘以 $1$ 的组合总数 $2^{c1}-1$，由于 $c1$ 可能很大直接计算会溢出，可以使用累乘并模 $1e9+7$

这道题最大的坑在于对数字 $1$ 的特殊处理，这个解法和代码都不是最优的，抽空再优化了

3、代码​

var numberOfGoodSubsets = function (nums) {
    const MOD = 1e9 + 7;
    const nMap = nums.reduce((a, c) => a.set(c, (a.get(c) || 0) + 1), new Map());
    const bNums = [4, 9, 16, 25, 8, 27, 16];
    const gNums = [...nMap.keys()].filter(n => bNums.every((b) => n % b)).sort((a, b) => a - b);
    const gcd = (a, b) => (b ? gcd(b, a % b) : a);

    let cn1 = 1;
    for (let c1 = nMap.get(1); c1; c1--) cn1 = 2 * cn1 % MOD;

    let count = 0, queue = gNums.map((n) => [n]);
    while (queue.length) {
        const nextQueue = [];
        for (const arr of queue) {
            for (const g of gNums) {
                if (g <= arr[arr.length - 1] || arr.some((a) => gcd(a, g) > 1)) continue;
                nextQueue.push([...arr, g]);
            }

            if (arr.length === 1 && arr[0] === 1) continue;
            count += arr.reduce((a, c) => {
                const cn = c > 1 ? nMap.get(c) : cn1 - 1;
                return a * cn % MOD;
            }, 1);
            count = count % MOD;
        }
        queue = nextQueue;
    }

    return count;
};

4、执行结果​

• 执行用时: 468 ms
• 内存消耗: 63.9 MB