在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