C++で順列を見つける

文字「D」と「I」で構成される秘密の署名があるとします。 「D」は2つの数値間の減少関係を示し、「I」は2つの数値間の増加関係を示します。そして、秘密の署名は、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]

これを解決するには、次の手順に従います-

• 1つのスタックstを定義する

• cnt：=2

• 配列retを定義する

• 初期化i：=1の場合、i <=sのサイズの場合、更新（iを1増やします）、実行-

  • s[i-1]が'D'と同じ場合、-

    • iをstに挿入

  • それ以外の場合

    • retの最後にiを挿入します

    • （stが空ではない）間、-

      • retの最後にstの一番上の要素を挿入します

      • stから要素を削除

• sのサイズをstに挿入

• （stが空ではない）間、-

  • retの最後にstの一番上の要素を挿入します

  • stから要素を削除

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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, ]