Pythonですべての1をグループ化するために必要な最小スワップを見つけるためのプログラム

バイナリ文字列があるとすると、文字列内の任意の場所ですべての1をグループ化するために必要なスワップの最小数を見つける必要があります。したがって、入力が「10101001101」のような場合、可能な解決策は「00000111111」であるため、出力は3になります。

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

• data：=指定された文字列のビットのリスト

• 1つ設定：=0、n：=データ配列の長さ

• サイズnの配列の合計を作成し、これを0で埋め、summ [0]：=data [0]

  を設定します。

• one：=one + data [0]

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

  • summ [i]：=summ [i-1] + data [i]

  • one：=one + data [i]

• ans：=one

• 左：=0、右：=1 – 1

• 右

  • leftが0の場合、temp：=summ [right]、それ以外の場合、temp：=summ [right] –

  • summ [left-1]

  • ans：=ansの最小値、1 – temp

  • 左右を1つ増やします

• ansを返す

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

例

class Solution(object):
   def solve(self, data):
      data = list(map(int, list(data)))
      one = 0
      n = len(data)
      summ=[0 for i in range(n)]
      summ[0] = data[0]
      one += data[0]
      for i in range(1,n):
         summ[i] += summ[i-1]+data[i]
         one += data[i]
      ans = one
      left = 0
      right = one-1
      while right <n:
         if left == 0:
            temp = summ[right]
         else:
            temp = summ[right] - summ[left-1]
         ans = min(ans,one-temp)
         right+=1
         left+=1
         return ans
ob = Solution()
print(ob.solve("10101001101"))

入力

"10101001101"

出力

3