删除获得点数
题目:删除并获得点数 给你一个整数数组 nums ,你可以对它进行一些操作。
每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
根据题目删除i时得到点数i同时删除i-1和i+1,这点跟上一道题打家劫舍十分相识,如果选择了某一家那么他的上一家和下一家就不能被选择。
通过这个样的思路首先我们要构造点数的数字,如果选择3那么所有的3都可以被获得,相当于打家劫舍中的第三家金钱为3*3的数量、第二家和第四家不能再选,如下得到点数数组
let max = Math.max(...nums)
let arrTemp = new Array(max + 1).fill(0)
for(let i = 0; i < nums.length;i++) {
arrTemp[nums[i]] += nums[i]
}
1
2
3
4
5
2
3
4
5
从0到最大值将所有点数的值统计到数组中,下标为原数组nums值,arrTemp[i]为nums中所有值为i的合计。将上面得到数组调用打家劫舍的求取最大值算法,就可得到最大可获得的点数。完整代码如下:
var deleteAndEarn = function(nums) {
let max = Math.max(...nums)
let arrTemp = new Array(max + 1).fill(0)
for(let i = 0; i < nums.length;i++) {
arrTemp[nums[i]] += nums[i]
}
let arr = new Array(arrTemp.length + 1)
arr[0] = 0, arr[1] = arrTemp[0],arr[2]=Math.max(arrTemp[0], arrTemp[1])
for(let i = 3; i<= arrTemp.length; i++) {
arr[i] = Math.max(arr[i - 2] + arrTemp[i - 1], arr[i - 3] + arrTemp[i - 2])
}
return arr[arrTemp.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
上次更新: 2025/09/05, 8:09:00