leetcode 740 删除并获得点数
740 删除并获得点数题意
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums ，删除它并获得 nums 的点数。之后，你必须删除 所有 等于 nums - 1 和 nums + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
案例
示例 1：
输入：nums =
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：
输入：nums =
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。思路
[*]当我们操作完nums的元素之后，必须要删除nums - 1和nums的所有元素，所以我们需要对数组做一个排序，这样nums和nums就是两个相连在一起的数据了。
[*]他又需要获取操作操作的最大点数，所以我们需要对这些数做一个汇总。
[*]然后就可以遍历处理之后的数组了。举个例子，我们处理完的数据是a_map = {1:3,4:10, 2:12，3： 13}。后面用a_map来表示这个映射，，key表示原始数据，value表示汇总之后的数据。
[*]我们就可以获取到key之后，对他进行排序并遍历。（1，2，4】
开始判断要不删除当前元素
【1， 2， 3， 5】
当删除第一个元素可以获得数就是a_map
删除第二个元素可以获得的数就是
判断第二个元素和第一个元素是否相邻的，如果是相邻的就从两个取一个最大值。如果不是就直接相加
依次排列。。。
由此我们的出的公式就是
不是相邻的
$$
s_i = a_map + s{i-1}
$$
相邻的
$$
s_i = max(a_map + nums_i, nums_{i - 1})
$$
代码
const deleteAndEarn = (nums: number[]): number => {
const map: { : number } = nums.reduce((a: { : number }, b: number): {
: number
} => {
const value = a || 0;
a = value + 1
return a
}, {})
const keys = Object.keys(map)
.sort((a, b) => parseInt(a) - parseInt(b))
.map(item => parseInt(item));
const dp = new Array(nums.length).fill(0);
// 边界情况
if (nums.length === 0) return 0;
else if (keys.length === 1) return map] * keys
// 给dp数组默认值
dp = keys * map]
// 开始写遍历
console.log(keys)
for (let i = 1; i < keys.length; i++) {
// 判断是不是属于i-1或者i+1的情况
if (keys - 1 !== keys) {
dp = keys * map] + dp;
} else {
// 这里是属于i-1或者i+1的情况
// 注意，需要注意一下当i是1时候我们要进行i-2，会有问题，所以我门这里也要单独判断一下。
let last_value: number
if (i === 1) {
last_value = 0;
} else {
last_value = dp;
}
dp = Math.max(last_value + keys * map], dp);
}
}
return dp;
}https://img-blog.csdnimg.cn/img_convert/f904fa936ec9172877be3c99b4282686.png结语
如果对您有帮助的话，您可以搜搜一下正在努力的迪迦关注一下此公众号吗？谢谢您了。
来源:https://www.cnblogs.com/dijia-blog1/p/18520852
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]