740. 删除并获得点数

题目来源: 740. 删除并获得点数 // 给你一个整数数组 nums ,你可以对它进行一些操作。 // 每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。 // 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 官方解题:
/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function(nums) {
    const rob =(nums)=>{
        const size = nums.length;
        if(size == 1){
            return nums[0];
        }
        let [f,s] = [nums[0], Math.max(nums[0],nums[1])];
        for(let i=2;i<size;i++){
            [f,s] = [s, Math.max(f+nums[i],s)]
        }
        return s;
    }
    let n = nums.length;
    let res = 0;
    nums.sort((a,b)=>a-b);
    let sums = [nums[0]];
    for(let i=1;i<n;i++){
        let val = nums[i];
        if(val === nums[i-1]){
            sums[sums.length-1] +=val;
        }else if(val === nums[i-1] + 1){
            sums.push(val)
        }else{
            // console.log('-1--',res,sums)
            res += rob(sums);
            sums = [val]
        }
    }
    // console.log('-2--',res,sums)
    res += rob(sums);
    return res;
}; 
let nums = [3,4,2];
console.log(nums, deleteAndEarn(nums))
nums = [2,2,3,3,3,4,5,7,8,9,10,11,12];
console.log(nums, deleteAndEarn(nums))

个人解题:

var deleteAndEarn = function(nums) {
    let max = Math.max(...nums)+1;
    let sums=new Array(max).fill(0);
    for(let num of nums)
    {
        sums[num] +=num;
    }

    let dp = new Array(max).fill(0);
    dp[1] = sums[1];
    for(let i=2;i<max;i++){
        dp[i] = Math.max(dp[i-2]+sums[i], dp[i-1]);
    }
    return dp;
    // const rob =(nums)=>{
    //     const size = nums.length;
    //     if(size == 1){
    //         return nums[0];
    //     }
    //     let [f,s] = [nums[0], Math.max(nums[0],nums[1])];
    //     for(let i=2;i<size;i++){
    //         [f,s] = [s, Math.max(f+nums[i],s)]
    //     }
    //     return s;
    // }
    // return rob(sums);
}; 


nums = [2,2,3,3,3,4,5,7,8,9,10,11,12];
console.log(nums, deleteAndEarn(nums))

官方解题的亮点是使用两个变量优化了状态转移方程所用到的数组

 

// 示例 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

 

上一篇:微信小程序用canvas 绘制虚线


下一篇:【树叶识别】HU不变矩树叶识别【Matlab 740期】