力扣每日一题：740.删除并获得点数 python动态规划详解!
2021-05-05 本文已影响0人
清风Python
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表将这道题还原回去：
- 这道题存在重复数字，我们先通过的
d = collections.Count(nums)将其转化为dict类型. - 我们使用
k = sorted(d.keys(),reverse=True)转化为递减的数组 - 现在我们再来看这道题是不就和打家jie舍很类似了。
- 如果len(k) == 1,k[0],那么总和为k[0] * d[k[0]],但len(k) == 2时需要注意下
- 如果k[0] - k[1] > 1，那么按照题意是可以并存的，此时k[1] = k[0] * d[k[0]] + k[1] * d[k[1]]
- 如果k[0] - k[1] <= 1,那么只能二选一， max(k[0] * d[k[0]], k[1] * d[k[1]])
- 如法炮制，使用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
