Tìm hoán vị trong C ++

Giả sử chúng ta có một chữ ký bí mật bao gồm ký tự 'D' và 'I'. 'D' biểu thị mối quan hệ giảm dần giữa hai số, 'I' biểu thị mối quan hệ tăng dần giữa hai số. Và chữ ký bí mật được tạo bởi một mảng số nguyên đặc biệt, chứa duy nhất tất cả các số khác nhau từ 1 đến n.

Ví dụ:chữ ký bí mật "DI" có thể được xây dựng từ một mảng như [2,1,3] hoặc [3,1,2], nhưng không được xây dựng bằng cách sử dụng mảng như [3,2,4] hoặc [2, 1,3,4], đều là chuỗi đặc biệt xây dựng bất hợp pháp không thể đại diện cho chữ ký bí mật "DI".

Bây giờ chúng ta phải tìm hoán vị nhỏ nhất về mặt từ vựng của [1, 2, ... n] có thể tham chiếu đến chữ ký bí mật đã cho trong đầu vào.

Vì vậy, nếu đầu vào là "DI", thì đầu ra sẽ là [2,1,3], Như chúng ta đã biết [3,1,2] cũng có thể xây dựng chữ ký bí mật "DI", nhưng vì chúng ta muốn tìm cái có hoán vị từ vựng nhỏ nhất, chúng ta cần xuất ra [2,1,3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một ngăn xếp

• cnt:=2

• Xác định ret mảng

• để khởi tạo i:=1, khi i <=size of s, hãy cập nhật (tăng i lên 1), thực hiện -

  • nếu s [i - 1] giống với 'D', thì -

    • chèn tôi vào st

  • Nếu không

    • chèn tôi vào cuối ret

    • while (not st là trống), do -

      • chèn phần tử trên cùng của st vào cuối ret

      • xóa phần tử khỏi st

• chèn kích thước của s vào st

• while (not st là trống), do -

  • chèn phần tử trên cùng của st vào cuối ret

  • xóa phần tử khỏi st

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"DIID"

Đầu ra

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