首页 > 其他分享 >leetcode 740 删除并获得点数

leetcode 740 删除并获得点数

时间:2024-11-01 17:09:13浏览次数:1  
标签:740 map 删除 nums keys number 点数 leetcode

740 删除并获得点数

题意

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

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

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

案例

示例 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 个点数。

思路

  1. 当我们操作完nums[i]的元素之后,必须要删除nums[i] - 1和nums[i+1]的所有元素,所以我们需要对数组做一个排序,这样nums[i+1]和nums[i-1]就是两个相连在一起的数据了。
  2. 他又需要获取操作操作的最大点数,所以我们需要对这些数做一个汇总。
  3. 然后就可以遍历处理之后的数组了。举个例子,我们处理完的数据是a_map = {1:3,4:10, 2:12,3: 13}。后面用a_map来表示这个映射,,key表示原始数据,value表示汇总之后的数据。
  4. 我们就可以获取到key之后,对他进行排序并遍历。(1,2,4】

开始判断要不删除当前元素

【1, 2, 3, 5】

当删除第一个元素可以获得数就是a_map[i]

删除第二个元素可以获得的数就是

判断第二个元素和第一个元素是否相邻的,如果是相邻的就从两个取一个最大值。如果不是就直接相加

依次排列。。。

由此我们的出的公式就是

不是相邻的
$$
s_i = a_map[nums_i] + s{i-1}
$$
相邻的
$$
s_i = max(a_map[nums_{i-2}] + nums_i, nums_{i - 1})
$$

代码

const deleteAndEarn = (nums: number[]): number => {
    const map: { [key: number]: number } = nums.reduce((a: { [key: number]: number }, b: number): {
        [key: number]: number
    } => {
        const value = a[b] || 0;
        a[b] = 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[0]] * keys[0]
    // 给dp数组默认值
    dp[0] = keys[0] * map[keys[0]]
    // 开始写遍历
    console.log(keys)
    for (let i = 1; i < keys.length; i++) {
        // 判断是不是属于i-1或者i+1的情况
        if (keys[i] - 1 !== keys[i - 1]) {
            dp[i] = keys[i] * map[keys[i]] + dp[i - 1];
        } else {
            // 这里是属于i-1或者i+1的情况
            // 注意,需要注意一下当i是1时候我们要进行i-2,会有问题,所以我门这里也要单独判断一下。
            let last_value: number
            if (i === 1) {
                last_value = 0;
            } else {
                last_value = dp[i - 2];
            }
            dp[i] = Math.max(last_value + keys[i] * map[keys[i]], dp[i - 1]);
        }

    }
    return dp[keys.length - 1];
}

截屏2024-10-25 00.09.10结语
如果对您有帮助的话,您可以搜搜一下正在努力的迪迦关注一下此公众号吗?谢谢您了。

标签:740,map,删除,nums,keys,number,点数,leetcode
From: https://www.cnblogs.com/dijia-blog1/p/18520852

相关文章

  • Leetcode 3259. 超级饮料的最大强化能量
    动态规划。f[i][0/1]表示前i个且最后选A或B的方案的集合。所以f[i][0]=max(f[i-1][0],f[i-2][1])+A[i]。f[i][1]同理。1typedeflonglongLL;2constintN=1e5+10;3LLf[N][2];4classSolution{5public:6LLmaxEnergyBoost(vector<int>&A,vector<i......
  • Leetcode—624. 数组列表中的最大距离【中等】
    2024每日刷题(198)Leetcode—624.数组列表中的最大距离实现代码classSolution{public:intmaxDistance(vector<vector<int>>&arrays){intm=arrays.size();intn=arrays[0].size();intmn=arrays[0][0];intmx=ar......
  • Leetcode21:合并两个有效链表
    原题地址:.-力扣(LeetCode)题目描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=......
  • Leetcode每日一题 3216. 交换后字典序最小的字符串
    Leetcode每日一题##3216.交换后字典序最小的字符串###C++给你一个仅由数字组成的字符串s,在最多交换一次相邻且具有相同奇偶性的数字后,返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数,则它们具有相同的奇偶性。例如,5和9、2和4奇偶性相同,而......
  • leetcode560 和为k的子数组
    leetcode560和为k的子数组packagejava2024_10.day30;importjava.util.HashMap;publicclassleetcode560{/*思路:前缀和+哈希表a[j]-a[i]=k即a[i]=a[j]-k遍历到下标j的时候,先判a[j]==k,相等就ans++,然后查哈希表中a[j]-k的数的个数,然后把a[j]放入哈希......
  • Leetcode刷题Python之3165.不包含相邻元素的子序列的最大和
    提示:利用线段树解决不包含相邻元素的子序列最大和问题。文章目录一、题目描述示例二、解题思路1.思路分析2.线段树的状态设计3.线段树的操作三、代码实现代码详细解释四、总结时间复杂度分析一、题目描述给定一个整数数组nums和一个二维数组queries,其中q......
  • ​Leetcode 166.珠宝的最高价值​ 网格图dp C++实现
    问题:Leetcode166.珠宝的最高价值现有一个记作二维矩阵 frame 的珠宝架,其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为:只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下角时,停止拿取注意:珠宝的价值都是大于0的。除非这个......
  • LeetCode30.串联所有单词的子串
    题目链接:30.串联所有单词的子串-力扣(LeetCode)1.暴力解法(会超时)由于题目中要判断s中是否有子串符合words,于是可以定义一个hashMap来存储words中的字符串的信息;定义变量len表示words中字符串的数目,strLen表示每个字符串的长度(words中的字符串长度相同);遍历s,每次取出长为len......
  • Leetcode每日一题C之3211. 生成不含相邻零的二进制字符串
    1、执行结果:通过2、显示详情:3、题目:  给你一个正整数 n。如果一个二进制字符串 x 的所有长度为2的子字符串中包含 至少 一个 "1",则称 x 是一个 有效 字符串。返回所有长度为 n 的 有效 字符串,可以以任意顺序排列。示例1:输入: n=3输出: ["010","01......
  • Leetcode每日一题C之3216. 交换后字典序最小的字符串
     1、执行结果:通过2、显示详情:3、题目:  给你一个仅由数字组成的字符串 s,在最多交换一次 相邻 且具有相同 奇偶性 的数字后,返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数,则它们具有相同的奇偶性。例如,5和9、2和4奇偶性相同,而6和9奇偶......