文字列を単調に反転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

  を設定

• 0からn–1の範囲のiの場合

  • S [i]が0の場合、

    • oneCount =0の場合、次の反復にスキップします

    • フリップカウントを1増やします

  • それ以外の場合は、oneCountを1増やします

  • 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