删除并获得点数

740. 删除并获得点数

给你一个整数数组 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 * 10⁴
1 <= nums[i] <= 10⁴

相似题目

打家劫舍

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int deleteAndEarn(vector<int>& nums) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-16 11:19:40

impl Solution {
    pub fn delete_and_earn(nums: Vec<i32>) -> i32 {
        let mut sum = vec![0; *nums.iter().max().unwrap() as usize + 1];
        nums.iter().for_each(|&val| sum[val as usize] += val);
        sum.iter().fold((0, 0), |(f, s), x| (s, s.max(f + x))).1
    }

    pub fn delete_and_earn2(nums: Vec<i32>) -> i32 {
        let mut sum = vec![0; *nums.iter().max().unwrap() as usize + 1];
        nums.iter().for_each(|&n| sum[n as usize] += n);
        let (mut first, mut second) = (sum[0], sum[0].max(sum[1]));
        sum.iter().skip(2).for_each(|&val| {
            let cur = second.max(first + val);
            first = second;
            second = cur;
        });
        first.max(second)
    }

    /// 对于取值 x，如果取了，就不能取他临近的值，这与打劫相邻的房子类似
    /// 一间房子的价值等于 x 出现的次数乘以 x，因为删除邻居之后可以放心取完所有 x
    /// dp[i] = max(dp[i-1], dp[i-2]+cost[i])
    pub fn delete_and_earn3(nums: Vec<i32>) -> i32 {
        // init value arr with `maxVal + 1`
        let mut val = vec![0; (*nums.iter().max().unwrap_or(&0)) as usize + 1];

        // calc value arr in 198. 打家劫舍
        nums.iter().for_each(|&x| {
            val[x as usize] += x;
        });

        // calc result
        val.iter().fold((0, 0), |(a, b), &x| (b, b.max(a + x))).1
    }

    pub fn delete_and_earn4(nums: Vec<i32>) -> i32 {
        let mut d = vec![0; 10004];
        for v in nums.iter() {
            let i = *v as usize;
            d[i] += *v;
        }
        let (mut a, mut b) = (0, 0);
        for i in 0..10004 {
            let c = b.max(a + d[i]);
            a = b;
            b = c;
        }
        b
    }
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 43.2 MB, 提交时间: 2023-09-16 11:17:37

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function(nums) {
    let maxVal = 0;
    for (const val of nums) {
        maxVal = Math.max(maxVal, val);
    }
    const sum = new Array(maxVal + 1).fill(0);
    for (const val of nums) {
        sum[val] += val;
    }
    return rob(sum);
};

const rob = (nums) => {
    const size = nums.length;
    let first = nums[0], second = Math.max(nums[0], nums[1]);
    for (let i = 2; i < size; i++) {
        let temp = second;
        second = Math.max(first + nums[i], second);
        first = temp;
    }
    return second;
}

python3 解法, 执行用时: 60 ms, 内存消耗: 17.4 MB, 提交时间: 2023-09-16 11:17:23

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        maxVal = max(nums)
        total = [0] * (maxVal + 1)
        for val in nums:
            total[val] += val
        
        def rob(nums: List[int]) -> int:
            size = len(nums)
            first, second = nums[0], max(nums[0], nums[1])
            for i in range(2, size):
                first, second = second, max(first + nums[i], second)
            return second
        
        return rob(total)

java 解法, 执行用时: 2 ms, 内存消耗: 42 MB, 提交时间: 2023-09-16 11:16:44

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    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;
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 11.6 MB, 提交时间: 2023-09-16 11:16:33

class Solution {
private:
    int rob(vector<int> &nums) {
        int size = nums.size();
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = max(maxVal, val);
        }
        vector<int> sum(maxVal + 1);
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }
};

golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2021-07-18 09:14:48

func deleteAndEarn(nums []int) int {
    maxVal := 0
    for _, val := range nums {
        maxVal = max(maxVal, val)
    }
    sum := make([]int, maxVal+1)
    for _, val := range nums {
        sum[val] += val  // 相同的数之和
    }
    return rob(sum)  // 转为打家劫舍问题
}

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    first, second := nums[0], max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        first, second = second, max(first+nums[i], second)
    }
    return second
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2021-07-18 09:13:49

func deleteAndEarn(nums []int) int {
    maxVal := 0
    for _, val := range nums {
        maxVal = max(maxVal, val)
    }
    sum := make([]int, maxVal+1)
    for _, val := range nums {
        sum[val] += val  // 相同的数之和
    }
    return rob(sum)
}

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    first, second := nums[0], max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        first, second = second, max(first+nums[i], second)
    }
    return second
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

上一题

下一题

详情