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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告