ধরুন আমাদের একটি অ্যারে এ আছে। কিছু প্রারম্ভিক সূচক থেকে, আমরা একের পর এক লাফ দিতে পারি। সিরিজে অবস্থান (1, 3, 5, ...) জাম্পকে বিজোড় সংখ্যাযুক্ত জাম্প বলা হয় এবং সিরিজে অবস্থান (2, 4, 6, ...) জাম্পকে জোড় সংখ্যাযুক্ত জাম্প বলা হয়।
এখন আমরা সূচক i থেকে সূচী j এ (i
বিজোড় সংখ্যাযুক্ত জাম্পের সময়, আমরা সূচক j এ যেতে পারি যাতে A[i] <=A[j] এবং A[j] হল সবচেয়ে ছোট সম্ভাব্য মান। যখন এই ধরনের একাধিক সূচী j থাকে, তখন আমরা শুধুমাত্র ক্ষুদ্রতম এই ধরনের সূচী j-এ যেতে পারি।
জোড় সংখ্যাযুক্ত জাম্পের সময়, আমরা সূচক j এ যেতে পারি যাতে A[i]>=A[j] এবং A[j] হল সবচেয়ে বড় সম্ভাব্য মান। যখন এই ধরনের একাধিক সূচী j থাকে, তখন আমরা শুধুমাত্র ক্ষুদ্রতম এই ধরনের সূচী j-এ যেতে পারি।
এটি এমন একটি ক্ষেত্রে হতে পারে যে কিছু সূচক i এর জন্য, কোন আইনি লাফ নেই৷
এখন একটি প্রারম্ভিক সূচককে ভাল বলা হয় যখন, সেই সূচক থেকে শুরু করে, আমরা কয়েকবার লাফিয়ে অ্যারের শেষ পর্যন্ত পৌঁছাতে পারি।
আমাদের ভাল শুরুর সূচকের সংখ্যা খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি [10,13,12,14,15] এর মত হয়, তাহলে আউটপুট হবে 2, কারণ দুটি স্থান সূচক 3 এবং 4 আছে যেখান থেকে আমরা শেষ পর্যন্ত পৌঁছাতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
ret :=1
n :=A
একটি অ্যারে সংজ্ঞায়িত করুন NextGreaterEqual এর আকার n এটি -1 দিয়ে পূরণ করুন
একটি অ্যারে সংজ্ঞায়িত করুন NextSmallerEqual এর আকার n এটি -1 দিয়ে পূরণ করুন
একটি মানচিত্র সংজ্ঞায়িত করুন st
আরম্ভ করার জন্য i :=n - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), করুন −
if :=কী-মান জোড়া যার মান A[i>
nextGreaterEqual[i] :=যদি (এটি) শেষ উপাদান না হয়, তাহলে এর মান, অন্যথায় -1
যদি এটি st এর শেষ উপাদানের সমান না হয় এবং এর প্রথমটি A[i] এর সমান হয়, তাহলে −
(এটি 1 দ্বারা বাড়ান)
nextSmallerEqual[i] :=যদি (এটি) প্রথম উপাদান না হয়, তাহলে এর আগেরটির মান, অন্যথায় -1
st[A[i]] :=i
n x 2 আকারের একটি 2D অ্যারে v সংজ্ঞায়িত করুন এবং এটি মিথ্যা দিয়ে পূরণ করুন
v[n - 1, 0] =v[n - 1, 1] =সত্য
আরম্ভ করার জন্য i :=n - 2, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
যদি nextGreaterEqual[i] -1 এর সমান না হয়, তাহলে −
v[i, 1] :=v[nextGreaterEqual[i], 0]
যদি nextSmallerEqual[i] -1 এর সমান না হয়, তাহলে −
v[i, 0] :=v[nextSmallerEqual[i], 1]
যদি v[i, 1] অ-শূন্য হয়, তাহলে −
(রেট 1 দ্বারা বৃদ্ধি করুন)
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int oddEvenJumps(vector<int>& A){
int ret = 1;
int n = A.size();
vector<int> nextGreaterEqual(n, -1);
vector<int> nextSmallerEqual(n, -1);
map<int, int> st;
for (int i = n - 1; i >= 0; i--) {
map<int, int>::iterator it = st.lower_bound(A[i]);
nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
if (it != st.end() && it->first == A[i])
it++;
nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
: -1;
st[A[i]] = i;
}
vector<vector<bool> > v(n, vector<bool>(2, false));
v[n - 1][0] = v[n - 1][1] = true;
for (int i = n - 2; i >= 0; i--) {
if (nextGreaterEqual[i] != -1) {
v[i][1] = v[nextGreaterEqual[i]][0];
}
if (nextSmallerEqual[i] != -1) {
v[i][0] = v[nextSmallerEqual[i]][1];
}
if (v[i][1])
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {10,13,12,14,15};
cout << (ob.oddEvenJumps(v));
} ইনপুট
{10,13,12,14,15} আউটপুট
2
