跳到主要内容

1994.好子集的数目

· 阅读需 5 分钟

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

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


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