• 欢迎光临~

力扣---740. 删除并获得点数

开发技术 开发技术 2022-12-14 次浏览

给你一个整数数组 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 个点数。

提示:
    1 <= nums.length <= 2 * 104
    1 <= nums[i] <= 104

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

本题和小偷那题很相似https://www.cnblogs.com/allWu/p/16978811.html

假设有一个数是 n ,那么比 n - 1 小的数可获得的最大点数都对 n 没有影响,即 在数字 n 时 可获得的最大点数等于:1、比 n - 1 小的数可获得的最大点数之和加上数字 n 可获得的点数。                                                     2、n - 1时可获得的最大点数。

两者取最大值即可。

当 n 从 0 逐渐增大到最大的数字时,也将逐渐接近可获得的最大点数。

代码如下:

 1 class Solution {
 2     public int deleteAndEarn(int[] nums) {
 3         int maxVal = 0;
 4         for (int val : nums) {
 5             maxVal = Math.max(maxVal, val);
 6         }
 7         // 定义一个长度为nums中最大数字 + 1 的数组,将 第 0 个位置不填,可以直接将数组下标作为对应的数字。
 8         int[] arr = new int[maxVal + 1];
 9         for (int a : nums) {
10             arr[a] += a;
11         }
12         
13         // 此处和小偷那道题几乎相同。
14         int max1 = arr[0];
15         int max2 = Math.max(arr[0], arr[1]);
16         for (int i = 2; i < arr.length; i ++) {
17             int tem = Math.max(max1 + arr[i], max2);
18             max1 = max2;
19             max2 = tem;
20         }
21         return max2;
22     }
23 }

运行结果如下:

力扣---740. 删除并获得点数

 

程序员灯塔
转载请注明原文链接:力扣---740. 删除并获得点数
喜欢 (0)