Ricky.L的随笔
0%

LeetCode.740.删除并获得点数（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.740.删除并获得点数（中等）

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

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

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

题解

由于要删除值相邻的元素，可以在脑海里先按元素值对nums数组排序，方便梳理题意，最终求解的东西跟数组顺序也没关系。

删除一个nums[i]获得点数后，所有nums[i] - 1和nums[i] + 1的相邻元素被删除了（不计点数），数组里剩下的所有等于nums[i]的值都还是要逐个主动删除并且计入点数的，因为它们不会因为是某个被删除元素的相邻元素而被删除，因为相邻元素从删除第一个nums[i]就删完了。

所以，假设nums[i]在数组里有c个，删除nums[i]可以获得的点数是nums[i] * c。

可以用一个数组sum记录nums数组中所有相同元素的和，以nums[i]作为sum数组的下标，方便查询点数。即sum[nums[i]] = nums[i] * c。

获取了sum[nums[i]]就不能选取sum[nums[i] - 1]和sum[nums[i] + 1]了，这就转变为打家劫舍的最优化问题。

sum数组的长度为nums数组的最大值 + 1，是一个常数空间，对性能影响可以接受。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun deleteAndEarn(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        val maxValue = nums.max()!!
        val sum = IntArray(maxValue + 1) { 0 }
        for (num in nums) {
            sum[num] += num
        }
        return rob(sum)
    }

    fun rob(nums: IntArray) : Int {
        if (nums.size == 1) return nums[0]
        var pre2 = nums[0]
        var pre1 = maxOf(nums[0], nums[1])
        var cur = pre1
        for (i in 2 until nums.size) {
            cur = maxOf(pre2 + nums[i], pre1)
            pre2 = pre1
            pre1 = cur
        }
        return cur
    }
}