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