ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে এবং আরেকটি সংখ্যা k, আমাদের পরীক্ষা করতে হবে যে তালিকাটি এমন তালিকায় বিভক্ত করা যেতে পারে যেখানে প্রতিটি তালিকায় k মান রয়েছে এবং মানগুলি ধারাবাহিকভাবে বৃদ্ধি পাচ্ছে।
সুতরাং, যদি ইনপুট nums =[4, 3, 2, 4, 5, 6], k =3 এর মত হয়, তাহলে আউটপুট হবে True, কারণ আমরা তালিকাটিকে [2, 3, 4] এবং [2, 3, 4] এ বিভক্ত করতে পারি। 4, 5, 6]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র সংজ্ঞায়িত করুন
-
প্রতিটি কীর জন্য এটি m
এ-
m[এটি] 1 দ্বারা বৃদ্ধি করুন
-
-
ঠিক আছে :=সত্য
-
যখন (m-এর আকার 0 নয় এবং ঠিক আছে সত্য), −
করুন-
ঠিক আছে :=মিথ্যা
-
প্রতিটি কী-মানের জন্য এটি m
-এ যুক্ত করুন-
যদি (it.key - 1) m এ না থাকে, তাহলে −
-
পতাকা :=সত্য
-
আরম্ভ করার জন্য i :=it.key, যখন i <=it.key + k - 1, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
যদি আমি m এ উপস্থিত না থাকি, তাহলে −
-
পতাকা :=মিথ্যা
-
-
-
যদি পতাকা সত্য হয়, তাহলে -
-
আরম্ভ করার জন্য i :=it.key , যখন i <=it.key + k - 1, আপডেট (iby 1 বাড়ান), −
-
(1 দ্বারা m[i] হ্রাস করুন)
-
যদি m[i] 0 এর সমান হয়, তাহলে −
-
m
থেকে i মুছুন
-
-
-
ঠিক আছে :=সত্য
-
লুপ থেকে বেরিয়ে আসুন
-
-
-
-
-
m খালি হলে true ফেরত দিন, অন্যথায় মিথ্যা।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
