পাইথনে Kটি কনsekutিভ ১ পাওয়ার জন্য ন্যূনতম এডজেসেন্ট সোয়াপ খুঁজে বের করার প্রোগ্রাম

আমাদের একটি বাইনারি অ্যারে nums এবং একটি মান k আছে। এক মুভে, আমরা দুটি এডজেসেন্ট ইন্ডেক্স সিলেক্ট করে তাদের মান সোয়াপ করতে পারি। আমাদের ন্যূনতম মুভ সংখ্যা বের করতে হবে যাতে nums-এ kটি কনsekutিভ 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, ans := 999999, loc := একটি নতুন লিস্ট
nums-এর প্রতিটি ইন্ডেক্স i এবং ভ্যালু x এর জন্য:
- যদি x != 0 হয়, তবে:
  - i-কে loc-এর শেষে যোগ করুন
  - m := (j + len(loc) - 1) // 2
  - val += loc[-1] - loc[m] - (len(loc) - j) // 2
  - যদি len(loc) - j > k হয়, তবে:
    - m := (j + len(loc)) // 2
    - val -= loc[m] - loc[j] - (len(loc) - j) // 2
    - j := j + 1
  - যদি len(loc) - j == k হয়, তবে:
    - ans := min(ans, val)
ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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