ধরুন আমাদের একটি nums অ্যারে আছে যা আরোহী ক্রমে সাজানো। আমাদের true ফেরত দিতে হবে যদি এবং কেবল যদি আমরা এটি ১ বা তার বেশি সাবসিকোয়েন্সে ভাগ করতে পারি যাতে প্রতিটি সাবসিকোয়েন্স ক্রমাগত পূর্ণসংখ্যাগুলি নিয়ে গঠিত হয় এবং যার দৈর্ঘ্য কমপক্ষে ৩। তাই যদি ইনপুট হয় [1,2,3,3,4,4,5,5], তবে আউটপুট হবে True, কারণ আমাদের দুটি ক্রমাগত সিকোয়েন্স রয়েছে। এগুলি হল [1,2,3,4,5] এবং [3,4,5]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি ম্যাপ m তৈরি করুন এবং nums-এর ফ্রিকোয়েন্সি m-এ সংরক্ষণ করুন, nums-এর আকার n সংরক্ষণ করুন
- cnt := n
- i = 0 থেকে n – ১ পর্যন্ত
- x := nums[i]
- যদি m[x] এবং m[x + 1] এবং m[x + 2] হয়
- m[x], m[x + 1] এবং m[x + 2] ১ হ্রাস করুন, x ৩ বৃদ্ধি করুন এবং count ৩ হ্রাস করুন
- যখন m[x] > 0 এবং m[x] > m[x – ১]
- cnt ১ হ্রাস করুন, m[x] ১ হ্রাস করুন এবং x ১ বৃদ্ধি করুন
- যদি cnt ০ হয় তবে true ফেরত দিন, অন্যথায় false
- বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isPossible(vector<int>& nums) { unordered_map <int, int> m; int n = nums.size(); for(int i = 0; i < n; i++){ m[nums[i]]++; } int cnt = n; for(int i = 0; i < n; i++){ int x = nums[i]; if(m[x] && m[x + 1] && m[x + 2]){ m[x]--; m[x + 1]--; m[x + 2]--; x += 3; cnt -= 3; while(m[x] > 0 && m[x] > m[x - 1]){ cnt--; m[x]--; x++; } } } return cnt == 0; } }; main(){ vector<int> v = {1,2,3,3,4,4,5,5}; Solution ob; cout << (ob.isPossible(v)); }ইনপুট
[1,2,3,3,4,4,5,5]
আউটপুট
1
