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

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