跳到主要内容

点数题库

删除与获得点数​

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

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[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 个点数。

方案A 动态规划​

思路: 在选择了元素 x 后，该元素以及所有等于 x-1 或 x+1 的元素会从数组中删去。若还有多个值为 x 的元素，由于所有等于 x-1 或 x+1 的元素已经被删除，我们可以直接删除 x 并获得其点数。因此若选择了 x，所有等于 x 的元素也应一同被选择，以尽可能多地获得点数

  • 通过 sum 记录 nums 中所有相同元素之和: sum[x]=x+x……
  • 在数组 sum 中，选择了下标 x ，则无法选择 x-1 和 x+1 ，转移为打家劫舍问题
    1. 状态定义: 用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额
    2. 状态转移方程: 对于第 k (k>2) 间房屋，有两个选项：
      • 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
      • 不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
      • 在两个选项中选择偷窃总金额较大的选项
      • 可得状态转移方程: dp[i]=max(dp[i−2]+nums[i],dp[i−1])
    3. 初始状态:
      • dp[0]=nums[0] 只有一间房屋，则偷窃该房屋
      • dp[1]=max(nums[0],nums[1]) 只有两件房屋，选择其中金额较高的房屋进行偷窃
    4. 问题答案:
    5. 优化空间:

:::details 点击查看代码

function rob(nums){
    let dp0=nums[0];
    let dp1=Math.max(nums[0],nums[1]);
    for(let i=2;i<nums.length;i++){
        let temp=dp1;
        dp1=Math.max(dp0+nums[i],dp1);
        dp0=temp;
    }
    return dp1;
}
function deleteAndEarn(nums) {
    let max=nums[0];
    for(let item of nums){
        max=Math.max(max,item);
    }
    let sum=new Array(max+1).fill(0);
    for(let item of nums){
        sum[item]+=item;
    }
    return rob(sum);
};

:::

性能分析:

  • 时间复杂度：O(N+M)，其中 N 是数组 nums 的长度，M 是 nums 中元素的最大值。
  • 空间复杂度：O(M)。