地址:
力扣https://leetcode-cn.com/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:
输出:9
解释:
删除 3 获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。
提示:
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
选定一个 i,删除 i-1 和 i -2 ,不就是选定一个,旁边两个不能选,典型的 198、打家劫舍
不过还有一些小细节要处理,就是数组存在重复元素,所以不能直接套用
那么如果我们把元素个数统计完成,并且将其求和的值放在新数组里面
这个新数组就能套用了
这部分的工作交给 排序算法之计数排序 完成
方法一、计数数组+打家劫舍
#define max(a,b) ( (a) > (b) ? (a) : (b) )int rob(int* nums, int numsSize){int i;int dp[10001]={0};dp[0] = nums[0];for(i=1; i
查看更多刷题笔记