力扣740. 删除并获得点数
动态规划
- 思路:
- 选择元素 x,获得其点数,删除 x + 1 和 x - 1,则其他的 x 的点数也会被获得;
- 可以将数组转换成一个有序 map,key 为 x, value 为对应所有 x 的和;
- 则问题转换成了不能同时获得相邻两个房间的金币并能获得最大收益问题:力扣198. 打家劫舍;
- 动态规划状态转移方程 dp[i] 跟之前两个状态相关,可以使用滚动数组的方式,减少空间复杂度:
- dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1])
- dp0 -> dp[i - 2], dp0' = dp[i - 1]
- dp1 -> dp[i - 1], dp1' = dp[i]
- 在使用一个临时变量:
- tmp = dp[i - 1] -> dp1
- dp[i] | -> dp1' <- dp1 = std::max(dp[i - 2] -> dp0 + nums[i], dp[i - 1] -> dp1)
- dp[i - 1] | -> dp1 -> tmp
class Solution {
public:int deleteAndEarn(vector<int>& nums) {int maxVal = 0;for (int val : nums) {maxVal = std::max(maxVal, val);}std::vector<int> sum(maxVal + 1);for (int val : nums) {sum[val] += val;}return rob(sum);}private:int rob(std::vector<int>& nums) {int size = nums.size();if (size == 0) {return 0;}if (size == 1) {return nums[0];}int dp0 = nums[0];int dp1 = std::max(dp0, nums[1]);for (int i = 2; i < size; ++i) {int tmp = dp1;dp1 = std::max(dp0 + nums[i], dp1);dp0 = tmp;}return dp1;}
};
——————————————————————

相关文章:
力扣740. 删除并获得点数
动态规划 思路: 选择元素 x,获得其点数,删除 x 1 和 x - 1,则其他的 x 的点数也会被获得;可以将数组转换成一个有序 map,key 为 x, value 为对应所有 x 的和;则问题转换成了不能同…...
spring和springboot的区别
在当今的软件开发领域,Spring和Spring Boot无疑是Java开发者最常用的框架之一。尽管它们都源于Spring项目,但它们在设计和使用上有很大的不同。本文将深入探讨Spring和Spring Boot之间的主要区别,以及为什么有时候选择其中一个而不是另一个是…...
imgaug库图像增强指南(35):【iaa.Fog】——轻松创建自然雾气场景
引言 在深度学习和计算机视觉的世界里,数据是模型训练的基石,其质量与数量直接影响着模型的性能。然而,获取大量高质量的标注数据往往需要耗费大量的时间和资源。正因如此,数据增强技术应运而生,成为了解决这一问题的…...
网络安全--防御保护02
第二天重要的一个点是区域这个概念 防火墙的主要职责在于控制和防护---安全策略---防火墙可以根据安全策略来抓取流量之后做出对应的动作 防火墙的分类: 单一主机防火墙:专门有设备作为防火墙 路由集成:核心设备,可流量转发 分…...
UE5 C++学习笔记 常用宏的再次理解
1.随意创建一个类,他都有UCLASS()。GENERATED_BODY()这样的默认的宏。 UCLASS() 告知虚幻引擎生成类的反射数据。类必须派生自UObject. (告诉引擎我是从远古大帝UObject中,继承而来,我们是一家人,只是我进化了其他功能…...
SpringBoot整合SSE
目录 1.SseController2. SseServiceSseServiceSseServiceImpl 3.SendMessageTask4.将定时任务加入启动类5.参考资料 1.SseController Slf4j RestController RequestMapping("sse") public class SseController {Autowiredprivate SseService sseService;RequestMappi…...
mysql-进阶篇
文章目录 存储引擎MySQL体系结构相关操作 存储引擎特点InnoDBInnoDB 逻辑存储结构 MyISAMMemory三个存储引擎之间的区别存储引擎的选择 索引1. 索引结构B-TreeB-Tree (多路平衡查找树)B-Tree演变过程 BTree与 B-Tree 的区别BTree演变过程 Hash 2.索引分类3.索引语法演示 4.SQL性…...
Js中的构造函数
在JavaScript中,构造函数是一种特殊类型的方法,用于创建并初始化一个新的对象。它通常使用 new 关键字来调用,并且通常以大写字母开头,以与其他非构造函数区分开来。 一个简单的构造函数示例: function Person(name,…...
[小程序]页面事件
一、下拉刷新 1.开启和配置 小程序中开启下拉刷新的方式有两种: ①全局开启下来刷新 在app.json的window节点中,设置enablePullDownRefresh设为ture。 ②局部开启下来刷新 在页面对应的json文件的的window节点中,设置enablePullDownRefresh设…...
vue echarts地图
下载地图文件: DataV.GeoAtlas地理小工具系列 范围选择器右侧行政区划范围中输入需要选择的省份或地市,选择自己想要的数据格式,这里选择了geojson格式,点右侧的蓝色按钮复制到浏览器地址栏中,打开的geojson文件内容…...
v38.Switch语句
1.Switch语句可以替代if-else语句 2.具体使用 Switch(expression) { case label:...... } ①将x与case后的label 进行比较; ②注意后面有冒号; ③从上往下开始检查case; ④如果…...
如何进行产品的人机交互设计?
产品的人机交互设计是指通过用户界面和用户体验设计来优化产品与用户之间的交互过程,从而提高产品的易用性、可用性和用户满意度。人机交互设计需要考虑用户的需求、行为模式、心理感受以及技术实现,下面我将介绍如何进行产品的人机交互设计。 首先&…...
【ARMv8M Cortex-M33 系列 7.3 -- EXC_RETURN 与 LR 及 PC 的关系详细介绍】
请阅读【嵌入式开发学习必备专栏 之 ARM Cortex-Mx专栏】 文章目录 背景EXC_RETURN 与 LR 及 PCcortex-m33 从异常返回后 各个寄存器出战顺序ARM 栈增长方式 背景 接着上篇文章:【ARMv8M Cortex-M33 系列 7.2 – HardFault 问题定位 1】,后面定位到是在…...
Linux之权限(内容详细,细节满满)
个人主页:点我进入主页 专栏分类:C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 Linux 欢迎大家点赞,评论,收藏。 一起努力 目录 一.前言 二.权限修改的两种方法 …...
了解云工作负载保护:技术和最佳实践
云工作负载是指云环境中的应用程序或存储元素,无论是公共云、私有云还是混合云。每个云工作负载都使用云的资源,包括计算、网络和存储。 云工作负载可以多种多样,例如运行应用程序、数据库或托管网站。它们可以是静态的或动态的,…...
【Godot4自学手册】第三节设置主人公的动画
继续,今天是第三节,我们主要实现主人公的动画效果,共有两种方法实现动画效果 一、通过AnimationPlayer节点实现动画效果 我们首先在player场景下,player节点下添加AnimationPlayer节点,添加方法是,在play…...
excel学习1
直接ctrl cctrl v会报错位移选择粘贴时用123那个数字粘贴而不是ctrl V 只要结果不要公式 上面复制的为数值这里是复制的公式他们两个不一样 这个方法太麻烦了直接用格式刷,选择一个区域一个单元格,不要选择多个一刷就出来了 第一个计算后向下拖就行了&…...
裁员致谷歌中国籍程序员身亡,技术变革下裁员对程序员的影响有多大
裁员,这是一个令无数人心悸的词汇。在瞬息万变的科技时代,裁员仿佛成了不少公司应对困境的“救命稻草”。然而,在这背后,每一名员工,每一个程序员,他们所承担的代价,又有多少人能够深切地理解&a…...
MybatisPlus的主键ID生成策略和公共字段自动填充的使用及注意事项
主键策略(ID自动生成) 以下是MyBatis-Plus中常见的几种主键生成策略及其对应的枚举值(3.3.0之前的版本): 主键生成策略枚举值数据库自增IdType.AUTO用户输入IdType.INPUT分布式全局唯一IDIdType.ID_WORKER分布式全局…...
【GitHub项目推荐--微软开源的可视化工具】【转载】
说到数据可视化,大家都很熟悉了,设计师、数据分析师、数据科学家等,都需要用各种方式各种途径做着数据可视化的工作.....当然许多程序员在工作中有时也需要用到一些数据可视化工具,如果工具用得好,就可以把原本枯燥凌乱…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
VASP软件在第一性原理计算中的应用-测试GO
VASP软件在第一性原理计算中的应用 VASP是由维也纳大学Hafner小组开发的一款功能强大的第一性原理计算软件,广泛应用于材料科学、凝聚态物理、化学和纳米技术等领域。 VASP的核心功能与应用 1. 电子结构计算 VASP最突出的功能是进行高精度的电子结构计算ÿ…...
