C++ leetcode之刪除并獲得點(diǎn)數(shù)的示例代碼
參考鏈接
https://leetcode-cn.com/problems/delete-and-earn/
題目描述
給你一個(gè)整數(shù)數(shù)組 nums ，你可以對(duì)它進(jìn)行一些操作。
每次操作中，選擇任意一個(gè) nums[i] ，刪除它并獲得 nums[i] 的點(diǎn)數(shù)。之后，你必須刪除每個(gè)等于 nums[i] - 1 或 nums[i] + 1 的元素。
開(kāi)始你擁有 0 個(gè)點(diǎn)數(shù)。返回你能通過(guò)這些操作獲得的最大點(diǎn)數(shù)。
解題思路
本題需要明確的一點(diǎn)是，如果刪除了有多個(gè)相同值的元素，因?yàn)楸人?或小1的元素都被刪了，后面這些相同的元素還會(huì)被剩下，所以可以一次全部刪除。
回溯法
即暴力窮舉所有情況。首先用哈希表記錄所有相同元素的和，窮舉哈希表的每一個(gè)鍵，記錄下它的值，并去除哈希表中鍵比它大1和小1的值，遞歸后再恢復(fù)。（會(huì)超時(shí)?。?/p>
遞歸式動(dòng)態(tài)規(guī)劃
先對(duì)數(shù)組進(jìn)行排序，然后用哈希表記錄所有相同元素的和，同時(shí)新建一個(gè)記錄所有不重復(fù)元素的數(shù)組，這樣就可以把“狀態(tài)”設(shè)為不重復(fù)數(shù)組的索引了，狀態(tài)表存儲(chǔ)的就是當(dāng)前索引到最后一個(gè)索引間能獲得的最大點(diǎn)數(shù)?！斑x擇”就是是否刪除當(dāng)前索引處元素。如果要?jiǎng)h除當(dāng)前元素，這一步中需要判斷下一個(gè)元素與當(dāng)前元素的差是否等于1，如果等于1，就往下跳2個(gè)元素，否則跳1個(gè)元素；如果不刪除當(dāng)前元素，則直接跳一個(gè)元素。
迭代式動(dòng)態(tài)規(guī)劃
官方解法用數(shù)組代替哈希表存儲(chǔ)相同元素的元素和，這樣每個(gè)元素間的差都是1，狀態(tài)表記錄第0個(gè)元素到當(dāng)前元素能獲得的最大點(diǎn)數(shù)?！斑x擇”是是否刪除當(dāng)前元素，如果刪除，點(diǎn)數(shù)為當(dāng)前元素與第0個(gè)元素到前2個(gè)元素的最大點(diǎn)數(shù)和，如果不刪，就是第0個(gè)元素到前一個(gè)元素的最大點(diǎn)數(shù)。
排序 + 動(dòng)態(tài)規(guī)劃
同樣是官方的最優(yōu)解法，若 nums 中不存在某個(gè)元素 x，則選擇任一小于 x 的元素不會(huì)影響到大于 x 的元素的選擇。因此我們可以將 nums 排序后，將其劃分成若干連續(xù)子數(shù)組，子數(shù)組內(nèi)任意相鄰元素之差不超過(guò) 1。對(duì)每個(gè)子數(shù)組按照方法一的動(dòng)態(tài)規(guī)劃過(guò)程計(jì)算出結(jié)果，累加所有結(jié)果即為答案。
代碼
回溯法
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
unordered_map<int, int> mp;
for (int num : nums)
{
mp[num] += num;
}
int res = Earn(mp);
return res;
}
int Earn(unordered_map<int, int>& mp)
{
int res = 0;
for (auto& item : mp)
{
if (mp[item.first] == 0)
{
continue;
}
int sum = mp[item.first];
mp[item.first] = 0;
int prev_plus_1 = mp[item.first + 1];
int prev_sub_1 = mp[item.first - 1];
mp[item.first + 1] = 0;
mp[item.first - 1] = 0;
res = max(res, sum + Earn(mp));
mp[item.first] = sum;
mp[item.first + 1] = prev_plus_1;
mp[item.first - 1] = prev_sub_1;
}
return res;
}
};
遞歸式動(dòng)態(tài)規(guī)劃
class Solution {
public:
unordered_map<int, int> memo;
int deleteAndEarn(vector<int>& nums) {
sort(nums.begin(), nums.end());
unordered_map<int, int> mp;
vector<int> unique;
int tmp = INT_MAX;
for (int num : nums)
{
if (tmp != num)
{
unique.push_back(num);
tmp = num;
}
mp[num] += num;
}
unique.push_back(INT_MAX);
int res = dp(mp, unique, 0);
return res;
}
int dp(unordered_map<int, int>& mp, vector<int>& nums, int start)
{
if (start + 1 >= nums.size())
{
return 0;
}
if (memo.count(start) == 1)
{
return memo[start];
}
int do_it = 0;
if (nums[start] - nums[start + 1] == 1 || nums[start + 1] - nums[start] == 1)
{
do_it = mp[nums[start]] + dp(mp, nums, start + 2);
}
else
{
do_it = mp[nums[start]] + dp(mp, nums, start + 1);
}
int not_do = dp(mp, nums, start + 1);
memo[start] = max(do_it, not_do);
return max(do_it, not_do);
}
};
迭代式動(dòng)態(tài)規(guī)劃
class Solution {
private:
int rob(vector<int> &nums) {
int size = nums.size();
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
public:
int deleteAndEarn(vector<int> &nums) {
int maxVal = 0;
for (int val : nums) {
maxVal = max(maxVal, val);
}
vector<int> sum(maxVal + 1);
for (int val : nums) {
sum[val] += val;
}
return rob(sum);
}
};
排序 + 動(dòng)態(tài)規(guī)劃
class Solution {
private:
int rob(vector<int> &nums) {
int size = nums.size();
if (size == 1) {
return nums[0];
}
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
public:
int deleteAndEarn(vector<int> &nums) {
int n = nums.size();
int ans = 0;
sort(nums.begin(), nums.end());
vector<int> sum = {nums[0]};
for (int i = 1; i < n; ++i) {
int val = nums[i];
if (val == nums[i - 1]) {
sum.back() += val;
} else if (val == nums[i - 1] + 1) {
sum.push_back(val);
} else {
ans += rob(sum);
sum = {val};
}
}
ans += rob(sum);
return ans;
}
};
到此這篇關(guān)于C++ leetcode之刪除并獲得點(diǎn)數(shù)的示例代碼的文章就介紹到這了,更多相關(guān)C++ leetcode內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語(yǔ)言字符串快速壓縮算法代碼，將字符串中連續(xù)出席的重復(fù)字母進(jìn)行壓縮，其主要的壓縮字段的格式為”字符重復(fù)的次數(shù)+字符”。有需要的小伙伴參考下吧。2015-03-03
關(guān)于C/C++中可變參數(shù)的詳細(xì)介紹(va_list,va_start,va_arg,va_end)
可變參數(shù)的函數(shù)原理其實(shí)很簡(jiǎn)單,而va系列是以宏定義來(lái)定義的,實(shí)現(xiàn)跟堆棧相關(guān).我們寫(xiě)一個(gè)可變函數(shù)的C函數(shù)時(shí),有利也有弊,所以在不必要的場(chǎng)合,我們無(wú)需用到可變參數(shù)。如果在C++里,我們應(yīng)該利用C++的多態(tài)性來(lái)實(shí)現(xiàn)可變參數(shù)的功能,盡量避免用C語(yǔ)言的方式來(lái)實(shí)現(xiàn)2013-10-10
C++入門(mén)基礎(chǔ)之命名空間、輸入輸出和缺省參數(shù)
C++入門(mén)基礎(chǔ)篇的內(nèi)容為C++的基本特性,只有在掌握C++的基本特性后,是進(jìn)入后面類和對(duì)象學(xué)習(xí)的基礎(chǔ),下面這篇文章主要給大家介紹了關(guān)于C++入門(mén)基礎(chǔ)之命名空間、輸入輸出和缺省參數(shù)的相關(guān)資料,需要的朋友可以參考下2023-01-01
Qt圖形圖像開(kāi)發(fā)之曲線圖表庫(kù)QChart編譯安裝詳細(xì)方法與使用實(shí)例
這篇文章主要介紹了Qt圖形圖像開(kāi)發(fā)之曲線圖表庫(kù)QChart編譯安裝詳細(xì)方法與使用實(shí)例,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C++模板特化與偏特化的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08
C語(yǔ)言中#define與typedef的互換細(xì)節(jié)詳解
本篇文章是對(duì)C語(yǔ)言中#define與typedef的互換細(xì)節(jié)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表中的增刪改(頭插頭刪)教程示例詳解
這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表中增刪改關(guān)于頭插頭刪的教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
QT使用SQLite數(shù)據(jù)庫(kù)超詳細(xì)教程(增刪改查、對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新)
這篇文章主要給大家介紹了關(guān)于QT使用SQLite數(shù)據(jù)庫(kù)的相關(guān)資料,其中包括增刪改查以及對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新,SQLite是一種嵌入式關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng),它是一個(gè)軟件庫(kù),提供了一個(gè)自包含、無(wú)服務(wù)器、零配置的、事務(wù)性的SQL數(shù)據(jù)庫(kù)引擎,需要的朋友可以參考下2024-01-01
本篇文章是對(duì)用C語(yǔ)言去除字符串兩邊空字符的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++實(shí)現(xiàn)LeetCode(648.替換單詞)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(648.替換單詞),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08