【C++动态规划 状态压缩】2597. 美丽子集的数目|2033
本文涉及知识点
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] 表示(1<<j)&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|(1<<i)] = true
单个状态时间复杂度:O(n),总时间复杂度:O(2nn)
动态规划的初始化
dp[0]=true,其它全为false。
动态规划的返回值
dp中true的数量-1。
代码
核心代码
class Solution {public:int beautifulSubsets(vector<int>& nums, int k) {const int N = nums.size();const int MC = 1 << N;vector<int> 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);}}}vector<bool> 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 },k=2;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[i<<i]
枚举后续状态:
j1= i&-i j2 = i-j1
如果v[j1]&j2 则i是非法状态。否则dp[i] = dp[j2]
class Solution {public:int beautifulSubsets(vector<int>& nums, int k) {const int N = nums.size();const int MC = 1 << N;vector<int> v(MC);for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) {if (abs(nums[i] - nums[j]) == k) {v[1<<i] |= (1 << j);}}}vector<bool> 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] = (0==j2)||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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++动态规划 状态压缩】2597. 美丽子集的数目|2033
本文涉及知识点 C动态规划 LeetCode2597. 美丽子集的数目 给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 如果 nums 的子集中,任意两个整数的绝对差均不等于 k ,则认为该子数组是一个 美丽 子集。 返回数组 nums 中 非空 且 美丽 的子集数目。…...
前端-Rollup
Rollup 是一个用于 JavaScript 的模块打包工具,它将小的代码片段编译成更大、更复杂的代码,例如库或应用程序。它使用 JavaScript 的 ES6 版本中包含的新标准化代码模块格式,而不是以前的 CommonJS 和 AMD 等特殊解决方案。ES 模块允许你自由…...
20【变量的深度理解】
一说起变量,懂点编程的都知道,但是在理解上可能还不够深 变量就是存储空间,电脑上的存储空间有永久(硬盘)和临时(内存条)两种,永久数据重启电脑后依旧存在,临时数据只…...
大数据学习之Kafka消息队列、Spark分布式计算框架一
Kafka消息队列 章节一.kafka入门 4.kafka入门_消息队列两种模式 5.kafka入门_架构相关名词 Kafka 入门 _ 架构相关名词 事件 记录了世界或您的业务中 “ 发生了某事 ” 的事实。在文档中 也称为记录或消息。当您向 Kafka 读取或写入数据时,您以事件的 形式执行…...
基于Flask的旅游系统的设计与实现
【Flask】基于Flask的旅游系统的设计与实现(完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统采用Python作为后端开发语言,结合前端Bootstrap框架,为用户提供了丰富…...
“AI视频智能分析系统:让每一帧视频都充满智慧
嘿,大家好!今天咱们来聊聊一个特别厉害的东西——AI视频智能分析系统。想象一下,如果你有一个超级聪明的“视频助手”,它不仅能自动识别视频中的各种元素,还能根据内容生成详细的分析报告,是不是感觉特别酷…...
算法随笔_31:移动零
上一篇:算法随笔_30: 去除重复字母-CSDN博客 题目描述如下: 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums [0,1,…...
改进候鸟优化算法之二:基于混沌映射的候鸟优化算法(MBO-CM)
基于混沌映射的候鸟优化算法(Migrating Birds Optimization based on Chaotic Mapping,MBO-CM)是一种结合了混沌映射与候鸟优化算法(Migrating Birds Optimization,MBO)的优化方法。 一、候鸟优化算法(MBO)简介 候鸟优化算法是一种自然启发的元启发式算法,由Duman等人…...
在Docker 容器中安装 Oracle 19c
在 Docker 容器中安装 Oracle 19c 是可行的,但它相较于其他数据库(如 MySQL、PostgreSQL 等)会复杂一些,因为 Oracle 数据库有一些特定的要求,如操作系统和库的依赖,以及许可证问题。 不过,Ora…...
使用Avalonia UI实现DataGrid
1.Avalonia中的DataGrid的使用 DataGrid 是客户端 UI 中一个非常重要的控件。在 Avalonia 中,DataGrid 是一个独立的包 Avalonia.Controls.DataGrid,因此需要单独通过 NuGet 安装。接下来,将介绍如何安装和使用 DataGrid 控件。 2.安装 Dat…...
MySQL中的读锁与写锁:概念与作用深度剖析
MySQL中的读锁与写锁:概念与作用深度剖析 在MySQL数据库的并发控制机制中,读锁和写锁起着至关重要的作用。它们是确保数据在多用户环境下能够正确、安全地被访问和修改的关键工具。 一、读锁(共享锁)概念 读锁,也称为…...
Dest1ny漏洞库:用友 U8 Cloud ReleaseRepMngAction SQL 注入漏洞(CNVD-2024-33023)
大家好,今天是Dest1ny漏洞库的专题!! 会时不时发送新的漏洞资讯!! 大家多多关注,多多点赞!!! 0x01 产品简介 用友U8 Cloud是用友推出的新一代云ERP,主要聚…...
python学opencv|读取图像(四十九)原理探究:使用cv2.bitwise()系列函数实现图像按位运算
【0】基础定义 按位与运算:两个等长度二进制数上下对齐,全1取1,其余取0。 按位或运算:两个等长度二进制数上下对齐,有1取1,其余取0。 按位异或运算: 两个等长度二进制数上下对齐,相…...
【面试】【编程范式总结】面向对象编程(OOP)、函数式编程(FP)和响应式编程(RP)
一、编程范式总结 编程范式是指开发软件时采用的一种方法论或思维方式,主要包括面向对象编程(OOP)、**函数式编程(FP)和响应式编程(RP)**等。这些范式的不同特性和适用场景,帮助开发…...
创建要素图层和表视图
操作方法: 下面按照步骤学习如何使用Make Feature Layer和Make Table View工具 1.在arcmap中打开活动地图文档 2.导入arcpy模块 3.设置工作空间 arcpy.env.workspace "<>" 4.使用try语句,使用Make Feature Layer工具创建内存副本 try:flayer arcpy.Ma…...
51单片机入门_01_单片机(MCU)概述(使用STC89C52芯片;使用到的硬件及课程安排)
文章目录 1. 什么是单片机1.1 微型计算机的组成1.2 微型计算机的应用形态1.3 单板微型计算机1.4 单片机(MCU)1.4.1 单片机内部结构1.4.2 单片机应用系统的组成 1.5 80C51单片机系列1.5.1 STC公司的51单片机1.5.1 STC公司单片机的命名规则 2. 单片机的特点及应用领域2.1 单片机的…...
万物皆有联系:驼鸟和布什
布什?一块布十块钱吗?不是,大家都知道,美国有两个总统,叫老布什和小布什,因为两个布什总统(父子俩),大家就这么叫来着,目的是为了好区分。 布什总统的布什&a…...
【最后203篇系列】007 使用APS搭建本地定时任务
说明 最大的好处是方便。 其实所有任务的源头,应该都是通过定时的方式,在每个时隙发起轮询。当然在任务的后续传递中,可以通过CallBack或者WebHook的方式,以事件的形态进行。这样可以避免长任务执行的过程中进行等待和轮询。 总结…...
go gin配置air
一、依赖下载 安装最新,且在你工作区下进行安装,我的是D:/GO是我的工作区,所有项目都在目录下的src, go install github.com/air-verse/airlatest 如果出现类似报错: 将图中第三行 github.com/air-verse/air 替换最…...
Java定时任务实现方案(五)——时间轮
时间轮 这篇笔记,我们要来介绍实现Java定时任务的第五个方案,使用时间轮,以及该方案的优点和缺点。 时间轮是一种高效的定时任务调度算法,特别适用于大量定时任务的场景。时间轮的定时任务实现,可以使用DelayQueue…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
