สตริงไบนารีพิเศษใน C++

สมมติว่าเรามีสตริงไบนารีเชิงพื้นที่ สตริงนี้มีคุณสมบัติดังต่อไปนี้ −

• มีเลข 0 และ 1 เท่ากัน

• ทุกคำนำหน้าในสตริงไบนารีมีอย่างน้อย 1 วินาทีเท่ากับ 0

ตอนนี้ สมมติว่าเรามีสตริงพิเศษ S อันที่จริงแล้ว การย้ายคือการเลือกสตริงย่อยพิเศษของ S ที่ต่อเนื่องกันสองรายการและสลับกัน

เราต้องหาสตริงผลลัพธ์ที่ใหญ่ที่สุดเท่าที่จะเป็นไปได้ในตอนท้ายของการเคลื่อนไหวจำนวนเท่าใดก็ได้

ดังนั้น หากอินพุตเท่ากับ 11011000 เอาต์พุตจะเป็น 11100100 นั่นเป็นเพราะ:สตริงย่อย "10" และ "1100" ถูกสลับ นี่คือสตริงที่ใหญ่ที่สุดที่เป็นไปได้หลังจากการเคลื่อนไหวไม่กี่ครั้ง

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

• กำหนดฟังก์ชัน makeLargestSpecial() ซึ่งจะใช้เวลา s

• ret :=สตริงว่าง

• กำหนดอาร์เรย์ v ของสตริง

• ผม :=0

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

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

    • (เพิ่มขึ้นอีก 1)

  • มิฉะนั้น

    • (ลดลง 1)

  • ถ้า cnt เหมือนกับ 0 แล้ว −

    • แทรก "1" + makeLargestSpecial(สตริงย่อยของ s จากดัชนี i + 1 ถึง j - i - 1) ที่ส่วนท้ายของ v

    • ผม :=j + 1

• เรียงลำดับอาร์เรย์ vr

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

  • ret :=ret + v[i]

• รีเทิร์น

• จากการเรียกเมธอดหลัก makeLargestSpecial() ด้วยสตริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string makeLargestSpecial(string s) {
      string ret = "";
      vector<string> v;
      int i = 0;
      for (int j = 0, cnt = 0; j < s.size(); j++) {
         if (s[j] == '1') {
            cnt++;
         }
         else
         cnt--;
         if (cnt == 0) {
            v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
            j - i - 1)) + "0");
            i = j + 1;
         }
      }
      sort(v.rbegin(), v.rend());
      for (int i = 0; i < v.size(); i++)
      ret += v[i];
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.makeLargestSpecial("11011000"));
}

อินพุต

11011000

ผลลัพธ์

11100100