在C ++中生成二进制字符串所需的最少交换

问题陈述

给定一个具有偶数长度且等于0和1的二进制数的二进制字符串。使字符串交替出现的最小交换次数是多少？如果没有两个连续的元素相等，则二进制字符串是交替的

示例

如果str = 11110000，则需要进行2次交换。

算法

• 计算字符串的奇数位和偶数位的零数。假设它们的计数分别为oddZeroCnt和evenZeroCnt

• 计算字符串奇数和偶数位置的位数。假设它们的计数分别为oddOneCnt和evenOneCnt

• 我们将始终将1与0交换。因此，我们只需要检查交替字符串是否以0开头，则交换次数为min(evenZeroCnt,oddOneCnt)，如果我们交替字符串以1开头，则交换次数为min（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