leetcode 740. Delete and Earn | 740. 删除并获得点数(暴力递归->傻缓存->DP)

2023-12-31 19:18

本文主要是介绍leetcode 740. Delete and Earn | 740. 删除并获得点数(暴力递归->傻缓存->DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

https://leetcode.com/problems/delete-and-earn/
在这里插入图片描述

题解

建立 help 数组,相当于一个(正向)索引表。

先排序,因为删除的顺序不影响最优结果(实际上是影响结果的,只不过最优解一定是从小到大删除的,因为如果先删除中间的元素的话,它的两边可能被误伤,而如果从边缘开始删除的话,只能误伤到一侧。)

class Solution {public int deleteAndEarn(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int n : nums) {int count = map.getOrDefault(n, 0);map.put(n, count + 1);}int[][] help = new int[map.keySet().size()][2];int p = 0;for (int k : map.keySet()) {help[p][0] = k;help[p++][1] = map.get(k);}// 删除顺序不影响结果(至少从小到大删除结果不会更差),所以先排序Arrays.sort(help, Comparator.comparingInt(o -> o[0]));// Approach 2: Recursion with Memoization
//        return process(help, 0, dp);// Approach 3: Dynamic Programmingint[] dp = new int[help.length + 2];Arrays.fill(dp, -1);dp[help.length] = 0;dp[help.length + 1] = 0;for (int i = help.length - 1; i >= 0; i--) {int step = (i + 1 < help.length && help[i][0] + 1 == help[i + 1][0]) ? 2 : 1;dp[i] = Math.max(dp[i + 1], dp[i + step] + help[i][0] * help[i][1]);}return dp[0];}// 在当前i位置,删或不删,能够获得的最大收益
//    public int process(int[][] help, int i, int[] dp) {
//        if (i >= help.length) return 0;
//        if (dp[i] >= 0) return dp[i];
//
//        int step = (i + 1 < help.length && help[i][0] + 1 == help[i + 1][0]) ? 2 : 1;
//        int p1 = process(help, i + 1, dp); // 不删i位置
//        int p2 = process(help, i + step, dp) + help[i][0] * help[i][1]; // 删i位置
//
//        dp[i] = Math.max(p1, p2);
//        return dp[i];
//    }
}

在这里插入图片描述

这篇关于leetcode 740. Delete and Earn | 740. 删除并获得点数(暴力递归->傻缓存->DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/556925

相关文章

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

python删除xml中的w:ascii属性的步骤

《python删除xml中的w:ascii属性的步骤》使用xml.etree.ElementTree删除WordXML中w:ascii属性,需注册命名空间并定位rFonts元素,通过del操作删除属... 可以使用python的XML.etree.ElementTree模块通过以下步骤删除XML中的w:as

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

如何在Mac上彻底删除Edge账户? 手动卸载Edge浏览器并清理残留文件技巧

《如何在Mac上彻底删除Edge账户?手动卸载Edge浏览器并清理残留文件技巧》Mac上的Edge账户里存了不少网站密码和个人信息,结果同事一不小心打开了,简直尴尬到爆炸,想要卸载edge浏览器并清... 如果你遇到 Microsoft Edge 浏览器运行迟缓、频繁崩溃或网页加载异常等问题,可以尝试多种方

Oracle 数据库数据操作如何精通 INSERT, UPDATE, DELETE

《Oracle数据库数据操作如何精通INSERT,UPDATE,DELETE》在Oracle数据库中,对表内数据进行增加、修改和删除操作是通过数据操作语言来完成的,下面给大家介绍Oracle数... 目录思维导图一、插入数据 (INSERT)1.1 插入单行数据,指定所有列的值语法:1.2 插入单行数据,指

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略(Key Expir

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-