|
题目链接：https://leetcode-cn.com/problems/delete-and-earn/
题意：
给你一个整数数组?nums?，你可以对它进行一些操作。
每次操作中，选择任意一个?nums[i]?，删除它并获得?nums[i]?的点数。之后，你必须删除 所有 等于?nums[i] - 1 和 nums[i] + 1?的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
?方法：动态规划+哈希表
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
//此题类似于打家劫舍
map<int,int> mp;//哈希表，存储映射关系<数字，出现的次数>
for(int num:nums)//将nums中的数组存储到哈希表中
{
mp[num]++;//更新哈希表
}
int size = mp.size();//存储哈希表的长度
if(size==0) return 0;//如果哈希表中没有项
else if(size==1) return mp.begin()->first*mp.begin()->second;//如果哈希表中恰好只有一项，返回对应的key*value
vector<int> dp(10002,0);//dp数组，dp[i]表示前i个数里能获取到的最大点数
int maxV = 0;//存储最大点数
dp[0] = 0;//初始化dp数组的第一个值
int pre = 0,ppre=0;//前一个哈希项的key，前前个哈希项的key
for(auto iter=mp.begin();iter!=mp.end();iter++)
{
if(pre==0)//如果前一个元素是0，说明目前是哈希项中的第一项
{
dp[iter->first] = iter->first*iter->second;//更新dp数组
maxV = max(dp[iter->first],maxV);//更新最大点数
pre = iter->first;//更新前一个元素的值，相对于下一个元素，目前元素就是前一个元素
}else//如果不是首元素
{
if(iter->first-pre==1)//与前一项相差刚好为1，目前项不能选，需要权衡比较，取最大的dp值
{
dp[iter->first] = max(dp[pre],dp[ppre]+iter->first*iter->second);
}else//前一项和目前的差值大于1，那只要把当前的最大点数和当前项的所有点数相加即可
{
dp[iter->first] = maxV+iter->first*iter->second;
}
ppre = pre;//更新前前项
pre = iter->first;//更新前一项
maxV = max(dp[iter->first],maxV);//更新最大点数
}
}
return maxV;
}
};
?优化dp数组后：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
//此题类似于打家劫舍
map<int,int> mp;//哈希表，存储映射关系<数字，出现的次数>
for(int num:nums)//将nums中的数组存储到哈希表中
{
mp[num]++;//更新哈希表
}
int size = mp.size();//存储哈希表的长度
if(size==0) return 0;//如果哈希表中没有项
else if(size==1) return mp.begin()->first*mp.begin()->second;//如果哈希表中恰好只有一项，返回对应的key*value
vector<int> dp(size+1,0);//dp数组，dp[i]表示前i项里能获取到的最大点数
int maxV = 0;//存储最大点数
dp[0] = 0;//初始化dp数组的第一个值
int index = 1;//记录dp数组中项的序号
int pre = 0;//前一个哈希项的key
for(auto iter=mp.begin();iter!=mp.end();iter++)
{
if(pre==0)//如果前一个元素是0，说明目前是哈希项中的第一项
{
dp[index] = iter->first*iter->second;//更新dp数组
maxV = max(dp[index],maxV);//更新最大点数
index++;//对应项的序号自加
pre = iter->first;//更新前一个元素的值，相对于下一个元素，目前元素就是前一个元素
}else//如果不是首元素
{
if(iter->first-pre==1)//与前一项相差刚好为1，目前项不能选，需要权衡比较，取最大的dp值
{
dp[index] = max(dp[index-1],dp[index-2]+iter->first*iter->second);
}else//前一项和目前的差值大于1，那只要把当前的最大点数和当前项的所有点数相加即可
{
dp[index] = maxV+iter->first*iter->second;
}
pre = iter->first;//更新前一项
maxV = max(dp[index],maxV);//更新最大点数
index++;//更新序号
}
}
return maxV;
}
};
?
|