740. Delete and Earn

leetcode medium

#array#csharp#dynamic-programming#hash-table#leetcode#math#medium#sort#stack

Task

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]

Output: 6

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public int DeleteAndEarn(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (var num in nums) {
            if (!count.ContainsKey(num)) {
                count[num] = 0;
            }
            count[num]++;
        }
        
        int avoid = 0, using = 0, prev = -1;
        foreach (var num in count.Keys.OrderBy(x => x)) {
            if (num - 1 != prev) {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + Math.Max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.Max(avoid, using);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int DeleteAndEarn(vector<int>& nums) {
        var count = new unordered_map<int, int>();
        foreach (var num in nums) {
            if (!count.count(num)) {
                count[num] = 0;
            }
            count[num]++;
        }
        
        int avoid = 0, using = 0, prev = -1;
        foreach (var num in count.Keys.OrderBy(x => x)) {
            if (num - 1 != prev) {
                int newAvoid = max(avoid, using);
                using = num * count[num] + max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = max(avoid, using);
                using = num * count[num] + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return max(avoid, using);
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int avoid = 0, using = 0, prev = -1;
        for (int num : count.keySet().stream().sorted().mapToInt(Integer::intValue).toArray()) {
            if (num - 1 != prev) {
                int newAvoid = Math.max(avoid, using);
                using = num * count.get(num) + Math.max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.max(avoid, using);
                using = num * count.get(num) + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.max(avoid, using);
    }
}

JavaScript solution

matched/original

var deleteAndEarn = function(nums) {
    const count = {};
    nums.forEach(num => count[num] = (count[num] || 0) + 1);
    
    let prev = null;
    let avoid = 0, using = 0;
    
    Object.keys(count).sort((a, b) => a - b).forEach(num => {
        num = parseInt(num);
        if (num - 1 !== prev) {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + Math.max(avoid, using);
            avoid = newAvoid;
        } else {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + avoid;
            avoid = newAvoid;
        }
        prev = num;
    });
    
    return Math.max(avoid, using);
};

Python solution

matched/original

def deleteAndEarn(nums):
    from collections import Counter
    
    count = Counter(nums)
    prev = None
    avoid = using = 0
    
    for num in sorted(count):
        if num - 1 != prev:
            new_avoid, new_using = max(avoid, using), num * count[num] + max(avoid, using)
        else:
            new_avoid, new_using = max(avoid, using), num * count[num] + avoid
        avoid, using = new_avoid, new_using
        prev = num
    
    return max(avoid, using)

Go solution

matched/original

package main

import "sort"

func deleteAndEarn(nums []int) int {
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    uniqueNums := make([]int, 0, len(count))
    for num := range count {
        uniqueNums = append(uniqueNums, num)
    }
    sort.Ints(uniqueNums)

    avoid, using, prev := 0, 0, -1
    for _, num := range uniqueNums {
        if num-1 != prev {
            newAvoid := max(avoid, using)
            using = num*count[num] + max(avoid, using)
            avoid = newAvoid
        } else {
            newAvoid := max(avoid, using)
            using = num*count[num] + avoid
            avoid = newAvoid
        }
        prev = num
    }

    return max(avoid, using)
}

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

Explanation

Algorithm

Подсчитайте количество каждого числа в массиве nums.

Используйте динамическое программирование для расчета максимальных очков, которые можно заработать, используя накопленный результат для чисел, меньших текущего. Добавьте текущий день в стек.

Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎