สมมติว่าเรามีรายการไบนารี ดังนั้นที่นี่มีเพียง 1 และ 0 เท่านั้นที่มีและเรายังมีตัวเลข k อีกตัว เราสามารถตั้งค่าได้มากที่สุด k 0s ถึง 1s เราต้องหาความยาวของรายการย่อยที่ยาวที่สุดที่มี 1s ทั้งหมด
ดังนั้น หากอินพุตเป็น nums =[0, 1, 1, 0, 0, 1, 1] k =2 ผลลัพธ์จะเป็น 6 เนื่องจากเราสามารถตั้งค่า 0s ตรงกลางสองตัวเป็น 1s จากนั้นรายการจะกลายเป็น [0, 1, 1, 1, 1, 1, 1].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ศูนย์ :=0, ans :=0, j :=0
- สำหรับแต่ละดัชนี i และค่า n เป็น nums ทำ
- ศูนย์ :=ศูนย์ + (1 เมื่อ n เท่ากับ 0 มิฉะนั้น 0)
- ในขณะที่ศูนย์> k ทำ
- ศูนย์ :=ศูนย์ - (1 เมื่อ nums[j] เท่ากับ 0 มิฉะนั้น 0)
- j :=j + 1
- ถ้า i - j + 1> แล้ว
- ตอบ :=i - j + 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
