Số lần hoán đổi tối thiểu cần thiết để tạo một chuỗi nhị phân xen kẽ trong C ++

Tuyên bố vấn đề

Cho một chuỗi nhị phân có độ dài chẵn và số 0 và 1 bằng nhau. Số lần hoán đổi tối thiểu để làm cho chuỗi xen kẽ là bao nhiêu? Một chuỗi nhị phân xen kẽ nếu không có hai phần tử liên tiếp nào bằng nhau

Ví dụ

Nếu str =11110000 thì cần 2 lần hoán đổi.

Thuật toán

• Đếm số lượng các số 0 ở vị trí lẻ và vị trí chẵn của chuỗi. Đặt số lượng của chúng tương ứng là lẻZeroCnt và chẵnZeroCnt
• Đếm số đơn vị ở vị trí lẻ và vị trí chẵn của chuỗi. Đặt số lượng của chúng tương ứng là lẻOneCnt và chẵnOneCnt
• Chúng tôi sẽ luôn hoán đổi 1 với 0. Vì vậy, chúng tôi chỉ cần kiểm tra xem chuỗi xen kẽ của chúng tôi bắt đầu bằng 0 thì số lần hoán đổi là tối thiểu (chẵnZeroCnt, lẻOneCnt) và nếu chuỗi xen kẽ của chúng tôi bắt đầu bằng 1 thì số lần hoán đổi là tối thiểu (chẵnOneCnt, lẻZeroCnt). Câu trả lời là tối thiểu trong hai điều này

Ví dụ

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

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Đầu ra

Minimum swaps = 2