ন্যূনতম k দৈর্ঘ্যের সাবলিস্ট গণনা করার জন্য প্রোগ্রাম যা পাইথনে তালিকার সমস্ত আইটেমকে 0 এ ফ্লিপ করা যেতে পারে

ধরুন আমাদের কাছে 0s এবং 1s সংরক্ষিত সংখ্যা নামক সংখ্যার একটি তালিকা রয়েছে। আমাদের আরেকটি মান k.

আছে

এখন বিবেচনা করুন একটি অপারেশন আছে যেখানে আমরা k দৈর্ঘ্যের একটি সাবলিস্ট ফ্লিপ করি যাতে সমস্ত 1s হবে 0s এবং সমস্ত 0s হবে 1s। সংখ্যাগুলিকে 1 থেকে 0 সেকেন্ডে পরিবর্তন করার জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে। যদি আমরা এটি পরিবর্তন করতে না পারি -1 রিটার্ন করুন।

সুতরাং, ইনপুট যদি nums =[1,1,1,0,0,1,1,1], k =3 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমরা প্রথম তিনটি সংখ্যাকে শূন্যে ফ্লিপ করতে পারি এবং তারপর শেষ তিনটি সংখ্যা শূন্যে ফ্লিপ করুন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=সংখ্যার আকার
res :=0, ফ্লিপড :=0
to_conv :=n আকারের একটি তালিকা এবং 0
দিয়ে পূরণ করুন
0 থেকে n রেঞ্জের জন্য, করুন
- flipped :=Flipped XOR to_conv[i]
- cur :=সংখ্যা[i]
- cur :=cur XOR ফ্লিপড
- যদি cur 1 এর মত হয়, তাহলে
  - flipped :=flipped XOR 1
  - res :=res + 1
  - যদি i + k - 1>=n হয়, তাহলে
    - রিটার্ন -1
  - যদি i + k
    - to_conv[i + k] :=1
রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, nums, k):
      n = len(nums)
      res = 0
      flipped = 0
      to_conv = [0] * n
      for i in range(n):
         flipped ^= to_conv[i]
         cur = nums[i]
         cur ^= flipped
         if cur == 1:
            flipped ^= 1
            res += 1
            if i + k - 1 >= n:
               return -1
            if i + k < n:
               to_conv[i + k] = 1
      return res
ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))

ইনপুট

[1,1,1,0,0,1,1,1], 3