【LeetCode】删除并获得点数 Java 题解

关注

发布于: 2021 年 05 月 05 日

题目描述

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

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

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

示例 1：
输入：nums = [3,4,2]输出：6解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/delete-and-earn著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路

一般求最值的问题，动态规划是一种很好用的解法，我们可以按照动态规划的思路来思考分析问题。
这个题目认真分析之后，发现和之前做过的打家劫舍问题很像。我们可以转换成为打家劫舍问题。

AC 代码

class Solution {    public int deleteAndEarn(int[] nums) {        int maxVal = 0;
        for (int num : nums) {            maxVal = Math.max(num, maxVal);        }
        int[] sum = new int[maxVal + 1];        for (int num : nums) {            sum[num] += num;        }        int ans = 0;        ans = rob(sum);        return ans;    }
    public int rob(int[] nums) {        int size = nums.length;        int first = nums[0], second = Math.max(nums[0], nums[1]);        for (int i = 2; i < size; i++) {            int temp = second;            second = Math.max(first + nums[i], second);            first = temp;        }        return second;    }}

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 2021 年 05 月 05 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/37eaee11125c3889c70aff663】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】删除并获得点数 Java 题解

题目描述

思路

AC 代码

总结

HQ数字卡

评论