网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

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

小编给大家分享一下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]。
  • 中间状态:此处中间状态dp[i]表示从1选择到i可获得的最大点数。

  • 状态转移:一个值在整个过程中只有被删除和被获取点数两个可能,并且获取与否会影响其他数值的被选择情况。因此新来一个数,要么不选,则此时dp[i]=dp[i-1];如果选,则i-1就不能选,此时dp[i]=dp[i-2]+value[i],所以最终dp[i]=max(dp[i-1],dp[i-2]+value[i])。

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如何实现删除与获得点数”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


网页名称:LeetCode如何实现删除与获得点数
本文网址:http://bjjierui.cn/article/gjesoj.html

其他资讯