在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
热门推荐
1 狗狗技能训练
5 如何训练狗狗笑
6 狗狗训练排便
9 狗狗响片训练
10 如何训练狗狗不捡食
11 狗狗尿训练
12 怎么训练狗狗找东西
13 狗狗训练站立
14 狗狗训练飞盘
15 鞍山狗狗训练
16 怎样训练泰迪狗狗谢谢
17 狗狗外出训练
18 怎么训练金毛狗狗大小便