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 <= 1051 <= nums[i] <= 30
2、解题思路
- 状态压缩：对数组
nums使用哈希表计数，所有的键都会集中在 这个区间 - 从哈希表中剔除存在多个相同因子的数，比如
4,8,12 - 使用
BFS思路对符合要求的数字进行好子集组合，第一层为1个数的组合，第二层为2个数的组合，以此类推 - 组合过程中记得剔除掉存在最大公约数不为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
