最小翻转以使C ++中的左侧全为1，右侧全为0
问题陈述
给定一个二进制字符串，我们可以在其中将所有1翻转到左边，将所有0翻转到右边。任务是计算使左侧的所有1和右侧的全部0所需的最小翻转
示例
给定的二进制字符串为0010101。在此字符串中，有3个1位和4个0位。我们必须翻转突出显示的4位，以使所有1都在左侧，而所有0都在右侧，如下所示-
0010101
翻转字符串后将变为-
1110000
算法
从左到右遍历字符串，并计算将所有0转换为1所需的翻转次数。
从右到左遍历字符串，并计算将所有1转换为0所需的翻转次数
遍历位之间的所有位置并找到（0的翻转+1的翻转）的最小值
示例
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Minimum flips: 4