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

Arnab Chakraborty

更新於：2020年11月19日

瀏覽量：152

啟動你的職業生涯

完成課程獲得認證

開始學習