LeetCode 740.删除并获得点数----＞打家劫舍

浅浅的花香味﹌ 2024-02-20 08:45 45阅读 0赞

## 前言：简单写写自己对这道题的拙见，如有意见或者建议可以联系笔者owo ##

首先，看看完整题目描述：

> 给你一个整数数组 nums ，你可以对它进行一些操作。  
> 每次操作中，选择任意一个 nums\[i\] ，删除它并获得 nums\[i\] 的点数。之后，你必须删除 所有 等于 nums\[i\] - 1 和 nums\[i\] + 1 的元素。  
> 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
> 
> > 输入：nums = \[3,4,2\]  
> > 输出：6  
> > 解释：  
> > 删除 4 获得 4 个点数，因此 3 也被删除。  
> > 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
> 
> > 输入：nums = \[2,2,3,3,3,4\]  
> > 输出：9  
> > 解释：  
> > 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。  
> > 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。  
> > 总共获得 9 个点数。
> 
> 提示：
> 
>  *  1 <= nums.length <= 2 \* 10^4
>  *  1 <= nums\[i\] <= 10^4

这道题翻译成人话就是我可以在一个数组中随机获取一个x = nums\[i\]，但是数字的x+1和-1全部都得删除（如果数组中存在的话），举个例子，假如你选择3，那么数组中的2和4就全部不能选了。

其实遇到这种题说删除的，要是你真的信，你就输了，我们真正要做的应该是**逻辑删除** ，意思就是**不选**或者其他做法，这题我们可以理解为不选即可。

那么问题来了，对于给定的随机数组，我们要如何快速判定一个数的左右数不能选择呢？？？答案很简单，定义一个hash数组，下标意义就为这个数x=nums\[i\]，但是需要注意的是，我们需要检查数据范围是否允许我们这么操作而不会导致空间超过限制。很明显，1<x=nums\[i\]<10^4这个数远远不足以超过内存限制。所以我们这个定义hash数组：

int[] hash = new int[maxNum+1]]; // maxNum为数组中的最大值

快速定位的问题解决了，数组里面的值应该填什么呢？？？  
我们先来思考一个问题：  
题目上写着每次可以取一个x=nums\[i\]然后x+1与x-1就得被**逻辑删除**,除此之外这个x会存在重复，那么就意味着，**我们在每次取值的时候直接获取全部的x不就好了？**，那么这样就以为这，我们的数组\[2,2,3,3,3,4,4\]可以修改为如下图所示的数组\[4,9,8\]：  
![image.png][]

然后装进我们的hash数组就会是这个样子：

hash = [0,0,4,9,8] // 伪代码

到这个一步，你就会发现这个玩意在取值的时候只需要考虑要么选择hash\[2\]+hash\[4\]或者hash\[3\]就可以了，这样就做到了一个选与不选的逻辑删除。\*\*到这一步你就会发现这不就是一个动态规划的打家劫舍吗！！！\*\*那套一下打家劫舍的套路选自己不选隔壁的套路就可以轻松解题啦~~~~

解题代码如下（有些粗糙见谅）：

class Solution {
        
        public int deleteAndEarn(int[] nums) {
        
            return dp(nums);
        }
        private int dp(int[] nums){
        
        
            int n = 0;
            for(int i = 0; i < nums.length; i++){
        
                n = Math.max(nums[i],n);
            }
            //[1,1,1]纯1数组需要特殊处理。因为hash数组长度length=1,下面的动态规划过程不需要走
            if(n == 1){
        
                return nums[0]*nums.length;
            }
            int[] hash = new int[n+1];
            for(int i = 0; i < nums.length; i++){
        
                hash[nums[i]] += nums[i];
            }
            int[] dp = new int[n+1];
            dp[1] = hash[1];
            dp[2] = Math.max(hash[1],hash[2]);
            for(int i = 3; i < n+1; i++){
        
                dp[i] = Math.max(dp[i-2]+hash[i],dp[i-1]);
            }
            return dp[n];
        }
    }

--------------------

END 希望本文章能对你提供帮助

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/98b0ebd5325645a79f95bb4a60deb6b5.png