网站文章只被收录网站首页,WordPress 空间模板,做企业网站cms,大学生网页设计作品本文涉及知识点
C动态规划
LeetCode2597. 美丽子集的数目
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 如果 nums 的子集中#xff0c;任意两个整数的绝对差均不等于 k #xff0c;则认为该子数组是一个 美丽 子集。 返回数组 nums 中 非空 且 美丽 的子集数目。…本文涉及知识点
C动态规划
LeetCode2597. 美丽子集的数目
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 如果 nums 的子集中任意两个整数的绝对差均不等于 k 则认为该子数组是一个 美丽 子集。 返回数组 nums 中 非空 且 美丽 的子集数目。 nums 的子集定义为可以经由 nums 删除某些元素也可能不删除得到的一个数组。只有在删除元素时选择的索引不同的情况下两个子集才会被视作是不同的子集。 示例 1 输入nums [2,4,6], k 2 输出4 解释数组 nums 中的美丽子集有[2], [4], [6], [2, 6] 。 可以证明数组 [2,4,6] 中只存在 4 个美丽子集。 示例 2 输入nums [1], k 1 输出1 解释数组 nums 中的美丽数组有[1] 。 可以证明数组 [1] 中只存在 1 个美丽子集。 提示 1 nums.length 20 1 nums[i], k 1000
动态规划状态压缩
动态规划的状态表示
dp[mask] 表示(1j)mask的数字已经使用是否是完美子集。空间复杂度O(2nn)。
动态规划的填表顺序
mask从0到大
动态规划的转移方程
v[i]的如下位为1其它为0:a第i位。 b,第j位 abs(nums[j]-nums[i])k。 !dp[mask]忽略。 if(v[i]mask)则忽略i。 dp[mask|(1i)] true 单个状态时间复杂度O(n)总时间复杂度O(2nn)
动态规划的初始化
dp[0]true其它全为false。
动态规划的返回值
dp中true的数量-1。
代码
核心代码
class Solution {public:int beautifulSubsets(vectorint nums, int k) {const int N nums.size();const int MC 1 N;vectorint v(N);for (int i 0; i N; i) {v[i] 1 i;for (int j 0; j N; j) {if (abs(nums[i] - nums[j]) k) {v[i] | (1 j);}}}vectorbool dp(MC);for (int i 0; i N; i) {dp[1 i] true;}for (int i 0; i MC; i) {if (!dp[i])continue;for (int j 0; j N; j) {if (i v[j])continue;dp[i | (1 j)] true;}}const int ans count(dp.begin(), dp.end(), true);return ans;}};单元测试 int k;TEST_METHOD(TestMethod11){nums { 2,4,6 },k2;auto res Solution().beautifulSubsets(nums, k);AssertEx(4, res);}TEST_METHOD(TestMethod12){nums { 1 }, k 1;auto res Solution().beautifulSubsets(nums, k);AssertEx(1, res);}优化
v[i] 改成v[ii] 枚举后续状态 j1 i-i j2 i-j1 如果v[j1]j2 则i是非法状态。否则dp[i] dp[j2]
class Solution {public:int beautifulSubsets(vectorint nums, int k) {const int N nums.size();const int MC 1 N;vectorint v(MC);for (int i 0; i N; i) { for (int j 0; j N; j) {if (abs(nums[i] - nums[j]) k) {v[1i] | (1 j);}}}vectorbool dp(MC);for (int i 0; i N; i) {dp[1 i] true;}for (int i 1; i MC; i) {const int j1 i -i;const int j2 i - j1;if (j2 v[j1])continue;dp[i] (0j2)||dp[j2];}const int ans count(dp.begin(), dp.end(), true);return ans;}};扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
