最小化后缀翻转使二进制字符串非减
在本题中，我们将通过翻转二进制字符串的字符来计算将字符串转换为非减序所需的最少操作次数。
如果第 p 个索引处的字符为 0，且与前一个索引处的字符不匹配，我们可以翻转从第 \mathrm{p^{th}} 个索引开始的子字符串的所有字符，并计算最少翻转次数。
问题描述 - 给定一个二进制字符串 alpha。我们需要计算将二进制字符串转换为升序所需的最少翻转次数。在一次翻转中，我们可以选择任意索引 p，并从第 p 个索引开始翻转子字符串。
示例
输入
alpha = "11000110"
输出
3
说明
在第一步中，我们可以从第二个索引开始翻转子字符串。因此，结果字符串为 11111001。
在第二步中，选择从第五个索引开始的字符串，然后翻转它。因此，字符串变为 11111110。
翻转最后一个字符，使字符串等于 1111111。
因此，我们需要执行总共 3 次翻转才能将字符串转换为升序。
输入
alpha = "0011"
输出
0
说明 - 该字符串已按升序排列。
输入
alpha = "1100";
输出
1
说明 - 我们可以从第二个索引开始翻转子字符串，得到 1111 字符串。
方法 1
在此方法中，我们将遍历字符串，当发现当前字符为"0"且与前一个字符不匹配时，我们将翻转当前索引右侧的所有字符。
算法
步骤 1 - 将"cnt"初始化为 0，以存储所需的最小值翻转。
步骤 2 - 如果索引 p 和 p - 1 处的字符不同，且索引 'p' 处的字符为 '0'，则执行以下步骤。
步骤 3 - 从第 p 个索引开始遍历字符串。
步骤 4 - 如果第 q 个索引处的字符为 '0'，则将其替换为 '1'。否则，将其替换为 '0'。
步骤 5 - 将 cnt 值加 1。
步骤 6 - 最后，返回 'cnt' 值。
示例
#include <bits/stdc++.h>
using namespace std;
int GetOperations(string alpha) {
//用于存储操作计数
int cnt = 0;
for (int p = 1; p < alpha.length(); p++) {
// 对于不同的相邻字符
if (alpha[p] != alpha[p - 1]) {
if (alpha[p] == '0') {
// 翻转从索引 p 开始的子字符串的所有位
for (int q = p; q < alpha.length(); q++) {
if (alpha[q] == '0') {
alpha[q] = '1';
} else {
alpha[q] = '0';
}
}
cnt++;
}
}
}
// return answer
return cnt;
}
int main() {
string alpha = "11000110";
cout << "将字符串转换为递增顺序所需的最少操作是 " << GetOperations(alpha);
return 0;
}
输出
将字符串转换为递增顺序所需的最少操作是 3
时间复杂度 - O(N*N)，用于遍历和翻转字符串字符。
空间复杂度 - O(1)，因为我们不使用任何额外空间。
方法 2
在此方法中，我们将使用布尔变量来跟踪字符串字符是否被翻转，而不是翻转它们。
算法
步骤 1 - 将"cnt"和"isFlipped"初始化为"0"。
步骤 2 - 开始遍历字符串。如果索引 p 和 p - 1 处的字符不匹配，请按照以下步骤操作。
步骤 3 - 如果 isFlipped 等于 0，且 alpha[p] 也为 '0'，则将 isFlipped 更改为 1，并将 'cnt' 加 1。
步骤 4 - 如果 isFlipped 为 1，则将 'cnt' 加 1。
步骤 5 - 从函数返回 'cnt'。
示例
#include <bits/stdc++.h>
using namespace std;
int GetOperations(string alpha) {
// 用于存储操作计数
int cnt = 0;
// 用于跟踪翻转
bool isFlipped = 0;
for (int p = 1; p < alpha.length(); p++) {
// 对于不同的相邻字符
if (alpha[p] != alpha[p - 1]) {
// alpha[p] 为 '0'，不等于 alpha[p-1]。因此，字符串按降序排列。
if (isFlipped == 0 && alpha[p] == '0') {
isFlipped = 1;
cnt++;
}
// 当字符串按升序排列，但字符串被翻转时
else if (isFlipped == 1) {
cnt++;
}
}
}
// return answer
return cnt;
}
int main() {
string alpha = "11000";
cout << "将字符串转换为递增顺序所需的最少操作是 " << GetOperations(alpha);
return 0;
}
输出
将字符串转换为递增顺序所需的最少操作是 1
时间复杂度 - O(N) 遍历字符串。
空间复杂度 - O(1)
在第二种方法中，我们使用布尔变量来跟踪虚拟翻转的字符。因此，当我们发现字符串不是按升序排列时，这种方法可以降低翻转所有正确字符的成本。
