力扣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;
    }
};

——————————————————————

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/340739.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

中间件-缓存、索引、日志

文章目录 缓存中间件本地缓存中间件分布式缓存中间件全文索引中间件分布式日志中间件小结 缓存中间件 缓存是性能优化的一大利器 我们先一起来看一个用户中心查询用户信息的基本流程 这时候&#xff0c;如果查找用户信息这个 API 的调用频率增加&#xff0c;并且在整个业务流…

怎么使用【jmeter正则表达式提取器】解决返回值作参数的问题

前言 我们在使用jmeter做接口测试时&#xff0c;常常会碰到上个接口的返回值会作为下个接口的参数来进行请求。这时候&#xff0c;就需要用到jmeter的正则表达式提取器了。 添加正则表达式提取器步骤&#xff1a; “选择要添加提取器的接口右键”——add——post processors—…

线程池--JAVA

虽然线程是轻量级进程&#xff0c;但是如果当创建和销毁的的频率非常之高&#xff0c;那么它也就会消耗很多的资源。 而线程池就是用来优化线程频繁创建和销毁的场景&#xff0c;减少线程创建、销毁的频率。 ExecutorService JAVA标准库为我们实现了线程池&#xff0c;Execu…

archlinux 如何解决安装以后没有声音的问题

今天安装完archlinux以后发现看视频没声音 检查一下是否有 /lib/firmware/intel/sof 发现没有 如果你也是这样的话&#xff0c;可以尝试安装&#xff1a; sudo pacman -S sof-firmware 重启后再看看有没有声音&#xff1a; reboot 反正我有声音了

跟着我学Python进阶篇:03. 面向对象(下)

往期文章 跟着我学Python基础篇&#xff1a;01.初露端倪 跟着我学Python基础篇&#xff1a;02.数字与字符串编程 跟着我学Python基础篇&#xff1a;03.选择结构 跟着我学Python基础篇&#xff1a;04.循环 跟着我学Python基础篇&#xff1a;05.函数 跟着我学Python基础篇&#…

【ARM 嵌入式 编译系列 7.3 -- GCC 链接脚本中 DISCARD 与 .ARM.exidx】

请阅读【嵌入式开发学习必备专栏 之 ARM GCC 编译专栏】 文章目录 背景.ARM.exidx方法一:使用链接器脚本方法二:使用链接器选项注意事项背景 在移植 RT-Thread 到 cortex-m33(RA4M2)上的时候,在编译的时候遇到下面问题: Building target: ra4m2.elf arm

Vue2基础-Vue对象进阶介绍2

文章目录 一、自定义指令1、用法2、注意点 二、生命周期1、概念2、示意图3、分析 一、自定义指令 本质上是封装了DOM元素的具体操作 1、用法 <div >放大十倍后的值是&#xff1a;<span v-big"n"></span></div> <input type"text&…

【Linux】—— 共享内存

本期我将要带大家学习的是有关进程间通信的另一种方式——共享内存。共享内存是一种用于进程间通信的高效机制&#xff0c;允许多个进程访问和操作同一块内存区域。 目录 &#xff08;一&#xff09;深刻理解共享内存 1.1 概念解释 1.2 共享内存原理 1.3 共享内存数据结构 …

Spring | Srping AOP (AOP简介、动态代理、基于“代理类”的AOP实现)

目录: 1.Spring AOP简介1.1 AOP简介1.2 AOP术语 2.动态代理2.1 JDK动态代理2.2 CGLIB代理 3.基于“代理类”的AOP实现3.1 Spring的通知类型3.2 ProxyFactoryBean ( 可通知.xml配置文件完成aop功能 ) 1.Spring AOP简介 1.1 AOP简介 Spring的AOP模块&#xff0c;是Spring框架体系…

【C++】list容器迭代器的模拟实现

list容器内部基本都是链表形式实现&#xff0c;这里的迭代器实现的逻辑需要注意C语言中指针的转换。 list容器如同数据结构中的队列&#xff0c;通常用链式结构进行存储。在这个容器中&#xff0c;我们可以模仿系统的逻辑&#xff0c;在头结点后设置一个“ 哨兵 ”&#xff0c;…

什么勒索攻击,应该如何防护?

当前&#xff0c;勒索攻击、僵尸网络攻击、DDos攻击、APT攻击、挖矿攻击、供应链攻击、网站攻击、电信诈骗等各种攻击手段层出不穷。 勒索攻击应该是今年网络安全行业讨论最多的话题&#xff0c;勒索钱财或者窃取商业数据是黑产最主要的目的。 勒索软件的攻击特征 与其它攻击行…

限价单和止损单是什么?澳福实例讲解

什么是限价单和止损单&#xff0c;投资者如何使用它?了解交易基础知识&#xff0c;快速进入市场盈利收场&#xff0c;今天fpmarkets澳福和各位投资者继续探讨交易基础知识。 止损单是在看涨趋势中以更高的价格买入的前提&#xff0c;通过图表得知&#xff0c;黄线显示欧元兑美…

刷题 ------ 排序

文章目录 1.K 次取返后最大化的数组和&#xff08;堆&#xff09;2.数组的相对排序&#xff08;桶&#xff09;3.最小绝对差4.根据数字二进制下1的数目排序&#xff08;qsort&#xff09;5.有多少小于当前数字的数字6.非递增顺序的最小子序列7.按照频率将数组升序排序&#xff…

生成当天递增唯一的流水号的几种方式

说明&#xff1a;当开发中&#xff0c;如交易、文件传输过程中的文件名&#xff0c;可能需要我们使用一串唯一的数字来锁定这一条“交互记录”&#xff0c;即流水号。 本文介绍几种生成6位递增唯一&#xff0c;且每日重置的流水号的方式。 方式一&#xff1a;使用Redis 我们…

Leetcode—22.括号生成【中等】

2023每日刷题&#xff08;七十九&#xff09; Leetcode—22.括号生成 算法思想 实现代码 class Solution { public:vector<string> generateParenthesis(int n) {vector<string> ans;int m n * 2;string path(m, 0);function<void(int, int)> dfs [&…

自己构建webpack+vue3+ts

先看看我的目录结构&#xff08;我全局使用TS&#xff09;&#xff1a; 一、安装配置webpack打包 安装esno npm install esnoesno 是基于 esbuild 的 TS/ESNext node 运行时,有了它&#xff0c;就可以直接通过esno *.ts的方式启动脚本&#xff0c;package.json中添加 type:…

力扣62. 不同路径

动态规划 思路&#xff1a; 定义 dp[r][c] 为到达坐标 (r, c) 的路径数&#xff1a; 它只能有同一行左边相邻方格向右到达或者同一列上方相邻方格向下到达&#xff1b;状态转移方程&#xff1a; dp[r][c] dp[r][c - 1] dp[r - 1][c]初始状态 dp[0][0] 1第一行的路径数是 1第…

二维码地址门牌管理系统:社区新风向

文章目录 前言一、集成先进技术的系统二、便捷居民体验三、支持社区管理四、未来展望与可扩展性 前言 随着科技的不断发展&#xff0c;智能化管理已经深入到我们的生活中。二维码门牌管理系统作为一款创新产品&#xff0c;在社区管理领域迅速引起广泛关注。这款系统不仅提升了…

CTFhub-bak文件

CTFhub-Web-信息泄露-备份文件下载-bak文件 题目信息 解题过程 看到提示说和index.php有关&#xff0c;在url后面加index.php.bak&#xff0c;跳转到http://challenge-7a4da2076cfabae6.sandbox.ctfhub.com:10800/index.php.bak网址&#xff0c;即&#xff1a; 跳转到下载页…

彻底搞定让人头痛的nginx location 路径匹配规则

nginx location 路径匹配规则 一、前言二、说在前面三、开始表演 一、前言 很多同学&#xff0c;在配置nginx的时候&#xff0c;都会遇到一个头痛的问题&#xff0c;就是location 的路径应该怎么写&#xff1f;到底要不要加斜杠&#xff0c;有点傻傻分不清楚。今天就来帮助大家…