[leetcode]問題解答と解説。740. Delete and Earn [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
【740. Delete and Earn】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

森田賢二のleetCode

[leetcode] 740. Delete and Earn ルール

整数の配列numsが与えられている．あなたは以下の操作を任意の回数行うことで得られる点数を最大化したい。

nums[i]を選んで削除し、nums[i]点を獲得する。その後、nums[i] - 1 に等しい要素と nums[i] + 1 に等しい要素をすべて削除しなければならない。
上記の操作を何回か適用して獲得できるポイントの最大値を返せ。

exampleは実際の問題ページを見てください

[leetcode] 740. Delete and Earn 問題ページ

740. Delete and Earn

[leetcode] 740. Delete and Earn

my code is not good(time out & not good)

var deleteAndEarn = function(nums) {
    let i = 1
    let earn = 0
    while(i < nums.length){
        earn += nums[i]
        delete nums[i]
        if(nums[i+1] === nums[i] + 1) while(nums[i+1] === (nums[i] + 1)){ delete nums[i++]}
        if(nums[i-1] === nums[i] -1) while(nums[i-1] === (nums[i] - 1)){ delete nums[i--]}
        i = 0
    }
    return earn
};

時間切れ

[leetcode] 740. Delete and Earn。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない

JavaScriptでfilterされている、discussはこちらから

気に入った解答1

シンプルだったので

var deleteAndEarn = function(nums) {
    const n = Math.max(...nums) + 1 // 一番多い要素
    const counts = new Array(n).fill(0); // ０埋め

    for (const num of nums) counts[num]++; // その数が何個あるかを保存しておく。削除するなら全部ポイントを稼げるため

    const dp = new Array(n).fill(0); // どのくらい稼いだかを都度保存する用
    dp[1] = counts[1]; // dp[0]は0なので省略

    for (let i = 2; i < n; i++) {
        const points = counts[i] * i; // 何個あるか。その分だけpoint
        dp[i] = Math.max(dp[i - 2] + points, dp[i - 1]); // -2戻ってたす方が多いのかそれとも前回の方が多いのか、多い方を最高記録として保存
    }

    return dp[n - 1]; // 最後まで積算されてきた数字返す
}

• countとdpを作ることが浮かぶかどうか
• dpだと気づくかどうか
• earn問題だと気づくかどうか

[leetcode] 740. Delete and Earn をやってみて感想

カテゴリー leetCode