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 的元素。
開始你擁有 0 個(gè)點(diǎn)數(shù)。返回你能通過這些操作獲得的最大點(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)任意相鄰元素之差不超過 1。對(duì)每個(gè)子數(shù)組按照方法一的動(dòng)態(tài)規(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++使用遞歸方法求n階勒讓德多項(xiàng)式完整實(shí)例
這篇文章主要介紹了C++使用遞歸方法求n階勒讓德多項(xiàng)式,涉及C++遞歸算法與浮點(diǎn)數(shù)運(yùn)算的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2016-05-05
詳解C語言中不同類型的數(shù)據(jù)轉(zhuǎn)換規(guī)則
這篇文章給大家講解不同類型數(shù)據(jù)間的混合運(yùn)算與類型轉(zhuǎn)換，有自動(dòng)類型轉(zhuǎn)換和強(qiáng)制類型轉(zhuǎn)換，針對(duì)每種轉(zhuǎn)換方法小編給大家介紹的非常詳細(xì)，需要的朋友參考下吧2021-07-07
C++優(yōu)先級(jí)隊(duì)列的使用指南與模擬實(shí)現(xiàn)
優(yōu)先級(jí)隊(duì)列是一種特殊的隊(duì)列,其中每個(gè)元素都有一個(gè)與之關(guān)聯(lián)的優(yōu)先級(jí),優(yōu)先級(jí)較高的元素會(huì)在隊(duì)列中較早地被處理,而優(yōu)先級(jí)較低的元素會(huì)在后續(xù)處理,本文給大家介紹C++優(yōu)先級(jí)隊(duì)列的使用指南與模擬實(shí)現(xiàn),需要的朋友可以參考下2023-09-09
C語言實(shí)現(xiàn)樹的動(dòng)態(tài)查找實(shí)例代碼
這篇文章主要介紹了C語言實(shí)現(xiàn)樹的動(dòng)態(tài)查找實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-06-06
C語言 坐標(biāo)移動(dòng)詳解及實(shí)例代碼
這篇文章主要介紹了C語言 坐標(biāo)移動(dòng)詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-01-01
這篇文章主要介紹了使用c語言獲取直播吧最近一周nba比賽信息的方法,需要的朋友可以參考下2014-04-04
詳細(xì)講解C語言中的數(shù)據(jù)以及位運(yùn)算
這篇文章主要為大家詳細(xì)介紹了C語言中數(shù)據(jù)表示方法以及位運(yùn)算的相關(guān)知識(shí)點(diǎn)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-06-06
IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無限滾動(dòng)
這篇文章主要介紹了IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無限滾動(dòng)的相關(guān)資料,需要的朋友可以參考下2017-07-07
C++中運(yùn)算符重載的規(guī)則語法實(shí)例
今天小編就為大家分享一篇關(guān)于C++中運(yùn)算符重載的規(guī)則語法實(shí)例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
本篇文章介紹了C++類內(nèi)存分布結(jié)構(gòu)，我們來看看編譯器是怎么處理類成員內(nèi)存分布的，特別是在繼承、虛函數(shù)存在的情況下2021-06-06