Leetcode刷题详解——删除并获得点数
1. 题目链接:740. 删除并获得点数
2. 题目描述:
给你一个整数数组
nums
,你可以对它进行一些操作。每次操作中,选择任意一个
nums[i]
,删除它并获得nums[i]
的点数。之后,你必须删除 所有 等于nums[i] - 1
和nums[i] + 1
的元素。开始你拥有
0
个点数。返回你能通过这些操作获得的最大点数。示例 1:
输入:nums = [3,4,2] 输出:6 解释: 删除 4 获得 4 个点数,因此 3 也被删除。 之后,删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2:
输入:nums = [2,2,3,3,3,4] 输出:9 解释: 删除 3 获得 3 个点数,接着要删除两个 2 和 4 。 之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。 总共获得 9 个点数。
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
3. 解法(动态规划):
3.1 算法思路:
- 定义一个常量
N
,表示数组的最大值加1
。这里假设输入数组nums
中的元素都是非负整数,并且小于等于N-1
。 - 创建一个长度为N的整数数组
arr
,并初始化为0
。这个数组用于存储每个元素出现的次数。 - 遍历输入数组
nums
,将每个元素的值累加到对应的arr
数组位置上。这样可以统计每个元素出现的次数。 - 创建一个长度为N的整数向量
f
,用于存储动态规划的状态。这个向量f[i]
表示在考虑前i个元素时可以获得的最大收益。 - 创建一个引用
g
,指向向量f
,以便在后续计算中使用。 - 使用循环迭代计算状态转移方程。从i=1开始,依次计算f[i]和g[i]的值。
f[i] = g[i - 1] + arr[i]
:表示在考虑前i个元素时,可以选择当前元素或者不选择当前元素。g[i] = max(f[i - 1], g[i - 1])
:表示在考虑前i个元素时,可以选择当前元素或者不选择当前元素。
- 返回最终结果,即最大收益。可以通过比较
f[N - 1]
和g[N - 1]
的值来得到最大收益。
3.2 C++算法代码:
class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001; // 定义一个常量N,表示数组的最大值加1int arr[N] = {0}; // 创建一个长度为N的整数数组arr,并初始化为0for (auto x : nums) arr[x] += x; // 遍历输入数组nums,将每个元素的值累加到对应的arr数组位置上vector<int> f(N); // 创建一个长度为N的整数向量f,用于存储动态规划的状态auto g = f; // 创建一个引用g,指向向量f,以便在后续计算中使用for (int i = 1; i < N; i++) {f[i] = g[i - 1] + arr[i]; // 更新状态转移方程,计算当前位置的最大收益g[i] = max(f[i - 1], g[i - 1]); // 更新状态转移方程,计算当前位置的最大收益(不选择当前元素)}return max(f[N - 1], g[N - 1]); // 返回最终结果,即最大收益}
};
相关文章:

Leetcode刷题详解——删除并获得点数
1. 题目链接:740. 删除并获得点数 2. 题目描述: 给你一个整数数组 nums ,你可以对它进行一些操作。 每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] …...

HTTP四种请求方式,状态码,请求和响应报文
1.get请求 一般用于获取数据请求参数在URL后面请求参数的大小有限制 2.post请求 一般用于修改数据提交的数据在请求体中提交数据的大小没有限制 3.put请求 一般用于添加数据 4.delete请求 一般用于删除数据 5.一次完整的http请求过程 域名解析:使用DNS协议…...

Python - Wave2lip 环境配置与 Wave2lip x GFP-GAN 实战 [超详细!]
一.引言 前面介绍了 GFP-GAN 的原理与应用,其用于优化图像画质。本文关注另外一个相关的项目 Wave2lip,其可以通过人物视频与自定义音频进行适配,改变视频中人物的嘴型与音频对应。 二.Wave2Lip 简介 Wave2lip 研究 lip-syncing 以达到视频…...
2311rust,1.31版本更新
1.31.0稳定版 Rust1.31可能是最激动人心的版本! 使用Cargo创建一个新项目: cargo new foo以下是Cargo.toml的内容: [package] name "foo" version "0.1.0" authors ["名字"] edition "2018" //版本. [dependencies]在[package]…...

文心一言-情感关怀之旅
如何让LLM更有温度。 应用介绍...

下厨房网站月度最佳栏目菜谱数据获取及分析PLus
目录 概要 源数据获取 写Python代码爬取数据 Scala介绍与数据处理 1.Sacla介绍 2.Scala数据处理流程 数据可视化 最终大屏效果 小结 概要 本文的主题是获取下厨房网站月度最佳栏目近十年数据,最终进行数据清洗、处理后生成所需的数据库表,最终进…...

buildadmin+tp8表格操作(5)自定义组装搜索的查询
有时候我们会自定义组装一些数据,发送给后端,让后端来进行筛选,这里有一个示例 const onComSearchIdEq () > {// 展开公共搜索baTable.table.showComSearch true/*** 公共搜索表单赋值* 范围搜索有两个输入框,输入框绑定变量…...

企业级固态硬盘如何稳定运行?永铭固液混合铝电解电容来帮忙
企业级 固态硬盘 永铭固液混合铝电解电容 企业级固态硬盘(SSD)主要应用于互联网、云服务、金融和电信等客户的数据中心,企业级SSD具备更快传输速度、更大单盘容量、更高使用寿命以及更高的可靠性要求。 企业级固态硬盘的运行要求—固液混合电…...
【MISRA C 2012】Rule 4.2 不应该使用三连符
1. 规则1.1 原文1.2 分类 2. 关键描述3. 代码实例 1. 规则 1.1 原文 Rule 4.2 Trigraphs should not be used Category Advisory Analysis Decidable, Single Translation Unit Applies to C90, C99 1.2 分类 规则4.2:不应该使用三连符 Advisory建议类规范。 2…...

spring boot加mybatis puls实现,在新增/修改时,对某些字段进行处理,使用的@TableField()
1.先说场景,在对mysql数据库表数据插入或者更新时都得记录时间和用户id 传统实现有点繁琐,这里还可以封装一下公共方法。 2.解决方法: 2.1:使用aop切面编程(记录一下,有时间再攻克)。 2.2&…...

如何构建风险矩阵?3大注意事项
风险矩阵法(RMA)是确定威胁优先级别的最有效工具之一,可以帮助项目团队识别和评估项目中的风险,帮助项目团队对风险进行排序,清晰地展示风险的可能性和严重性,为项目团队制定风险管理策略提供依据。 如果没…...

SpringSecurity5|12.实现RememberMe 及 实现原理分析
security/day08 这个功能大家还熟悉么?我们在登录网站的时候,除了让你输入用户名和密码,还会有个勾选框: 记住我!!!不是让大家记住我哈。 值得一提的是,Spring Security 也提供了这个…...

持续集成交付CICD:Jenkins Sharedlibrary 共享库
目录 一、理论 1.共享库 2.共享库配置 3.使用共享库 4.共享库扩展 二、实验 1.连接共享库 2.使用共享库 三、问题 1.路径报错 2.readJSON 报错 一、理论 1.共享库 (1)概念 1)共享库这并不是一个全新的概念,其实在编…...

Linux--网络编程
一、网络编程概述1.进程间通信: 1)进程间通信的方式有**:管道,消息队列,共享内存,信号,信号量这么集中 2)特点:依赖于linux内核,基本是通过内核来实现应用层…...
数据结构 并查集
作用 快速的处理以下问题:【近乎O(1)的时间完成】 1.将两个集合合并 2.询问两个元素是否在一个集合中 用树的形式维护集合 基本原理 每一个集合用一棵树表示 每一个集合的编号就是根结点的编号,对于每一个结点,都存储其父结点…...
算法通关村第十六关黄金挑战——求滑动窗口中的最大值(滑动窗口与堆方法、双端队列法和直接比较法)
大家好,我是怒码少年小码。 今天这篇就讲一道题目,不难😎,但是一定要学会自己思考。 滑动窗口最大值 LeetCode 239:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。…...

常见树种(贵州省):009楠木、樟木、桂木种类
摘要:本专栏树种介绍图片来源于PPBC中国植物图像库(下附网址),本文整理仅做交流学习使用,同时便于查找,如有侵权请联系删除。 图片网址:PPBC中国植物图像库——最大的植物分类图片库 一、楠木 …...

全志H616开发版
开发板介绍: 二、开发板刷机 SDFormatter TF卡的格式化工具、Win32Diskimager 刷机工具 刷机镜像为:Orangepizero2_2.2.0_ubuntu_bionic_desktop_linux4.9.170.img 使用MobaXterm_Personal_20.3连接使用 网络配置:nmcli dev wifi 命令接入网…...

【Spring boot】RedisTemplate中String、Hash、List设置过期时间
文章目录 前言Redis中String设置时间的方法Redis中Hash和List设置时间的方法Redis中Hash的put、putAll、putIfAbsent区别 前言 时间类型:TimeUnit import java.util.concurrent.TimeUnit;TimeUnit.SECONDS:秒 TimeUnit.MINUTES:分 TimeUnit.HOURS&…...

Nosql之redis概述及基本操作
关系数据库与非关系型数据库概述 关系型数据库 关系型数据库是一个结构化的数据库,创建在关系模型(二维表格模型)基础上,一般面向于记录。SQL语句(标准数据查询语言)就是一种基于关系型数据库的语言,用于执行对关系型…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...