पायथन में K लगातार 1 के लिए न्यूनतम आसन्न स्वैप खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ऐरे nums और एक मान k है। एक चाल में, हम दो आसन्न इंडेक्स का चयन कर सकते हैं और उनके मानों को स्वैप कर सकते हैं। हमें चालों की न्यूनतम संख्या ढूंढनी है ताकि nums में 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]।

हल करने के चरण

1. j := 0
2. val := 0
3. ans := 999999
4. loc := एक नई सूची
5. nums में प्रत्येक इंडेक्स i और मान x के लिए:
   • यदि x नॉन-जीरो है, तो:
     • i को loc के अंत में जोड़ें
     • m := (j + len(loc) - 1) // 2
     • val := val + loc[-1] - loc[m] - (len(loc) - j) // 2
     • यदि len(loc) - j > k, तो:
       • m := (j + len(loc)) // 2
       • val := val - loc[m] - loc[j] - (len(loc) - j) // 2
       • j := j + 1
     • यदि len(loc) - j == k, तो:
       • ans := min(ans, val)
6. 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

आउटपुट

2