在C ++中将字符串翻转为单调递增
假设给出了一个字符串“0”和“1”。如果该字符串包含一定数量的“0”（可能为0），然后是一定数量的“1”（也可能为0），则它将是单调递增的。我们的字符串S为'0'和'1'，我们可以将任何'0'翻转为'1'或将'1'翻转为'0'。找到使S单调递增的最小翻转次数。因此，如果输入类似“010110”，则输出将为2。通过翻转，我们可以获得“011111”或“000111”。
为了解决这个问题，我们将遵循以下步骤-
n：=S的大小，设置flipCount：=0，oneCount：=0
对于i，范围为0至n–1
如果oneCount=0，则跳至下一个迭代
将flipCount增加1
如果S[i]为0，则
否则将1增加1
如果oneCount<flipCount，则设置flipCount：=oneCount
返回flipCount
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFlipsMonoIncr(string S) {
int n = S.size();
int flipCount = 0;
int oneCount = 0;
for(int i = 0; i < n; i++){
if(S[i] == '0'){
if(oneCount == 0) continue;
flipCount++;
} else oneCount++;
if(oneCount < flipCount) flipCount = oneCount;
}
return flipCount;
}
};
main(){
Solution ob;
cout << (ob.minFlipsMonoIncr("010110"));
}输入值
"010110"
输出结果
2