資料結構
網路
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 次檢視
廣告