740 刪除并獲得點數(shù)

題意

給你一個整數(shù)數(shù)組 nums ，你可以對它進行一些操作。

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數(shù)。之后，你必須刪除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。

案例

示例 1：

輸入：nums = [3,4,2]
輸出：6
解釋：
刪除 4 獲得 4 個點數(shù)，因此 3 也被刪除。
之后，刪除 2 獲得 2 個點數(shù)。總共獲得 6 個點數(shù)。

示例 2：

輸入：nums = [2,2,3,3,3,4]
輸出：9
解釋：
刪除 3 獲得 3 個點數(shù)，接著要刪除兩個 2 和 4 。
之后，再次刪除 3 獲得 3 個點數(shù)，再次刪除 3 獲得 3 個點數(shù)。
總共獲得 9 個點數(shù)。

思路

1. 當我們操作完nums[i]的元素之后，必須要刪除nums[i] - 1和nums[i+1]的所有元素，所以我們需要對數(shù)組做一個排序，這樣nums[i+1]和nums[i-1]就是兩個相連在一起的數(shù)據(jù)了。
2. 他又需要獲取操作操作的最大點數(shù)，所以我們需要對這些數(shù)做一個匯總。
3. 然后就可以遍歷處理之后的數(shù)組了。舉個例子，我們處理完的數(shù)據(jù)是a_map = {1:3,4:10, 2:12，3： 13}。后面用a_map來表示這個映射，，key表示原始數(shù)據(jù)，value表示匯總之后的數(shù)據(jù)。
4. 我們就可以獲取到key之后，對他進行排序并遍歷。（1，2，4】

開始判斷要不刪除當前元素

【1， 2， 3， 5】

當刪除第一個元素可以獲得數(shù)就是a_map[i]

刪除第二個元素可以獲得的數(shù)就是

判斷第二個元素和第一個元素是否相鄰的，如果是相鄰的就從兩個取一個最大值。如果不是就直接相加

依次排列。。。

由此我們的出的公式就是

不是相鄰的
$$
s_i = a_map[nums_i] + s{i-1}
$$
相鄰的
$$
s_i = max(a_map[nums_{i-2}] + nums_i, nums_{i - 1})
$$

代碼

const deleteAndEarn = (nums: number[]): number => {
    const map: { [key: number]: number } = nums.reduce((a: { [key: number]: number }, b: number): {
        [key: number]: number
    } => {
        const value = a[b] || 0;
        a[b] = value + 1
        return a
    }, {})
    const keys = Object.keys(map)
        .sort((a, b) => parseInt(a) - parseInt(b))
        .map(item => parseInt(item));
    const dp = new Array(nums.length).fill(0);
    // 邊界情況
    if (nums.length === 0) return 0;
    else if (keys.length === 1) return map[keys[0]] * keys[0]
    // 給dp數(shù)組默認值
    dp[0] = keys[0] * map[keys[0]]
    // 開始寫遍歷
    console.log(keys)
    for (let i = 1; i < keys.length; i++) {
        // 判斷是不是屬于i-1或者i+1的情況
        if (keys[i] - 1 !== keys[i - 1]) {
            dp[i] = keys[i] * map[keys[i]] + dp[i - 1];
        } else {
            // 這里是屬于i-1或者i+1的情況
            // 注意，需要注意一下當i是1時候我們要進行i-2，會有問題，所以我門這里也要單獨判斷一下。
            let last_value: number
            if (i === 1) {
                last_value = 0;
            } else {
                last_value = dp[i - 2];
            }
            dp[i] = Math.max(last_value + keys[i] * map[keys[i]], dp[i - 1]);
        }

    }
    return dp[keys.length - 1];
}

結(jié)語
如果對您有幫助的話，您可以搜搜一下正在努力的迪迦關(guān)注一下此公眾號嗎？謝謝您了。