💢歡迎來到張翊塵的技術站
💥技術如江河，匯聚眾志成。代碼似星辰，照亮行征程。開源精神長，傳承永不忘。攜手共前行，未來更輝煌💥

官方站點： 力扣 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 = #numsif sz == 1 thenreturn nums[1]endlocal maxVal = nums[1]for i = 2, sz doif nums[i] > maxVal thenmaxVal = nums[i]endendlocal count = {}for i = 1, maxVal docount[i] = 0endfor i, v in ipairs(nums) doif v == 0 thengoto continueelsecount[v] = count[v] + vend::continue::endif #count == 1 thenreturn count[1]endlocal dp = {}dp[1] = count[1]dp[2] = math.max(count[1], count[2])for i = 3, maxVal dodp[i] = math.max(dp[i - 1], dp[i - 2] + count[i])endreturn dp[maxVal]
end

🌺🌺🌺撒花！

如果本文對你有幫助，就點關注或者留個👍
如果您有任何技術問題或者需要更多其他的內容，請隨時向我提問。