欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

740.删除并获得点数

时间:2023-05-31

地址:

力扣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:

输入: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

来源:力扣(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

查看更多刷题笔记

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。