C++ leetcode之删除并获得点数的示例代码

参考链接

https://leetcode-cn.com/problems/delete-and-earn/

https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/

题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

解题思路

本题需要明确的一点是，如果删除了有多个相同值的元素，因为比它大1或小1的元素都被删了，后面这些相同的元素还会被剩下，所以可以一次全部删除。

回溯法

即暴力穷举所有情况。首先用哈希表记录所有相同元素的和，穷举哈希表的每一个键，记录下它的值，并去除哈希表中键比它大1和小1的值，递归后再恢复。（会超时！）

递归式动态规划

先对数组进行排序，然后用哈希表记录所有相同元素的和，同时新建一个记录所有不重复元素的数组，这样就可以把“状态”设为不重复数组的索引了，状态表存储的就是当前索引到最后一个索引间能获得的最大点数。“选择”就是是否删除当前索引处元素。如果要删除当前元素，这一步中需要判断下一个元素与当前元素的差是否等于1，如果等于1，就往下跳2个元素，否则跳1个元素；如果不删除当前元素，则直接跳一个元素。

迭代式动态规划

官方解法用数组代替哈希表存储相同元素的元素和，这样每个元素间的差都是1，状态表记录第0个元素到当前元素能获得的最大点数。“选择”是是否删除当前元素，如果删除，点数为当前元素与第0个元素到前2个元素的最大点数和，如果不删，就是第0个元素到前一个元素的最大点数。

排序 + 动态规划

同样是官方的最优解法，若 nums 中不存在某个元素 x，则选择任一小于 x 的元素不会影响到大于 x 的元素的选择。因此我们可以将 nums 排序后，将其划分成若干连续子数组，子数组内任意相邻元素之差不超过 1。对每个子数组按照方法一的动态规划过程计算出结果，累加所有结果即为答案。

代码

回溯法

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (int num : nums)
        {
            mp[num] += num;
        }
        int res = Earn(mp);
        return res;
    }

    int Earn(unordered_map<int, int>& mp)
    {
        int res = 0;
        for (auto& item : mp)
        {
            if (mp[item.first] == 0)
            {
                continue;
            }
            int sum = mp[item.first];
            mp[item.first] = 0;
            int prev_plus_1 = mp[item.first + 1];
            int prev_sub_1 = mp[item.first - 1];
            mp[item.first + 1] = 0;
            mp[item.first - 1] = 0;
            res = max(res, sum + Earn(mp));
            mp[item.first] = sum;
            mp[item.first + 1] = prev_plus_1;
            mp[item.first - 1] = prev_sub_1;
        }
        return res;
    }

};

递归式动态规划

class Solution {
public:
    unordered_map<int, int> memo;
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> mp;
        vector<int> unique;
        int tmp = INT_MAX;
        for (int num : nums)
        {
            if (tmp != num)
            {
                unique.push_back(num);
                tmp = num;
            }
            mp[num] += num;
        }
        unique.push_back(INT_MAX);
        int res = dp(mp, unique, 0);
        return res;
    }
    int dp(unordered_map<int, int>& mp, vector<int>& nums, int start)
    {
        if (start + 1 >= nums.size())
        {
            return 0;
        }
        if (memo.count(start) == 1)
        {
            return memo[start];
        }
        int do_it = 0;
        if (nums[start] - nums[start + 1] == 1 || nums[start + 1] - nums[start] == 1)
        {
            do_it = mp[nums[start]] + dp(mp, nums, start + 2);
        }
        else
        {
            do_it = mp[nums[start]] + dp(mp, nums, start + 1);
        }
        int not_do = dp(mp, nums, start + 1);
        memo[start] = max(do_it, not_do);
        return max(do_it, not_do);
    }
};

迭代式动态规划

class Solution {
private:
    int rob(vector<int> &nums) {
        int size = nums.size();
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = max(maxVal, val);
        }
        vector<int> sum(maxVal + 1);
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }
};

排序 + 动态规划

class Solution {
private:
    int rob(vector<int> &nums) {
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        int n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end());
        vector<int> sum = {nums[0]};
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.back() += val;
            } else if (val == nums[i - 1] + 1) {
                sum.push_back(val);
            } else {
                ans += rob(sum);
                sum = {val};
            }
        }
        ans += rob(sum);
        return ans;
    }
};

到此这篇关于C++ leetcode之删除并获得点数的示例代码的文章就介绍到这了,更多相关C++ leetcode内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！