Python程序：翻转k位后查找最长1序列的长度

假设我们有一个二进制列表，其中只有1和0，还有一个数字k。我们可以将最多k个0设置为1，我们需要找到包含所有1的最长子列表的长度。

例如，如果输入是nums = [0, 1, 1, 0, 0, 1, 1]，k = 2，则输出为6，因为我们可以将中间两个0设置为1，然后列表变为[0, 1, 1, 1, 1, 1, 1]。

为了解决这个问题，我们将遵循以下步骤：

  • zeros := 0, ans := 0, j := 0
  • 对于nums中的每个索引i和值n，执行：
    • zeros := zeros + (如果n为0则为1，否则为0)
    • 当zeros > k时，执行：
      • zeros := zeros - (如果nums[j]为0则为1，否则为0)
      • j := j + 1
    • 如果i - j + 1 > ans，则
      • ans := i - j + 1
  • 返回ans

让我们看下面的实现来更好地理解：

示例

在线演示

class Solution:
   def solve(self, nums, k):
      zeros = 0
      ans = 0
      j = 0
      for i, n in enumerate(nums):
         zeros += n == 0
         while zeros > k:
            zeros -= nums[j] == 0
            j += 1
         if i - j + 1 > ans:
            ans = i - j + 1
      return ans
ob = Solution()
nums = [0, 1, 1, 0, 0, 1, 1]
k = 2
print(ob.solve(nums, k))

输入

[0, 1, 1, 0, 0, 1, 1], 2

输出

6

更新于：2020年11月19日

浏览量：152

启动你的职业生涯

完成课程获得认证

开始学习
广告