740. Delete and Earn

LeetCode medium original: C# #array #csharp #dynamic-programming #hash-table #leetcode #math #medium #sort #stack

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

Ví dụ:

Input: nums = [3,4,2]

Output: 6

C# lời giải

đã khớp/gốc

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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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
}

Algorithm

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

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

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.