सी++ में क्रमपरिवर्तन खोजें

मान लीजिए कि हमारे पास एक गुप्त हस्ताक्षर है जिसमें 'D' और 'I' वर्ण शामिल हैं। 'D' दो संख्याओं के बीच घटते संबंध को दर्शाता है, 'I' दो संख्याओं के बीच बढ़ते संबंध को दर्शाता है। और गुप्त हस्ताक्षर का निर्माण एक विशेष पूर्णांक सरणी द्वारा किया गया था, जिसमें विशिष्ट रूप से 1 से n तक की सभी भिन्न संख्याएँ होती हैं।

उदाहरण के लिए, गुप्त हस्ताक्षर "DI" का निर्माण [2,1,3] या [3,1,2] जैसे सरणी से किया जा सकता है, लेकिन [3,2,4] या [2, 1,3,4], जो दोनों अवैध निर्माण विशेष स्ट्रिंग हैं जो "DI" गुप्त हस्ताक्षर का प्रतिनिधित्व नहीं कर सकते हैं।

अब हमें [1, 2, ... n] का शाब्दिक रूप से सबसे छोटा क्रमपरिवर्तन खोजना होगा जो इनपुट में दिए गए गुप्त हस्ताक्षर को संदर्भित कर सके।

इसलिए, यदि इनपुट "DI" जैसा है, तो आउटपुट [2,1,3] होगा, जैसा कि हम जानते हैं [3,1,2] गुप्त हस्ताक्षर "DI" भी बना सकते हैं, लेकिन चूंकि हम खोजना चाहते हैं सबसे छोटे लेक्सिकोग्राफिक क्रमपरिवर्तन के साथ, हमें [2,1,3]

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

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

• सीएनटी:=2

• एक सरणी रिट परिभाषित करें

• इनिशियलाइज़ i :=1 के लिए, जब i <=s का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • यदि s[i - 1] 'D' के समान है, तो -

    • मुझे सेंट में डालें

  • अन्यथा

    • रिट के अंत में i डालें

    • जबकि (सेंट खाली नहीं है), करें -

      • रिट के अंत में सेंट का शीर्ष तत्व डालें

      • सेंट से तत्व हटाएं

• s का आकार st में डालें

• जबकि (सेंट खाली नहीं है), करें -

  • रिट के अंत में सेंट का शीर्ष तत्व डालें

  • सेंट से तत्व हटाएं

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int< findPermutation(string s) {
      stack <int< st;
      int cnt = 2;
      vector <int< ret;
      for(int i = 1; i <= s.size(); i++){
         if(s[i - 1] == 'D'){
            st.push(i);
         }
         else{
            ret.push_back(i);
            while(!st.empty()){
               ret.push_back(st.top());
               st.pop();
            }
         }
      }
      st.push(s.size() + 1);
      while(!st.empty()){
         ret.push_back(st.top());
         st.pop();
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.findPermutation("DIID"));
}

इनपुट

"DIID"

आउटपुट

[2, 1, 3, 5, 4, ]