Python程式：計算翻轉最少數量的長度為k的子列表，以使列表的所有元素都變為0

假設我們有一個名為nums的數字列表，其中儲存了0和1。我們還有另一個值k。

現在假設有一個操作，我們可以翻轉長度為k的子列表，使得所有1都變為0，所有0都變為1。我們必須找到將nums更改為所有1都變為0所需的最小操作次數。如果我們無法更改它，則返回-1。

因此，如果輸入類似於nums = [1,1,1,0,0,1,1,1]，k = 3，則輸出將為2，因為我們可以將前三個數字翻轉為零，然後將最後三個數字翻轉為零。

為了解決這個問題，我們將遵循以下步驟：

  • n := nums的大小

  • res := 0，flipped := 0

  • to_conv := 一個大小為n的列表，並填充0

  • 對於範圍從0到n的i，執行以下操作：

    • flipped := flipped XOR to_conv[i]

    • cur := nums[i]

    • cur := cur XOR flipped

    • 如果cur等於1，則：

      • flipped := flipped XOR 1

      • res := res + 1

      • 如果i + k - 1 >= n，則：

        • 返回-1

      • 如果i + k < n，則：

        • to_conv[i + k] := 1

  • 返回res

示例

讓我們看看以下實現以更好地理解：

即時演示

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

更新於： 2020年12月22日

70 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告