ค้นหาการเรียงสับเปลี่ยนใน C++

สมมติว่าเรามีลายเซ็นลับที่ประกอบด้วยอักขระ '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]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งสแต็ก st

• cnt :=2

• กำหนดอาร์เรย์ ret

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=ขนาดของ s อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า s[i - 1] เหมือนกับ 'D' แล้ว −

    • ใส่ i ลงใน st

  • มิฉะนั้น

    • ใส่ i ต่อท้าย ret

    • ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ทำ -

      • แทรกองค์ประกอบด้านบนของ st ที่ส่วนท้ายของ ret

      • ลบองค์ประกอบออกจาก st

• แทรกขนาดของ s ลงใน st

• ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ทำ -

  • แทรกองค์ประกอบด้านบนของ st ที่ส่วนท้ายของ ret

  • ลบองค์ประกอบออกจาก 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, ]