当前位置: 首页 > news >正文

网站 内容建设需要进一步加强长沙网站seo收费标准

网站 内容建设需要进一步加强,长沙网站seo收费标准,携创网,涿州网站开发1994.好子集的数目 题目描述解决方案:状态压缩动态规划代码:Python 题目来源:LeetCode 原文链接:https://mp.weixin.qq.com/s/myI7_ZwJM7kizrwUtWgAZQ 难度级别:困难 题目描述 给你一个整数数组 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 6=2×3 6 = 2 × 3 6 = 2 \times 3 6=2×3 和 3 = 3 。
  • [1, 4] 和 [4] 不是 子集,因为乘积分别为 4 = 2 × 2 4 = 2 \times 2 4=2×2 4 = 2 × 2 4 = 2 \times 2 4=2×2

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

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

示例1:

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

示例2:

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

提示:

  • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
  • 1 < = n u m s [ i ] < = 30 1 <= nums[i] <= 30 1<=nums[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[i1][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[i1][mask]+f[i1][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[i1][..]转移而来,并且 f [ i − 1 ] [ . . ] f[i-1][..] f[i1][..]中的下标总是小于mask,因此我们可以使用类似0-1背包的空间优化方法,在遍历mask时从 2 1 0 − 1 2^10-1 2101到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(n+C×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)),即为动态规划需要使用的空间。
http://www.zhongyajixie.com/news/3600.html

相关文章:

  • 购物网站排名2018网络推广培训班哪家好
  • 电子商务网站建设实训体会网络营销技能大赛优秀作品
  • 成都网站建设多少钱360浏览器网页版入口
  • 广东佛山新冠疫情最新消息湖北搜索引擎优化
  • 新疆乌鲁木齐做网站如何做一个自己的网页
  • 推广做网站电话网络推广发帖网站
  • 葫芦岛网站公司百度网址大全官方网站
  • 企业网站必须做可信认证吗目前引流最好的平台
  • 东莞大朗网站建设哪家口碑好深圳百度快速排名优化
  • 做百度手机网站排名怎么打广告宣传自己的产品
  • 泰安58同城租房郑州客串seo
  • 网站首页排名没了申请百度收录网址
  • 视频网站备案杭州网站设计
  • 网站优化之站外优化技巧谷歌广告上海有限公司官网
  • 网站开发可以用两种语言吗无锡网站推广公司
  • 邯郸建设网站百度推广服务
  • 企业网站建设与管理无锡哪里有做网站的
  • 网站建设方案调查分析报告培训机构
  • 爱站工具维护免费网站收录入口
  • 杭州网站建设V芯ee8888e媒体:北京不再公布疫情数据
  • 南通做公司网站百度联盟项目看广告挣钱
  • 泽国镇规划建设局网站权重查询工具
  • 网站制作东莞seo关键词怎么选择
  • 国外做黄漫的网站有哪些百度链接提交工具
  • flash企业网站源码爱站网挖掘工具
  • 柒零叁网温州论坛广州网站运营专注乐云seo
  • 免费建网站平台百度指数查询手机版
  • 59网站一起做网店普宁怎么做表格
  • 公司策划方案怎么做河南网站建设优化技术
  • 微网站开发第三方平台cba排名