740、删除并获得点数

leetcode 数组动态规划哈希表

Created At : 2024-06-04 11:16

Count:845 Views 👀 :

Comment:

题目
示例 1：
示例 2：
1. 提示：
题解

题目

给你一个整数数组 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 * 10^4$
$1 <= nums[i] <= 10^4$

题解

贪婪自上而下局部最优解

class Solution {
    public int deleteAndEarn(int[] nums) {
        // 贪婪 总是删除最大的点数，避免被牵连删除了
        // 数组标记法, 主动删除标记为-1 被动删除标记为 -2 
        int[] total = new int[10001];
        // 初始状态标记为 1 - n, n 表示 num[i]的个数 
        // 处理重复数字，从大到小遍历，最大的数字存在重复则依次删除，因为可以增大点数
        // 如果nums[i] - 1 有很多个，其总和大于了num[i], 则 反转
        for (int i = 0;i < nums.length; i++) {
            if (total[nums[i]] == 0) {
                total[nums[i]] = nums[i];
            } else {
                total[nums[i]] += nums[i];
            }
        }
        int sumPoints = 0;
        for (int i = 10000;i >= 1;i--) {
            if (total[i] == 0) continue;
            if (total[i] >= total[i - 1] || total[i-1] < total[i] + total[i-2]) {
                sumPoints += total[i];
                System.out.println("use " + i +" : "+total[i]);
                i--;// nums[i] - 1的点数不算进来
                System.out.println("delete " + i +" : "+total[i]);
            } else {
                if (total[i-1] > total[i] + total[i-2]) {
                    System.out.println("delete " + i +" : "+total[i]);
                    i--;
                    System.out.println("use " + i +" : "+total[i]);
                    sumPoints += total[i];
                    System.out.println("delete " + i +" : "+total[i]);
                    i--;
                }
            }
        }
        return sumPoints;
    }
}

动态规划

198 打家劫舍的变种，把每户的钱，变成了 i 出现 t 次的总和

dp[i] 表示前i个数字的最大点数：
$dp[i] = max(dp[i-2]+(i)*times,dp[i-1])$

dp[i] 和 dp[i-1] 只能选择1个

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] total = new int[10001];
        for (int i = 0;i < nums.length; i++) {
            total[nums[i]] += nums[i];
        }
        int first = total[0], second = Math.max(total[0],total[1]);
        for (int i = 2;i <= 10000;i++) {
            int temp = second;
            // 跳过一个较小的值
            second = Math.max(first + total[i], second);
            first = temp;
        }
        return second;
    }
}

其他解法学习

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        int max = nums[0];
        for (int i = 0; i < len; ++i) {
           max = Math.max(max, nums[i]);
        }
//      构造一个新的数组all，举例，如果 all[8] 是 3, 说明 nums 数组里等于8 的元素有3个
        int[] all = new int[max + 1];
        for (int item : nums) {
            all[item] ++;
        }
        int[] dp = new int[max + 1];

//      当 max = 1 的时候，最优解: all[1] * 1
        dp[1] = all[1] * 1;

        // 自下而上
        for (int i = 2; i <= max; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
        }
        return dp[max];
    }
}

// 作者：陆艰步走
// 链接：https://leetcode.cn/problems/delete-and-earn/

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com