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

力扣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. 删除并获得点数

动态规划 思路&#xff1a; 选择元素 x&#xff0c;获得其点数&#xff0c;删除 x 1 和 x - 1&#xff0c;则其他的 x 的点数也会被获得&#xff1b;可以将数组转换成一个有序 map&#xff0c;key 为 x&#xff0c; value 为对应所有 x 的和&#xff1b;则问题转换成了不能同…...

spring和springboot的区别

在当今的软件开发领域&#xff0c;Spring和Spring Boot无疑是Java开发者最常用的框架之一。尽管它们都源于Spring项目&#xff0c;但它们在设计和使用上有很大的不同。本文将深入探讨Spring和Spring Boot之间的主要区别&#xff0c;以及为什么有时候选择其中一个而不是另一个是…...

imgaug库图像增强指南(35):【iaa.Fog】——轻松创建自然雾气场景

引言 在深度学习和计算机视觉的世界里&#xff0c;数据是模型训练的基石&#xff0c;其质量与数量直接影响着模型的性能。然而&#xff0c;获取大量高质量的标注数据往往需要耗费大量的时间和资源。正因如此&#xff0c;数据增强技术应运而生&#xff0c;成为了解决这一问题的…...

网络安全--防御保护02

第二天重要的一个点是区域这个概念 防火墙的主要职责在于控制和防护---安全策略---防火墙可以根据安全策略来抓取流量之后做出对应的动作 防火墙的分类&#xff1a; 单一主机防火墙&#xff1a;专门有设备作为防火墙 路由集成&#xff1a;核心设备&#xff0c;可流量转发 分…...

UE5 C++学习笔记 常用宏的再次理解

1.随意创建一个类&#xff0c;他都有UCLASS()。GENERATED_BODY()这样的默认的宏。 UCLASS() 告知虚幻引擎生成类的反射数据。类必须派生自UObject. &#xff08;告诉引擎我是从远古大帝UObject中&#xff0c;继承而来&#xff0c;我们是一家人&#xff0c;只是我进化了其他功能…...

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中&#xff0c;构造函数是一种特殊类型的方法&#xff0c;用于创建并初始化一个新的对象。它通常使用 new 关键字来调用&#xff0c;并且通常以大写字母开头&#xff0c;以与其他非构造函数区分开来。 一个简单的构造函数示例&#xff1a; function Person(name,…...

[小程序]页面事件

一、下拉刷新 1.开启和配置 小程序中开启下拉刷新的方式有两种&#xff1a; ①全局开启下来刷新 在app.json的window节点中&#xff0c;设置enablePullDownRefresh设为ture。 ②局部开启下来刷新 在页面对应的json文件的的window节点中&#xff0c;设置enablePullDownRefresh设…...

vue echarts地图

下载地图文件&#xff1a; DataV.GeoAtlas地理小工具系列 范围选择器右侧行政区划范围中输入需要选择的省份或地市&#xff0c;选择自己想要的数据格式&#xff0c;这里选择了geojson格式&#xff0c;点右侧的蓝色按钮复制到浏览器地址栏中&#xff0c;打开的geojson文件内容…...

v38.Switch语句

1.Switch语句可以替代if-else语句 2.具体使用 Switch&#xff08;expression&#xff09; &#xff5b; case label&#xff1a;...... &#xff5d; ①将x与case后的label 进行比较&#xff1b; ②注意后面有冒号&#xff1b; ③从上往下开始检查case&#xff1b; ④如果…...

如何进行产品的人机交互设计?

产品的人机交互设计是指通过用户界面和用户体验设计来优化产品与用户之间的交互过程&#xff0c;从而提高产品的易用性、可用性和用户满意度。人机交互设计需要考虑用户的需求、行为模式、心理感受以及技术实现&#xff0c;下面我将介绍如何进行产品的人机交互设计。 首先&…...

【ARMv8M Cortex-M33 系列 7.3 -- EXC_RETURN 与 LR 及 PC 的关系详细介绍】

请阅读【嵌入式开发学习必备专栏 之 ARM Cortex-Mx专栏】 文章目录 背景EXC_RETURN 与 LR 及 PCcortex-m33 从异常返回后 各个寄存器出战顺序ARM 栈增长方式 背景 接着上篇文章&#xff1a;【ARMv8M Cortex-M33 系列 7.2 – HardFault 问题定位 1】&#xff0c;后面定位到是在…...

Linux之权限(内容详细,细节满满)

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 Linux 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力 目录 一.前言 二.权限修改的两种方法 …...

了解云工作负载保护:技术和最佳实践

云工作负载是指云环境中的应用程序或存储元素&#xff0c;无论是公共云、私有云还是混合云。每个云工作负载都使用云的资源&#xff0c;包括计算、网络和存储。 云工作负载可以多种多样&#xff0c;例如运行应用程序、数据库或托管网站。它们可以是静态的或动态的&#xff0c;…...

【Godot4自学手册】第三节设置主人公的动画

继续&#xff0c;今天是第三节&#xff0c;我们主要实现主人公的动画效果&#xff0c;共有两种方法实现动画效果 一、通过AnimationPlayer节点实现动画效果 我们首先在player场景下&#xff0c;player节点下添加AnimationPlayer节点&#xff0c;添加方法是&#xff0c;在play…...

excel学习1

直接ctrl cctrl v会报错位移选择粘贴时用123那个数字粘贴而不是ctrl V 只要结果不要公式 上面复制的为数值这里是复制的公式他们两个不一样 这个方法太麻烦了直接用格式刷&#xff0c;选择一个区域一个单元格&#xff0c;不要选择多个一刷就出来了 第一个计算后向下拖就行了&…...

裁员致谷歌中国籍程序员身亡,技术变革下裁员对程序员的影响有多大

裁员&#xff0c;这是一个令无数人心悸的词汇。在瞬息万变的科技时代&#xff0c;裁员仿佛成了不少公司应对困境的“救命稻草”。然而&#xff0c;在这背后&#xff0c;每一名员工&#xff0c;每一个程序员&#xff0c;他们所承担的代价&#xff0c;又有多少人能够深切地理解&a…...

MybatisPlus的主键ID生成策略和公共字段自动填充的使用及注意事项

主键策略&#xff08;ID自动生成&#xff09; 以下是MyBatis-Plus中常见的几种主键生成策略及其对应的枚举值&#xff08;3.3.0之前的版本&#xff09;&#xff1a; 主键生成策略枚举值数据库自增IdType.AUTO用户输入IdType.INPUT分布式全局唯一IDIdType.ID_WORKER分布式全局…...

【GitHub项目推荐--微软开源的可视化工具】【转载】

说到数据可视化&#xff0c;大家都很熟悉了&#xff0c;设计师、数据分析师、数据科学家等&#xff0c;都需要用各种方式各种途径做着数据可视化的工作.....当然许多程序员在工作中有时也需要用到一些数据可视化工具&#xff0c;如果工具用得好&#xff0c;就可以把原本枯燥凌乱…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...