การแลกเปลี่ยนขั้นต่ำที่จำเป็นในการสร้างสตริงไบนารีสลับใน C ++

คำชี้แจงปัญหา

กำหนดสตริงไบนารีที่มีความยาวเท่ากันและมีจำนวนเท่ากับ 0 และ 1 จำนวนสวอปขั้นต่ำในการทำให้สตริงสลับกันคือเท่าไร? สตริงไบนารีจะสลับกันหากไม่มีองค์ประกอบที่ต่อเนื่องกันสององค์ประกอบเท่ากัน

ตัวอย่าง

หาก str =11110000 จำเป็นต้องมีการแลกเปลี่ยน 2 ครั้ง

อัลกอริทึม

• นับจำนวนศูนย์ที่ตำแหน่งคี่และตำแหน่งคู่ของสตริง ให้จำนวนของพวกเขาเป็นเลขคี่ZeroCnt และ evenZeroCnt ตามลำดับ
• นับจำนวนที่ตำแหน่งคี่และตำแหน่งคู่ของสตริง ให้การนับของพวกเขาเป็นเลขคี่OneCnt และแม้แต่OneCnt ตามลำดับ
• เราจะสลับ 1 กับ 0 เสมอ ดังนั้นเราแค่ตรวจสอบว่าสตริงการสลับของเราเริ่มต้นด้วย 0 หรือไม่ จากนั้นจำนวนการสลับคือขั้นต่ำ (evenZeroCnt, oddOneCnt) และหากสตริงการสลับของเราเริ่มต้นด้วย 1 แสดงว่าจำนวนการสลับคือ ขั้นต่ำ (evenOneCnt, oddZeroCnt) คำตอบคือขั้นต่ำของทั้งสอง

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
   int minSwaps = 0;
   int oddZeroCnt = 0;
   int evenZeroCnt = 0;
   int oddOneCnt = 1;
   int evenOneCnt = 1;
   int n = str.length();
   for (int i = 0; i < n; ++i) {
      if (i % 2 == 0) {
         if (str[i] == '1') {
            ++evenOneCnt;
         } else {
            ++evenZeroCnt;
         }
      } else {
         if (str[i] == '1') {
            ++oddOneCnt;
         } else {
            ++oddZeroCnt;
         }
      }
   }
   int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
   int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
   return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
   string str = "11110000";
   cout << "Minimum swaps = " << getMinSwaps(str) << endl;
   return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -

ผลลัพธ์

Minimum swaps = 2