当前位置: 首页 > 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;就可以把原本枯燥凌乱…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...