Pythonでリストのすべてのアイテムを0にするために反転できる最小k長のサブリストをカウントするプログラム

0と1を格納したnumsと呼ばれる数値のリストがあるとします。別の値kがあります。

ここで、すべての1が0になり、すべての0が1になるように、長さkのサブリストを反転する操作があるとします。 numsをすべて1から0に変更するために必要な操作の最小数を見つける必要があります。変更できない場合は-1を返します。

したがって、入力がnums =[1,1,1,0,0,1,1,1]、k =3のような場合、最初の3つの数値をゼロに反転してから、出力は2になります。最後の3つの数字をゼロに反転します。

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

• n：=numsのサイズ

• res：=0、反転：=0

• to_conv：=サイズnのリストで0を入力

• 0からnの範囲のiの場合、実行

  • 反転：=反転XOR to_conv [i]

  • cur：=nums [i]

  • cur：=curXORが反転しました

  • curが1と同じ場合、

    • 反転：=反転XOR 1

    • res：=res + 1

    • i + k-1> =nの場合、

      • -1を返す

    • i + k

      • to_conv [i + k]：=1

• 解像度を返す

例

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

class Solution:
   def solve(self, nums, k):
      n = len(nums)
      res = 0
      flipped = 0
      to_conv = [0] * n
      for i in range(n):
         flipped ^= to_conv[i]
         cur = nums[i]
         cur ^= flipped
         if cur == 1:
            flipped ^= 1
            res += 1
            if i + k - 1 >= n:
               return -1
            if i + k < n:
               to_conv[i + k] = 1
      return res
ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))

入力

[1,1,1,0,0,1,1,1], 3

出力

2