Pythonで交互の値を持つために必要なフリップの最小数を見つけるためのプログラム

バイナリ文字列sがあるとします。ここで、sの接頭辞を取り、それを後ろに移動できると仮定します。次に、同じ値の連続する文字がないように、反転する必要のある文字の最小数を見つけます。

したがって、入力がs ="10010101111"の場合、プレフィックス "10"を取得できるため、出力は2になります。次に、文字列が "01010111110"になるように後ろに移動し、3番目と5番目のビットを右から0に反転します。 （"01010101010"）。

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

• ans：=Sのサイズ

• N：=Sのサイズ

• s：=0

• 0から2*Nの範囲のiの場合、実行

  • s：=s +（S [i mod N] XOR（i AND 1））の整数

  • i> =N-1の場合、

    • ans：=ans、s、Nの最小値-s

    • s：=s-（S [（i-（N-1））mod N]）XOR（（i-（N-1））AND 1）

      の整数

• ansを返す

例

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

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

入力

"10010101111"

出力

2