数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的删除并获利
假设我们有一个包含整数的数组 nums，我们可以在数组上执行一些操作。在每次操作中，我们选择任何 nums[i] 并将其删除以赚取 nums[i] 数量的点数。我们必须删除等于 nums[i] - 1 或 nums[i] + 1 的所有元素。最初分数为 0。我们必须找到通过应用此类操作可以获得的最大点数。因此，如果输入类似于 [3,4,2]，则输出将为 6。这是因为，如果我们删除 4，我们将获得 4 分，因此 3 也将被删除。然后删除 2 以获得 2 分。共获得 6 分。
为了解决这个问题，我们将遵循以下步骤：
n := nums 数组的大小，定义映射 m，ret := 0，将 nums 中元素的频率存储到 m 中
cnt := 0
对于 m 的每个键值对 it
x := it 的键
temp := x * it 的值
it1 := 指向 it 的前一个键值对，it2 := 指向 it1 的前一个键值对
如果 cnt >= 1 且 x – it1 的键 > 1，则 temp := m[it1 的键]
否则，当 cnt >= 2 时，则 temp := temp + m[it2 的键]
a = m[it1 的键] 如果 cnt >= 1，否则为 0
m[it 的键] := temp 和 a 的最大值
ret := ret 和 temp 的最大值
将 cnt 增加 1
返回 ret
示例（C++）
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
map <int, int> m;
int ret = 0;
for(int i = 0; i < nums.size(); i++){
m[nums[i]]++;
}
int cnt = 0;
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
int x = it->first;
int temp = x * it->second;
map <int, int> :: iterator it1 = prev(it);
map <int, int> :: iterator it2 = prev(it1);
if(cnt >= 1 && x - it1->first > 1){
temp += m[it1->first];
}
else if(cnt >= 2){
temp += m[it2->first];
}
m[it->first] = max(temp, cnt >= 1 ? m[it1->first] : 0);
ret = max(ret, temp);
it++;
cnt++;
}
return ret;
}
};
main(){
vector<int> v = {3,4,2};
Solution ob;
cout << (ob.deleteAndEarn(v));
}输入
[3,4,2]
输出
6
更新于: 2020年5月2日
194 次查看
广告