Pythonでバイナリ文字列を交互に使用するために必要な最小限の変更を見つけるプログラム

バイナリ文字列sがあるとします。 1ビット反転できる操作を考えてみましょう。隣接する2つの文字が同じでない場合、文字列sは交互文字列と呼ばれます。を交互にするために必要な最小数の操作を見つける必要があります。

したがって、入力がs ="11100011"の場合、出力は3になります。これは、位置1、4、および7でビットを反転すると、 "10101010"になり、すべてが交互になるためです。

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

• 変更：=0

• even_1：=0、even_0：=0

• odd_1：=0、odd_0：=0

• 0からs-1のサイズのiの場合、実行します

  • 私が偶数の場合、

    • s[i]が「1」と同じ場合

      • even_1：=even_1 + 1

    • それ以外の場合

      • even_0：=even_0 + 1

  • それ以外の場合

    • s[i]が「1」と同じ場合

      • odd_1：=odd_1 + 1

    • それ以外の場合

      • odd_0：=odd_0 + 1

• if（even_1 + odd_0）>（even_0 + odd_1）、then

  • 変更：=even_0 + odd_1

• それ以外の場合

  • 変更：=even_1 + odd_0

• 返品変更

例（Python）

＆minnus;

def solve(s):
   change = 0
   even_1 = 0
   even_0 = 0
   odd_1 = 0
   odd_0 = 0
   for i in range(len(s)):
      if(i%2 == 0):
         if(s[i]=='1'):
            even_1 +=1
         else:
            even_0 +=1
      else:
         if(s[i] == '1'):
            odd_1 +=1
         else:
            odd_0 +=1
   if((even_1+odd_0)>(even_0+odd_1)):
      change = even_0 + odd_1
   else:
      change = even_1 + odd_0
   return change

s = "11100011"
print(solve(s))

入力

"11100011"

出力

3