LeetCode如何实现删除与获得点数

发布时间:2021-12-15 10:51:48 作者:小新
来源:亿速云 阅读:93

小编给大家分享一下LeetCode如何实现删除与获得点数,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

1

 题目描述

给定一个整数数组 nums ,每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数,同步删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。初始点数为0,返回可获得的最大点数。如:nums=[3,4,2],返回6。(首先选择4,积累4点数,同时删除3,再选择2,再积累2点数,总共为6。其他方式积累的点数均小于6)

2

 题解

思路:动态规划
通过题目要求,首先要明确一点是:  当选择了一个值获得其点数  ,则其他相同的值  也会选择。  因为当选择一个值时,  相邻值已被  删除,因此  其他相同的值不会被删除,一定会选择到。因此可以建立一个列表value,以值作为下标,记录选择每个值时对应可获得的点数。如:[2,2,3,3,4],value[2]=2*2,value[3]=3*2,value[4]=4*1,所以最后得到value=[0,0,4,6,4]。
class Solution:    def deleteAndEarn(self, nums: List[int]) -> int:        if not nums:            return 0        dp = [0]*(max(nums)+1)        value = dp.copy()        #value = [0]*(max(nums)+1)        for i,a in enumerate(nums):            value[a]+=a        dp[1] = value[1]        for i in range(2,max(nums)+1):            dp[i]=max(dp[i-1],dp[i-2]+value[i])        return dp[-1]

以上是“LeetCode如何实现删除与获得点数”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. leetcode--删除链表中的节点
  2. LeetCode如何删除链表中指定的所有元素

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:如何进行Apache Kafka 2.7.0加速移除Zookeeper的分析

下一篇:leetcode如何实现最长湍流子数组

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》