数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
更新于：2019年11月22日
311 次浏览
广告