算法每日一练 (18)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (18)

删除并获得点数

题目地址：删除并获得点数

题目描述

给你一个整数数组 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 个点数。

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

解题思路

• 首先根据题意判断边界条件，当集合 nums 中元素数量为 1 时直接返回首个元素的值即可。

• 然后获取数组中的最大值，创建辅助数组 count 来统计每个数字的总点数。其中 count[i] 表示 i 数字出现的点数之和。

• 当 count 集合中的元素个数小于 3 个时，表示源数组中不相同的元素个数不超过 2 个，故直接返回 count[1] 即可。

• 创建 dp 数组，初始化 dp[1]、dp[2]：

  • dp[1] = count[1]：因为 count[0] 永远等于 0 所以直接取 count[1] 即可。
  • dp[2] = max(count[1], count[2])：因为 count[1] 和 count[2] 只能选择删除其中一个，故选择其中最大的一个。

• 借助 for 循环从 3 开始到 maxVal，满足如下状态转移方程：

  $$dp[i]=max(dp[i-1],dp[i-2]+count[i])$$

  • 如果选择删除 i，则不能选择删除 i-1 和 i+1，故 dp[i] 的值就是 dp[i-2] + count[i]。
  • 如果不选择删除 i，则可以删除 i-1，故 dp[i] 的值就是 dp[i-1]。
  • 两者取其中最大值就是 dp[i] 的状态值。

• 最终返回 dp[maxVal] 的值即可。

解题代码

c/c++

#include <vector>

class Solution
{
public:
    int deleteAndEarn(std::vector<int> &nums)
    {
        int sz = nums.size();
        if (sz == 1)
            return nums[0];

        int maxVal = nums[0];
        for (int i = 1; i < sz; i++)
        {
            if (nums[i] > maxVal)
                maxVal = nums[i];
        }

        std::vector<int> count(maxVal + 1, 0);
        for (auto &e : nums)
        {
            count[e] += e;
        }

        if (count.size() < 3)
            return count[1];

        std::vector<int> dp(maxVal + 1, 0);
        dp[1] = count[1];
        dp[2] = std::max(count[1], count[2]);

        for (int i = 3; i <= maxVal; i++)
        {
            dp[i] = std::max(dp[i - 1], dp[i - 2] + count[i]);
        }

        return dp[maxVal];
    }
};

golang

func deleteAndEarn(nums []int) int {
	sz := len(nums)

	if sz == 1 {
		return nums[0]
	}

	maxVal := nums[0]
	for i := 1; i < sz; i++ {
		if nums[i] > maxVal {
			maxVal = nums[i]
		}
	}

	count := make([]int, maxVal+1)
	for _, num := range nums {
		count[num] += num
	}
    
    if len(count) < 3 {
		return count[1]
	}

	dp := make([]int, maxVal+1)
	dp[1] = count[1]
	dp[2] = max(count[1], count[2])

	for i := 3; i <= maxVal; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+count[i])
	}

	return dp[maxVal]
}

lua

local function deleteAndEarn(nums)
    local sz = #nums
    if sz == 1 then
        return nums[1]
    end

    local maxVal = nums[1]
    for i = 2, sz do
        if nums[i] > maxVal then
            maxVal = nums[i]
        end
    end

    local count = {}
    for i = 1, maxVal do
        count[i] = 0
    end

    for i, v in ipairs(nums) do
        if v == 0 then
            goto continue
        else
            count[v] = count[v] + v
        end
        ::continue::
    end

    if #count == 1 then
        return count[1]
    end

    local dp = {}
    dp[1] = count[1]
    dp[2] = math.max(count[1], count[2])

    for i = 3, maxVal do
        dp[i] = math.max(dp[i - 1], dp[i - 2] + count[i])
    end

    return dp[maxVal]
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。