一起学习交流~

删除并获得点数-打家劫舍

算法 laomuji 8个月前 (01-27) 371次浏览 已收录 0个评论

目录

题目

给你一个整数数组 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 个点数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

转变为打家劫舍问题
[2,2,3,3,3,4,5]
2 3 4 5
4 9 4 5
此时 就是对应的数字和对应的价值
可以发现 当前数字若是比上一个数字大1,
那么就有选或者不选两种情况
若不是比上一个数字大1,那么直接加上上一个数字的最大价值

class Solution {
    int rob(vector<pair<int,int>>& nums){
        int size = nums.size();
        vector<int>dp(nums.size()+1);
        dp[0]=0;
        dp[1]=nums[0].second;
        int maxRob = dp[1];
        for(int i =2;i<=size;i++){
            //当前数字
            int currentNum = nums[i-1].first;
            //当前价值
            int currentValue=nums[i-1].second;
            //上个数字
            int lastNum = nums[i-2].first;
            //上个价值
            int lastValue = dp[i-1];
            if(currentNum == lastNum + 1){
                //如果上一个是当前的+1,判断取哪个
                dp[i]=max(lastValue,dp[i-2]+currentValue);
            }else{
                dp[i]=lastValue+currentValue;
            }
            if(dp[i]>maxRob)maxRob=dp[i];
        }
        return maxRob;
    }
public:
    int deleteAndEarn(vector<int>& nums) {
        int size = nums.size();
        if(size==1)return nums[0];
        map<int,int>mapNums;
        for(int i =0;i<nums.size();i++){
            mapNums[nums[i]]+=nums[i];
        }
        vector<pair<int,int>>data(mapNums.begin(),mapNums.end());
        return rob(data);
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论