Chương trình tìm độ dài dãy 1 dài nhất sau khi lật tối đa k bit 0 trong Python

Mô tả bài toán

Cho danh sách nhị phân nums và số k. Có thể đổi tối đa k số 0 thành 1. Tìm độ dài danh sách con liên tiếp toàn 1 dài nhất.

Ví dụ: nums = [0,1,1,0,0,1,1], k = 2 → đầu ra 6 (lật hai 0 ở giữa thành 1).

Giải thuật (Cửa sổ trượt đếm số 0)

1. Khởi tạo zeros = 0, ans = 0, j = 0.
2. Duyệt i từ 0 đến n-1:
   • Nếu nums[i] == 0: zeros += 1.
   • Khi zeros > k: nếu nums[j] == 0 thì zeros -= 1; j += 1.
   • Cập nhật ans = max(ans, i - j + 1).
3. Trả về ans.

Ví dụ mã Python

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