सी++ में ऑड ईवन जंप

मान लीजिए कि हमारे पास एक सरणी A है। कुछ शुरुआती इंडेक्स से, हम छलांग की एक श्रृंखला बना सकते हैं। श्रृंखला में स्थिति (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 हैं जहां से हम अंत तक पहुंच सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट :=1

• n :=A का आकार

• एक सरणी को परिभाषित करें nextGreterEqual का आकार n इसे -1 से भरें

• एक सरणी को परिभाषित करें nextSmaller समान आकार n इसे -1 से भरें

• एक नक्शा सेंट परिभाषित करें

• इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • if :=की-वैल्यू पेयर जिसका मान A[i]

    . से अधिक नहीं है

  • nextGreterEqual[i] :=यदि (यह) अंतिम तत्व नहीं है, तो इसका मान, अन्यथा -1

  • यदि यह st के अंतिम तत्व के बराबर नहीं है और इसमें से पहला A[i] के समान है, तो -

    • (इसे 1 से बढ़ाएं)

  • nextSmallerEqual[i] :=अगर (यह) पहला तत्व नहीं है, तो इसके पिछले का मान, अन्यथा -1

  • सेंट [ए [i]]:=मैं

• आकार n x 2 के एक 2D सरणी v को परिभाषित करें और इसे असत्य से भरें

• v[n - 1, 0] =v[n - 1, 1] =सच

• इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • अगर nextGreterEqual[i] -1 के बराबर नहीं है, तो -

    • v[i, 1] :=v[nextGreterEqual[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