Pythonの特定の文字列で最小数のスワップで1をグループ化するプログラム

0と1を含むバイナリ文字列input_strが与えられたとします。私たちのタスクは、指定された文字列の1を交換することにより、0と1をグループ化することです。最小限の数のスワップ操作を実行する必要があり、その値を返す必要があります。覚えておくべきことの1つは、隣接する値のみを交換できることです。

したがって、入力がinput_str =10110101のような場合、出力は4

スワップは次のようになります-

10110101->01110101->01111001->01111010->01111100

スワップの総数：4。

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

• one：=1が配置されているinput_strの位置を含む新しいリスト
• mid：=（1/2のサイズ）のフロア値
• res：=0
• 0から1のサイズのiの場合は、
  • res：=res + | one [mid] --one [i] | -| mid --i |
• res <0の場合、
  • 0を返す
• それ以外の場合、
  • return res

例

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

def solve(input_string):
   one = [i for i in range(len(input_string)) if input_string[i] == "1"]
   mid = len(one) // 2
   res = 0
   for i in range(len(one)):
      res += abs(one[mid] - one[i]) - abs(mid - i)
   return 0 if res < 0 else res

print(solve('10110101'))

入力

'10110101'

出力

4