পাইথনে K ধারাবাহিকের জন্য ন্যূনতম সংলগ্ন অদলবদল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি অ্যারে সংখ্যা এবং একটি মান k আছে। এক পদক্ষেপে, আমরা দুটি সন্নিহিত সূচক নির্বাচন করতে পারি এবং তাদের মান অদলবদল করতে পারি। আমাদের ন্যূনতম সংখ্যক চাল খুঁজে বের করতে হবে যাতে সংখ্যায় k পরপর 1 থাকে।

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

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

• j :=0

• val :=0

• উত্তর :=999999

• loc :=একটি নতুন তালিকা

• প্রতিটি সূচকের জন্য i, এবং মান x সংখ্যায়, করুন

  • যদি x অ-শূন্য হয়, তাহলে

    • loc

      এর শেষে i ঢোকান

    • m :=এর ভাগফল (j + loc - 1 এর আকার) /2

    • val :=val + loc[-1] - loc[m] - এর ভাগফল (loc -j এর আকার)/2

    • যদি loc - j> k এর দৈর্ঘ্য হয়, তাহলে

      • m :=(j + loc এর আকার) /2

        এর ভাগফল

      • val :=val - loc[m] - loc[j] - এর ভাগফল (loc -j এর আকার)/2

      • j :=j + 1

    • যদি loc -j এর আকার k এর সমান হয়, তাহলে

      • উত্তর :=সর্বনিম্ন উত্তর এবং ভ্যাল

• উত্তর ফেরত দিন

উদাহরণ

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

def solve(nums, k):
   j = val = 0
   ans = 999999
   loc = []
   for i, x in enumerate(nums):
      if x:
         loc.append(i)
         m = (j + len(loc) - 1)//2
         val += loc[-1] - loc[m] - (len(loc)-j)//2
         if len(loc) - j > k:
            m = (j + len(loc))//2
            val -= loc[m] - loc[j] - (len(loc)-j)//2
            j += 1
         if len(loc)-j == k:
            ans = min(ans, val)
   return ans

nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))

ইনপুট

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

আউটপুট

2