多城市分站站群cms,深圳市住房保障署官网,芜湖做网站的客户,网站建设的步骤过程1994.好子集的数目 题目描述解决方案#xff1a;状态压缩动态规划代码#xff1a;Python 题目来源#xff1a;LeetCode 原文链接#xff1a;https://mp.weixin.qq.com/s/myI7_ZwJM7kizrwUtWgAZQ 难度级别#xff1a;困难
题目描述
给你一个整数数组 nums。如果 nums 的一… 1994.好子集的数目 题目描述解决方案状态压缩动态规划代码Python 题目来源LeetCode 原文链接https://mp.weixin.qq.com/s/myI7_ZwJM7kizrwUtWgAZQ 难度级别困难
题目描述
给你一个整数数组 nums。如果 nums 的一个子集中所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积那么我们称它为 好子集。
比方说如果 nums [1, 2, 3, 4] [2, 3] [1, 2, 3] 和 [1, 3] 是 好 子集乘积分别为 6 2 × 3 6 2 \times 3 62×3 6 2 × 3 6 2 \times 3 62×3 和 3 3 。[1, 4] 和 [4] 不是 好 子集因为乘积分别为 4 2 × 2 4 2 \times 2 42×2 和 4 2 × 2 4 2 \times 2 42×2 。
请你返回 nums 中不同的 好 子集的数目对 1 0 9 7 10^9 7 1097 取余 的结果。
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 可以表示为互不相同质数 23 和 5 的乘积。
- [3]乘积为 3 可以表示为质数 3 的乘积。
- [15]乘积为 15 可以表示为互不相同质数 3 和 5 的乘积。提示 1 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 1 n u m s [ i ] 30 1 nums[i] 30 1nums[i]30
解决方案状态压缩动态规划
题目乍看毫无头绪但是仔细阅读之后发现规定数组nums中的元素不超过30因此可以将[1,30]中的整数分成如下三类
对于任意一个好子集来说添加任意数目的1得到的新子集仍然是好子集2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30这些数均不包含平方因子因此每个数在好子集中至多出现一次4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28这些数包含平方因子因此一定不能在好子集中出现。
首先通过硬编码的方式把[1,30]中的整数按照上述分类也可以先预处理出所有[1,30]中质数2, 3, 5, 7, 11, 13, 17, 19, 23, 29再通过试除的方式动态分类。
分类完成后就可以考虑使用动态规划了。由于每个质因数只能出现一次并且[1, 30]中一共有10个质数因此可以用一个长度为10的二进制数mask表示这些质因数的使用情况其中mask的第 i 位为1表示第 i 个质数已经被使用过了。
因此定义 f [ i ] [ m a s k ] f[i][mask] f[i][mask]表示只选择[2,i]范围内的数并且选择的数的质因数使用情况为mask时的方案数。
如果 i 本身包含平方因子那么无法选择 i , 相当于在[2, i-1]范围内选择状态转移方程为 f [ i ] [ m a s k ] f [ i − 1 ] [ m a s k ] f[i][mask] f[i-1][mask] f[i][mask]f[i−1][mask]如果 i 本身不包含平方因子记其包含的质因子的二进制表示为subset同样可以通过试除的方法得到那么状态转移方程为 f [ i ] [ m a s k ] f [ i − 1 ] [ m a s k ] f [ i − 1 ] [ m a s k s u b s e t ] × f r e q [ i ] f[i][mask]f[i-1][mask]f[i-1][mask\\subset]\times freq[i] f[i][mask]f[i−1][mask]f[i−1][masksubset]×freq[i]其中 freq[i]表示数组nums中 i 出现的次数mask\subset表示从二进制表示mask中去除所有在subset中出现的1可以使用按位异或运算实现。这里需要保证subset是mask的子集可以使用按位与运算来判断。
动态规划的边界条件为 f [ 1 ] [ 0 ] 2 f r e q [ 1 ] f[1][0]2freq[1] f[1][0]2freq[1]即每一个在数组nums中出现的1都可以选或者不选。最终的答案即为所有 f [ 30 ] [ . . ] f[30][..] f[30][..]中除了 f [ 30 ] [ 0 ] f[30][0] f[30][0]以外的项的总和。
细节 注意到 f [ i ] [ m a s k ] f[i][mask] f[i][mask]只会从 f [ i − 1 ] [ . . ] f[i-1][..] f[i−1][..]转移而来并且 f [ i − 1 ] [ . . ] f[i-1][..] f[i−1][..]中的下标总是小于mask因此我们可以使用类似0-1背包的空间优化方法在遍历mask时从 2 1 0 − 1 2^10-1 210−1到1逆序遍历这样就只需要使用一个长度为 2 1 0 2^10 210的一维数组做状态转移了。
代码Python
#!/usr/bin/env python
from collections import Counter
from typing import List# Hard level
class Solution:# 状态压缩动态规划def numberOfGoodSubsets(self, nums: List[int]) - int:primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]mod 10 ** 9 7freq Counter(nums)f [0] * (1 len(primes))f[0] pow(2, freq[1], mod)for i, occ in freq.items():if i 1:continue# 检查 i 的每个质因数是否均不超过 1 个subset, x 0, icheck Truefor j, prime in enumerate(primes):if x % (prime * prime) 0:check Falsebreakif x % prime 0:subset | (1 j)if not check:continue# 动态规划for mask in range((1 len(primes)) - 1, 0, -1):if (mask subset) subset:f[mask] (f[mask] f[mask ^ subset] * occ) % modans sum(f[1:]) % modreturn ansif __name__ __main__:today Solution()nums list(map(int, input(nums ).strip().split(,)))print(today.numberOfGoodSubsets(nums))
复杂度分析
时间复杂度 O ( n C × O ( 2 π ( C ) ) O(n C × O(2π(C)) O(nC×O(2π(C))。其中 n 是数组 nums 的长度C 是 nums 元素的最大值在本题中 C 30π(x) 表示 ≤x 的质数的个数。 一共需要考虑 O ( C ) O(C) O(C)个数每个数需要 O ( 2 π ( C ) ) O(2π(C)) O(2π(C))的时间计算动态规划在初始时需要遍历一遍所有的数时间复杂度为 O ( n ) O(n) O(n)。 空间复杂度 O ( 2 π ( C ) ) O(2π(C)) O(2π(C))即为动态规划需要使用的空间。
