ধরুন আমাদের একটি বাইনারি তালিকা আছে, তাহলে এখানে শুধুমাত্র 1s এবং 0s পাওয়া যাবে এবং আমাদের কাছে আরও একটি সংখ্যা 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, উত্তর :=0, j :=0
- প্রতিটি সূচক i এবং n এর মান সংখ্যার জন্য, করুন
- শূন্য :=শূন্য + (1 যখন n 0 এর মত হয়, অন্যথায় 0)
- যখন শূন্য> k, do
- শূন্য :=শূন্য - (1 যখন সংখ্যা [j] 0 এর মত হয়, অন্যথায় 0)
- j :=j + 1
- যদি i - j + 1> ans, তাহলে
- উত্তর :=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
