[LeetCode] 740. Delete and Earn

本文主要是介绍[LeetCode] 740. Delete and Earn，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/delete-and-earn/

题目大意

对于数组nums ，选取一个数 num，那么nums数组中 num - 1 与 num + 1 都会被删除，重复多次直到 nums 数组为空。求选取 num 的最大和。

解题思路

方法一 treeMap

将nums 中所有元素进行reduce操作，得到 TreeMap，其中 key = num ，val = num*k （k 为 nums 中num 出现的次数）

然后 从 小到大遍历 treeMap，这里用到的是

iterator it = treeMap.entrySet().iterator();
Map.Entry<Integer,Integer> entry = (Map.Entry<Integern,Integer>)it.next();

这里用到了动态规划，
int dp[i] : 选了 treeMap中的第i个数时，得到的最大收益是多少。
这里分两种情况，
若 上个数 == 当前num -1，那么 两者数值上连续 dp[i] = Math.max(dp[i-3], dp[i-2]) + entry.getValue();前一个数一定不能取得。

当 若上个数 != 当前num -1，那么dp[i] = Math.max(dp[i-2], dp[i-1]) + entry.getValue();
可以取当前数。

由于 只用到了 i -3,i-2,i-1,i ，可以使用 4个变量代替，动态规划 数组。

但这个方法 太麻烦了。

class Solution {public int deleteAndEarn(int[] nums) {TreeMap<Integer,Integer>  treeMap = new TreeMap<>();for(int num : nums){treeMap.put(num,treeMap.getOrDefault(num,0)+num);}int[] sum = new int[4];int lastKey = 0;Iterator it  = treeMap.entrySet().iterator();if(it.hasNext()){Map.Entry<Integer,Integer> entry = (Map.Entry<Integer, Integer>) it.next();sum[3] = entry.getValue();sum[2] = sum[3];lastKey = entry.getKey();}while (it.hasNext()){Map.Entry<Integer,Integer> entry = (Map.Entry<Integer, Integer>) it.next();if(lastKey == entry.getKey() -1){sum[3] = Math.max(sum[0], sum[1]) + entry.getValue();sum[0] = sum[1];sum[1] = sum[2];sum[2] = sum[3];}else {sum[3] = Math.max(sum[1],sum[2]) + entry.getValue();sum[0] = Math.max(sum[1],sum[2]);sum[1] = sum[0];sum[2] = sum[3];}lastKey = entry.getKey();}return Math.max(sum[1],sum[2]);}
}

方法二 转化为 LeetCode 198. House Robber

可以将该问题转化为 House Robber 为题。
新 numsArr[num]中，index 为元素num数值，val 为 nums中 num的和。

然后 ， 动态规划

int dp[num]：遍历到num数时，能得到的最大 收益。（num不一定需要选取）

状态转移方程：
dp[num] = Math.max(dp[num-2] + numsArr[num], dp[num-1])。 当前最大收益为 dp[num-2] + 选num的收益 与 不选当前num的收益从而获得 dp[num-1] 的收益 中的 较大值。
由于只用到 i-2,i-1,i 可以使用 a,b,c 代替。

class Solution {public int deleteAndEarn(int[] nums) {int maxNum = 0 ;for(int num : nums)maxNum = Math.max(maxNum,num);int[] numsArr = new int[maxNum+1];for(int num:nums)numsArr[num] += num;int a = 0,b = 0,c = 0;for(int i = 0; i <= maxNum;i++){c = Math.max(a + numsArr[i],b);a = b;b = c;}return c;}
}

这篇关于[LeetCode] 740. Delete and Earn的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---