โปรแกรมหาความยาว 1s ติดกันมากสุดหลังกลับบิต k ตัวใน Python

สมมติว่ามีรายการไบนารี (0 และ 1) และตัวเลข k สามารถเปลี่ยน 0 เป็น 1 ได้สูงสุด k ตัว ต้องการหาความยาวสับลิสต์ยาวสุดที่เป็น 1 ทั้งหมด

ตัวอย่าง: nums = [0, 1, 1, 0, 0, 1, 1], k = 2 ผลลัพธ์ 6 เปลี่ยน 0 กลาง 2 ตัวได้ [0, 1, 1, 1, 1, 1, 1]

ขั้นตอนการแก้ปัญหา

1. zeros = 0, ans = 0, j = 0
2. วน i, n ใน enumerate(nums):
   • zeros += (n == 0)
   • ขณะ zeros > k:
     • zeros -= (nums[j] == 0)
     • j += 1
   • ans = max(ans, i - j + 1)
3. คืน 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