740.刪除并獲得點數(shù)

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

難度：中等

題目：

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

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

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

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^4

示例：

示例 1：

輸入：nums = [3,4,2]
輸出：6
解釋：
刪除 4 獲得 4 個點數(shù)，因此 3 也被刪除。
之后，刪除 2 獲得 2 個點數(shù)?？偣搏@得 6 個點數(shù)。

示例2：

輸入：nums = [2,2,3,3,3,4]
輸出：9
解釋：
刪除 3 獲得 3 個點數(shù)，接著要刪除兩個 2 和 4 。
之后，再次刪除 3 獲得 3 個點數(shù)，再次刪除 3 獲得 3 個點數(shù)。
總共獲得 9 個點數(shù)。

分析

如果朋友之前做過打家jie舍兩部曲，那么看到這題應(yīng)該很快反應(yīng)到應(yīng)該考慮動態(tài)規(guī)劃。
很多朋友問遇到題，你怎么知道應(yīng)該考慮到什么算法，沒什么知道不知道，同類型題做的多了自然就知道了。

不熟悉的同學(xué)，可以看看我的歷史解題：

• 打家jie舍
• 打家jie舍II

那么，今天這道題其實就是在打家jie舍的基礎(chǔ)上進行了擴展。我們可以通過hash表將這道題還原回去：

1. 這道題存在重復(fù)數(shù)字，我們先通過的d = collections.Count(nums)將其轉(zhuǎn)化為dict類型.
2. 我們使用k = sorted(d.keys(),reverse=True)轉(zhuǎn)化為遞減的數(shù)組
3. 現(xiàn)在我們再來看這道題是不就和打家jie舍很類似了。
4. 如果len(k) == 1,k[0],那么總和為k[0] * d[k[0]],但len(k) == 2時需要注意下
5. 如果k[0] - k[1] > 1，那么按照題意是可以并存的，此時k[1] = k[0] * d[k[0]] + k[1] * d[k[1]]
6. 如果k[0] - k[1] <= 1,那么只能二選一， max(k[0] * d[k[0]], k[1] * d[k[1]])
7. 如法炮制，使用for循環(huán)遍歷最終即可得到結(jié)果。

上面的分析大家理解了吧？

算法的時間復(fù)雜度O(n),由于創(chuàng)建了去重的k，所以空間復(fù)雜度最壞情況為O(n)。

來看看具體解題，還不錯，超過了96.5%的python用戶。

image.png

解題：

from collections import Counter
class Solution:
    def deleteAndEarn(self, nums):
        d = Counter(nums)
        k = sorted(d.keys(),reverse=True)
        ln = len(k)
        if ln == 1:
            return k[0] * d[k[0]]
        left = k[0] * d[k[0]]
        if k[0] - k[1] > 1:
            right = left + k[1] * d[k[1]]
        else:
            right = max(left, k[1] * d[k[1]])
        for i in range(2,ln):
            left, tmp = right, left
            if k[i - 1] - k[i] > 1:
                right += k[i] * d[k[i]]
            else:
                right = max(tmp+k[i] * d[k[i]],right)
        return right

歡迎關(guān)注我的公眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown