C++ leetcode之刪除并獲得點數(shù)的示例代碼

更新時間：2021年05月07日 09:58:23 作者：cqu_shuai

這篇文章主要介紹了C++ leetcode之刪除并獲得點數(shù)的示例代碼,本文給大家分享問題解析及解決方案，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

參考鏈接

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/

題目描述

給你一個整數(shù)數(shù)組 nums ，你可以對它進行一些操作。

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數(shù)。之后，你必須刪除每個等于 nums[i] - 1 或 nums[i] + 1 的元素。

開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。

在這里插入圖片描述

解題思路

本題需要明確的一點是，如果刪除了有多個相同值的元素，因為比它大1或小1的元素都被刪了，后面這些相同的元素還會被剩下，所以可以一次全部刪除。

回溯法

即暴力窮舉所有情況。首先用哈希表記錄所有相同元素的和，窮舉哈希表的每一個鍵，記錄下它的值，并去除哈希表中鍵比它大1和小1的值，遞歸后再恢復(fù)。（會超時?。?/p>

遞歸式動態(tài)規(guī)劃

先對數(shù)組進行排序，然后用哈希表記錄所有相同元素的和，同時新建一個記錄所有不重復(fù)元素的數(shù)組，這樣就可以把“狀態(tài)”設(shè)為不重復(fù)數(shù)組的索引了，狀態(tài)表存儲的就是當(dāng)前索引到最后一個索引間能獲得的最大點數(shù)?！斑x擇”就是是否刪除當(dāng)前索引處元素。如果要刪除當(dāng)前元素，這一步中需要判斷下一個元素與當(dāng)前元素的差是否等于1，如果等于1，就往下跳2個元素，否則跳1個元素；如果不刪除當(dāng)前元素，則直接跳一個元素。

迭代式動態(tài)規(guī)劃

官方解法用數(shù)組代替哈希表存儲相同元素的元素和，這樣每個元素間的差都是1，狀態(tài)表記錄第0個元素到當(dāng)前元素能獲得的最大點數(shù)?！斑x擇”是是否刪除當(dāng)前元素，如果刪除，點數(shù)為當(dāng)前元素與第0個元素到前2個元素的最大點數(shù)和，如果不刪，就是第0個元素到前一個元素的最大點數(shù)。

排序 + 動態(tài)規(guī)劃

同樣是官方的最優(yōu)解法，若 nums 中不存在某個元素 x，則選擇任一小于 x 的元素不會影響到大于 x 的元素的選擇。因此我們可以將 nums 排序后，將其劃分成若干連續(xù)子數(shù)組，子數(shù)組內(nèi)任意相鄰元素之差不超過 1。對每個子數(shù)組按照方法一的動態(tài)規(guī)劃過程計算出結(jié)果，累加所有結(jié)果即為答案。

代碼

回溯法

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;
    }

};

遞歸式動態(tài)規(guī)劃

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);
    }
};

迭代式動態(tài)規(guī)劃

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);
    }
};

排序 + 動態(tài)規(guī)劃

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;
    }
};

到此這篇關(guān)于C++ leetcode之刪除并獲得點數(shù)的示例代碼的文章就介紹到這了,更多相關(guān)C++ leetcode內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: