AlgoPressAppearance
0740-删除并获得点数
https://leetcode.cn/problems/delete-and-earn/
给你一个整数数组 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
思路分析
这题的也是一开始没有思路，然后看了题解才知道。
题目中，删除一个点数，那么点数-1和点数+1的数字都会被删除，得不到分。 但是我们就可以相应很安全的把所有的相同点数都获取到。
所以将题目中的数字，如果重新排序，并且相同的数字放到一起，因为数字是严格匹配的，比如 删除5，那么就会固定删除4,6，而不是排在5前面的数。所以为空的位置也必须放置0， 如 3,4,2 -> [0,0,2,3,4] 注意下标是 0,1,2,3,4 ， 然后 [2,2,3,3,3,4] -> [0,0,4,9,4]
此时问题就转化为了打家劫舍的问题了。
实现代码
注意几个点
- DeleteAndEarn 中不能直接判断 nums.Length == 2 取最大，因为他们可能不相邻，是可以加起来的，如[3,1] -> 4
- 注意 Rob 传入的参数是 calcNums 不要传错
csharp
public class Solution {
public int DeleteAndEarn(int[] nums) {
//前两种情况正常取最大值
if(nums.Length == 1){
return nums[0];
}
// if(nums.Length == 2){
// return Math.Max(nums[0],nums[1]);
// }
//找寻最大数字构造数组
int maxVal = 0;
for(int i=0; i < nums.Length; i++){
if(maxVal < nums[i]){
maxVal = nums[i];
}
}
int[] calcNums = new int[maxVal+1];
for(int i=0; i < nums.Length; i++){
calcNums[nums[i]] += nums[i];
}
for(int i=0; i< calcNums.Length; i++){
Console.WriteLine("i:{0},v:{1}",i,calcNums[i]);
}
return Rob(calcNums);
}
private int Rob(int[] nums){
int[] dp = new int[nums.Length];
dp[0] = nums[0];
dp[1] = Math.Max(nums[0],nums[1]);
for(int i=2; i<nums.Length; i++){
dp[i] = Math.Max(dp[i-2] + nums[i],dp[i-1]);
Console.WriteLine("dp:i:{0},v:{1}",i,dp[i]);
}
return dp[nums.Length - 1];
}
}
实现代码：整理
csharp
public class Solution {
public int DeleteAndEarn(int[] nums) {
//第一步 找出最大值 1 <= nums[i] <= 10^4
int maxVal = 0;
for(int i=0; i<nums.Length; i++){
maxVal = Math.Max(nums[i],maxVal);
}
//定义 新数组
int[] newNums = new int[maxVal+1];
for(int i=0; i<nums.Length; i++){
newNums[nums[i]] += nums[i];
}
//转变为打家劫舍
int[] dp = new int[newNums.Length];
dp[0] = newNums[0];
if(newNums.Length > 1){
dp[1] = Math.Max(newNums[0],newNums[1]);
}
//状态转移
for(int i=2; i<newNums.Length; i++){
dp[i] = Math.Max(dp[i-2] + newNums[i], dp[i-1]);
}
return dp[newNums.Length -1];
}
}
复习：20220630
csharp
public class Solution {
public int DeleteAndEarn(int[] nums) {
int max = nums.Max();
int[] newNums = new int[max+1];
for(int i=0; i<nums.Length; i++){
newNums[nums[i]] += nums[i];
}
//转化为打家劫舍，不可选取相连的数
int[] dp = new int[max+1];
dp[0] = newNums[0];
if(newNums.Length > 1){
dp[1] = Math.Max(newNums[0],newNums[1]);
}
for(int i=2; i<dp.Length; i++){
dp[i] = Math.Max(dp[i-1],dp[i-2]+newNums[i]);
}
return dp[max];
}
}