nums라는 숫자 목록이 있고 또 다른 숫자 k가 있다고 가정하고 각 목록에 k 값이 포함되어 있고 값이 연속적으로 증가하는 목록으로 분할할 수 있는지 확인해야 합니다.
따라서 입력이 nums =[4, 3, 2, 4, 5, 6], k =3과 같으면 목록을 [2, 3, 4] 및 [ 4, 5, 6]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 지도 정의
-
각 키에 대해 m
-
m[it]을 1 증가
-
-
확인 :=사실
-
동안 (m의 크기는 0이 아니고 ok는 참임) −
-
확인 :=거짓
-
각 키-값 쌍에 대해 m
-
(it.key - 1)이 m에 없으면 -
-
플래그 :=참
-
for initialize i :=it.key, i <=it.key + k - 1일 때 업데이트(i를 1만큼 증가), do -
-
i가 m에 없으면 -
-
플래그 :=거짓
-
-
-
플래그가 참이면 -
-
initialize i :=it.key 의 경우 i <=it.key + k - 1일 때 업데이트(i만큼 1 증가), −
-
(m[i]를 1만큼 감소)
-
m[i]가 0과 같으면 -
-
m에서 i 삭제
-
-
-
확인 :=사실
-
루프에서 나오세요
-
-
-
-
-
m이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int> nums, int k) {
map <int, int> m;
for(auto& it : nums){
m[it]++;
}
bool ok = true;
while(m.size() && ok){
ok = false;
for(auto& it : m){
if(!m.count(it.first - 1)){
bool flag = true;
for(int i = it.first; i <= it.first + k - 1;i++){
if(!m.count(i))
flag = false;
}
if(flag){
for(int i = it.first; i <= it.first + k - 1;i++){
m[i]--;
if(m[i] == 0)
m.erase(i);
}
ok = true;
break;
}
}
}
}
return m.empty();
}
};
main(){
vector<int> v = {4, 3, 2, 4, 5, 6};
Solution ob;
cout << ob.solve(v, 3);
}
입력
{4, 3, 2, 4, 5, 6} 출력
1