Leetcode 740.删除与获得点数

Posted on |

740. 删除与获得点数

题目

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 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 个点数。

注意:

nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。

方法

方法1：动态规划

观察问题的关键之处

  • nums的顺序无关
  • 一旦决定要num，就可以将所有出现的num添加到最后获取的点数中

条件是删除（不能取）临近的值，这类似于“打家劫舍”（不能打劫临近的房子）。将nums转化为points数组，nums中值为x多个数字累加并置于points[x]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        points=[0]*(max(nums)+1)
        for n in nums:
            points[n]+=n

        pre,cur=0,0
        for value in points:
            pre,cur=cur,max(pre+value,cur)
        return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        points=collections.Counter(nums)
        pre,cur=0,0

        for value in range(max(nums)+1):
            pre,cur=cur,max(pre+value*points[value],cur)
        return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        new_nums=[0]*(max(nums)+1)    # 将nums处理成打家劫舍问题中的形式
        for n in nums:
            new_nums[n]+=n

        dp=[0]*(len(new_nums)+1)
        dp[1]=new_nums[1]

        for i in range(2,len(new_nums)):
            dp[i]=max(dp[i-1],dp[i-2]+new_nums[i])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        n=len(nums)
        points=[0]*(max(nums)+1)
        for n in nums:
            points[n]+=n

        dp=[0]*len(points)
        dp[0]=points[0]
        dp[1]=max(points[0],points[1])
        for i in range(2,len(points)):
            dp[i]=max(dp[i-1],dp[i-2]+points[i])
        return max(dp)