与えられたバイナリ文字列から最小の正しい文字列を見つけるためのC++コード

nビットのバイナリ文字列Sがあるとします。冗長な先行ゼロはありません。 Sで2つの異なる操作を実行できます-

• 隣接するビットの任意のペアを交換します

• すべての「11」を「1」に置き換えます

val（S）をSの10進表現とします。val（A）の場合、正しい文字列Aが別の正しい文字列'B'よりも小さい最小の正しい文字列を見つける必要があります。

したがって、入力がS ="1001"の場合、出力は100になります。これは、 "1001"-> "1010"->"1100"->"100"のような操作を実行できるためです。

ステップ

これを解決するには、次の手順に従います-

n := size of S
res := a blank string
res := res + S[0]
for initialize i := 1, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      res := res concatenate "0"
return res

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
   int n = S.size();
   string res = "";
   res += S[0];
   for (int i = 1; i < n; i++){
      if (S[i] == '0'){
         res += "0";
      }
   }
   return res;
}
int main(){
   string S = "1001";
   cout << solve(S) << endl;
}

入力

"1001"

出力

100