在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