LeetCode

Appearance

740. Delete and Earn ​

题目 ​

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

  • Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

 

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104
Related Topics
  • 数组
  • 哈希表
  • 动态规划

  • 👍 1137
  • 👎 0

    • 思路 ​

    确定动态转移方程，dp[i] 的定义是什么，本题不是给定数组直接选择 dp， 假设原数组是：

    [2,2,3,3,3,4]

    转换成 hash

    key = nums[i] value = sum of nums[i]

    { 2: 4 3: 9 4: 1 } 目标遍历数组可以 hash.keys 经过排序后设置为转移方程的数组

    keys = [2，3，4]

    此时动态规划方程设置

    dp[i] = dp[i - 2] + hash[keys[i]] if keys[i] - 1 == keys[i-1] else dp[i - 1] + hash[i]

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
from collections import defaultdict


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        hash = defaultdict(int)
        for i in range(len(nums)):
            hash[nums[i]] += nums[i]

        keys = sorted(hash.keys())
        dp = [0] * len(keys)

        dp[0] = hash[keys[0]]
        if len(keys) > 1: dp[1] = max(hash[keys[0]], hash[keys[1]]) if keys[0] + 1 == keys[1] else hash[keys[0]] + hash[keys[1]]
        for i in range(2, len(keys)):
            if keys[i] - 1 == keys[i - 1]:
                dp[i] = max(dp[i - 2] + hash[keys[i]], dp[i - 1])
            else:
                dp[i] = dp[i - 1] + hash[keys[i]]

        return dp[-1]


        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • U 为数组中的key的长度
    • 时间复杂度 O(UlogU)
    • 空间复杂度 O(N)