C++에서 삭제 및 획득

<시간/>

정수 배열이 있다고 가정하고 배열에 대해 몇 가지 작업을 수행할 수 있습니다. 여기 각 작업에서 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
- x :=키
- temp :=x * 값
- it1 :=그것의 이전을 가리키고 it2 :=it1의 이전을 가리킴
- cnt>=1이고 x – it1의 키> 1이면 temp :=m[it1의 키]
- 그렇지 않으면 cnt>=2일 때 temp :=temp + m[key of it2]
- a =m[it1의 키] cnt>=1이면 0
- m[key of it] :=최대 온도 및 a
- ret :=ret 및 temp의 최대값
- cnt 1 증가
리턴 렛

예시(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]