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

Leetcode刷题详解——删除并获得点数

1. 题目链接:740. 删除并获得点数

2. 题目描述:

给你一个整数数组 nums ,你可以对它进行一些操作。

每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1nums[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 算法思路:

  1. 定义一个常量N,表示数组的最大值加1。这里假设输入数组nums中的元素都是非负整数,并且小于等于N-1
  2. 创建一个长度为N的整数数组arr,并初始化为0。这个数组用于存储每个元素出现的次数。
  3. 遍历输入数组nums,将每个元素的值累加到对应的arr数组位置上。这样可以统计每个元素出现的次数。
  4. 创建一个长度为N的整数向量f,用于存储动态规划的状态。这个向量f[i]表示在考虑前i个元素时可以获得的最大收益。
  5. 创建一个引用g,指向向量f,以便在后续计算中使用。
  6. 使用循环迭代计算状态转移方程。从i=1开始,依次计算f[i]和g[i]的值。
    • f[i] = g[i - 1] + arr[i]:表示在考虑前i个元素时,可以选择当前元素或者不选择当前元素。
    • g[i] = max(f[i - 1], g[i - 1]):表示在考虑前i个元素时,可以选择当前元素或者不选择当前元素。
  7. 返回最终结果,即最大收益。可以通过比较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. 题目链接&#xff1a;740. 删除并获得点数 2. 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;你可以对它进行一些操作。 每次操作中&#xff0c;选择任意一个 nums[i] &#xff0c;删除它并获得 nums[i] 的点数。之后&#xff0c;你必须删除 所有 等于 nums[i] …...

HTTP四种请求方式,状态码,请求和响应报文

1.get请求 一般用于获取数据请求参数在URL后面请求参数的大小有限制 2.post请求 一般用于修改数据提交的数据在请求体中提交数据的大小没有限制 3.put请求 一般用于添加数据 4.delete请求 一般用于删除数据 5.一次完整的http请求过程 域名解析&#xff1a;使用DNS协议…...

Python - Wave2lip 环境配置与 Wave2lip x GFP-GAN 实战 [超详细!]

一.引言 前面介绍了 GFP-GAN 的原理与应用&#xff0c;其用于优化图像画质。本文关注另外一个相关的项目 Wave2lip&#xff0c;其可以通过人物视频与自定义音频进行适配&#xff0c;改变视频中人物的嘴型与音频对应。 二.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数据处理流程 数据可视化 最终大屏效果 小结 概要 本文的主题是获取下厨房网站月度最佳栏目近十年数据&#xff0c;最终进行数据清洗、处理后生成所需的数据库表&#xff0c;最终进…...

buildadmin+tp8表格操作(5)自定义组装搜索的查询

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

企业级固态硬盘如何稳定运行?永铭固液混合铝电解电容来帮忙

企业级 固态硬盘 永铭固液混合铝电解电容 企业级固态硬盘&#xff08;SSD&#xff09;主要应用于互联网、云服务、金融和电信等客户的数据中心&#xff0c;企业级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&#xff1a;不应该使用三连符 Advisory建议类规范。 2…...

spring boot加mybatis puls实现,在新增/修改时,对某些字段进行处理,使用的@TableField()

1.先说场景&#xff0c;在对mysql数据库表数据插入或者更新时都得记录时间和用户id 传统实现有点繁琐&#xff0c;这里还可以封装一下公共方法。 2.解决方法&#xff1a; 2.1&#xff1a;使用aop切面编程&#xff08;记录一下&#xff0c;有时间再攻克&#xff09;。 2.2&…...

如何构建风险矩阵?3大注意事项

风险矩阵法&#xff08;RMA&#xff09;是确定威胁优先级别的最有效工具之一&#xff0c;可以帮助项目团队识别和评估项目中的风险&#xff0c;帮助项目团队对风险进行排序&#xff0c;清晰地展示风险的可能性和严重性&#xff0c;为项目团队制定风险管理策略提供依据。 如果没…...

SpringSecurity5|12.实现RememberMe 及 实现原理分析

security/day08 这个功能大家还熟悉么&#xff1f;我们在登录网站的时候&#xff0c;除了让你输入用户名和密码&#xff0c;还会有个勾选框&#xff1a; 记住我&#xff01;&#xff01;&#xff01;不是让大家记住我哈。 值得一提的是&#xff0c;Spring Security 也提供了这个…...

持续集成交付CICD:Jenkins Sharedlibrary 共享库

目录 一、理论 1.共享库 2.共享库配置 3.使用共享库 4.共享库扩展 二、实验 1.连接共享库 2.使用共享库 三、问题 1.路径报错 2.readJSON 报错 一、理论 1.共享库 &#xff08;1&#xff09;概念 1&#xff09;共享库这并不是一个全新的概念&#xff0c;其实在编…...

Linux--网络编程

一、网络编程概述1.进程间通信&#xff1a; 1&#xff09;进程间通信的方式有**&#xff1a;管道&#xff0c;消息队列&#xff0c;共享内存&#xff0c;信号&#xff0c;信号量这么集中 2&#xff09;特点&#xff1a;依赖于linux内核&#xff0c;基本是通过内核来实现应用层…...

数据结构 并查集

作用 快速的处理以下问题&#xff1a;【近乎O(1)的时间完成】 1.将两个集合合并 2.询问两个元素是否在一个集合中 用树的形式维护集合 基本原理 每一个集合用一棵树表示 每一个集合的编号就是根结点的编号&#xff0c;对于每一个结点&#xff0c;都存储其父结点&#xf…...

算法通关村第十六关黄金挑战——求滑动窗口中的最大值(滑动窗口与堆方法、双端队列法和直接比较法)

大家好&#xff0c;我是怒码少年小码。 今天这篇就讲一道题目&#xff0c;不难&#x1f60e;&#xff0c;但是一定要学会自己思考。 滑动窗口最大值 LeetCode 239&#xff1a;给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。…...

常见树种(贵州省):009楠木、樟木、桂木种类

摘要&#xff1a;本专栏树种介绍图片来源于PPBC中国植物图像库&#xff08;下附网址&#xff09;&#xff0c;本文整理仅做交流学习使用&#xff0c;同时便于查找&#xff0c;如有侵权请联系删除。 图片网址&#xff1a;PPBC中国植物图像库——最大的植物分类图片库 一、楠木 …...

全志H616开发版

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

【Spring boot】RedisTemplate中String、Hash、List设置过期时间

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

Nosql之redis概述及基本操作

关系数据库与非关系型数据库概述 关系型数据库 关系型数据库是一个结构化的数据库&#xff0c;创建在关系模型&#xff08;二维表格模型&#xff09;基础上&#xff0c;一般面向于记录。SQL语句(标准数据查询语言)就是一种基于关系型数据库的语言&#xff0c;用于执行对关系型…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...