题目链接

leetcode在线oj题——删除并获得点数

题目描述

给你一个整数数组 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

解题思路

直接看题目描述可能无法理解题目的具体含义，下面用一个示例来帮助理解题意

首先，题目给定一个nums数组

随便选一个数字，得到这个数字对应的点数，然后删除掉这个数字和比这个数字小1和比这个数字大1的所有数字

例如选择2，那么现在所有的1，2，3都被删除了，并且点数是2

例如再选择5，那么点数是所有5集合，并且删除4和5

再选择8，所有的数字都被删除完了，得到点数为25

因此可以发现，这道题的整体思路就是，保证选中的点删除后能够得到的点数比选择其相邻数字删除后能得到的点数大。而之前博客中讲到打家劫舍问题，与之类似
打家劫舍问题blog
打家劫舍中也是获取到最大的点数，不能偷取数组相邻两个位置，而这道题中是相邻的两个数字不能同时获取点数。因此，我们只需要创建一个arr数组，让arr数组的下标和nums数组中的数字对应，而arr数组中存储当前下标对应的数字的点数总和

例如nums数组中有三个5，那么arr[5] = 15

接着，只需要用打家劫舍问题的解决思路就可以解决这道问题了

完整代码

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] arr = new int[10001];
        for (int i = 0; i < nums.length; i++){
            arr[nums[i]] += nums[i];
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[dp.length - 1];
    }
}