Chương trình tìm độ dài của tập 1s dài nhất bằng cách lật k bit trong Python

Giả sử chúng ta có một danh sách nhị phân, vì vậy ở đây chỉ có các số 1 và số 0 và chúng tôi cũng có một số k khác. Chúng ta có thể đặt nhiều nhất k 0 đến 1s, chúng ta phải tìm độ dài của danh sách con dài nhất chứa tất cả các 1s.

Vì vậy, nếu đầu vào giống như nums =[0, 1, 1, 0, 0, 1, 1] k =2, thì đầu ra sẽ là 6, vì chúng ta có thể đặt hai số 0 ở giữa thành 1 và sau đó danh sách trở thành [0, 1, 1, 1, 1, 1, 1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• số không:=0, ans:=0, j:=0
• đối với mỗi chỉ số i và giá trị n trong nums, thực hiện
  • số không:=số không + (1 khi n giống 0, nếu không thì 0)
  • while các số không> k, do
    • zeros:=zeros - (1 khi nums [j] giống 0, nếu không 0)
    • j:=j + 1
  • if i - j + 1> ans, then
    • ans:=i - j + 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

6