永定区建设局网站,厦门网站开发网络公司,网络课程网站模板,网站项目团队介绍怎么写文章目录1. 题目2. 解题1. 题目
给定一个整数数组 nums #xff0c;你可以对它进行一些操作。
每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除每个等于 nums[i] - 1 或 nums[i] 1 的元素。
开始你拥有…
文章目录1. 题目2. 解题1. 题目
给定一个整数数组 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 个点数。注意:
nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。来源力扣LeetCode 链接https://leetcode-cn.com/problems/delete-and-earn 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先预处理出每个数字的分数并且按数字排序使用mapdp[i][0] 表示不拿 dp[i][1] 表示拿 i 号数字时的最大得分
class Solution {
public:int deleteAndEarn(vectorint nums) {if(nums.empty())return 0;mapint,int num_points;for(int num : nums)num_points[num] num;//数字和其对应的分数vectorpairint,int num_pts(num_points.begin(), num_points.end());//map key有序vectorvectorint dp(num_points.size(), vectorint(2, 0));// dp[i][0] 表示不拿 dp[i][1] 表示拿 i 号数字的最大得分dp[0][1] num_pts[0].second;//拿第一个数的得分for(int i 1; i num_pts.size(); i){if(num_pts[i-1].first1 num_pts[i].first)//数字间隔大于1dp[i][1] num_pts[i].second max(dp[i-1][0], dp[i-1][1]);//前一个数可以拿或者不拿else // num_pts[i-1].first1 num_pts[i].first 间隔1//我要拿了前一个不能拿dp[i][1] num_pts[i].second dp[i-1][0];dp[i][0] max(dp[i-1][0], dp[i-1][1]); //我不拿那么前一个拿或者不拿}return max(dp.back()[0], dp.back()[1]);}
};20 ms 10.4 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
