पायथन में लगातार 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] ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• जे:=0

• वैल:=0

• उत्तर :=999999

• loc :=एक नई सूची

• प्रत्येक अनुक्रमणिका i के लिए, और अंकों में x का मान करें, करें

  • अगर x गैर-शून्य है, तो

    • loc के अंत में i डालें

    • m :=भागफल (j + loc का आकार -1) /2

    • वैल :=वैल + लोक[-1] - loc[m] - भागफल (लोक-जे का आकार)/2

    • यदि लोकेशन की लंबाई - j> k, तो

      • m :=भागफल (j + loc का आकार) /2

      • वैल :=वैल - loc[m] - loc[j] - भागफल (लोक -j का आकार)/2

      • जे:=जे + 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