美文网首页清风Python力扣算法刷题
力扣每日一题:740.删除并获得点数 python动态规划详解!

力扣每日一题:740.删除并获得点数 python动态规划详解!

作者: 清风Python | 来源:发表于2021-05-05 22:34 被阅读0次

    740.删除并获得点数

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

    难度:中等

    题目:

    给你一个整数数组nums,你可以对它进行一些操作。

    每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。
    之后,你必须删除每个等于nums[i] - 1或nums[i] + 1的元素。

    开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

    提示:

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

    示例:

    示例 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 个点数。
    

    分析

    如果朋友之前做过打家jie舍两部曲,那么看到这题应该很快反应到应该考虑动态规划。
    很多朋友问遇到题,你怎么知道应该考虑到什么算法,没什么知道不知道,同类型题做的多了自然就知道了。

    不熟悉的同学,可以看看我的历史解题:

    那么,今天这道题其实就是在打家jie舍的基础上进行了扩展。我们可以通过hash表将这道题还原回去:

    1. 这道题存在重复数字,我们先通过的d = collections.Count(nums)将其转化为dict类型.
    2. 我们使用k = sorted(d.keys(),reverse=True)转化为递减的数组
    3. 现在我们再来看这道题是不就和打家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循环遍历最终即可得到结果。

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

    算法的时间复杂度O(n),由于创建了去重的k,所以空间复杂度最坏情况为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
    

    欢迎关注我的公众号: 清风Python,带你每日学习Python算法刷题的同时,了解更多python小知识。

    我的个人博客:https://qingfengpython.cn

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

    相关文章

      网友评论

        本文标题:力扣每日一题:740.删除并获得点数 python动态规划详解!

        本文链接:https://www.haomeiwen.com/subject/violdltx.html