পাইথনে ন্যূনতম অদলবদল করা সমস্ত 1-এর একসাথে গ্রুপ করা

ধরুন আমাদের কাছে একটি বাইনারি অ্যারে ডেটা আছে, আমাদের অ্যারের যেকোনো জায়গায় অ্যারেতে সংরক্ষিত সমস্ত 1-এর গোষ্ঠীবদ্ধ করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক সোয়াপ খুঁজে বের করতে হবে। সুতরাং যদি অ্যারেটি [1,0,1,0,1,0,0,1,1,0,1] এর মতো হয়, তাহলে আউটপুট 3 হবে, কারণ সম্ভাব্য সমাধান হল [0,0,0,0, 0,1,1,1,1,1,1]

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

• একটি সেট করুন :=0, n:=ডেটা অ্যারের দৈর্ঘ্য
• n আকারের একটি অ্যারের যোগফল তৈরি করুন এবং এটি 0 দিয়ে পূরণ করুন, যোগফল [0] :=ডেটা[0] সেট করুন
• এক :=এক + ডেটা[0]
• আমি 1 থেকে n – 1
  পরিসরে
  • summ[i] :=summ[i - 1] + ডেটা[i]
  • এক :=এক + ডেটা[i]
• উত্তর :=এক
• বাম :=0, ডানে :=এক – ১
• যখন ডানে
• যদি বাঁদিকে 0 হয়, তাহলে temp :=summ[right], অন্যথায় temp :=summ[right] – summ[left - 1]
• উত্তর :=সর্বনিম্ন উত্তর, এক – অস্থায়ী
• ডান ও বাম 1 দ্বারা বাড়ান

উদাহরণ(পাইথন)

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

class Solution(object):
   def minSwaps(self, data):
      one = 0
      n = len(data)
      summ=[0 for i in range(n)]
      summ[0] = data[0]
      one += data[0]
      for i in range(1,n):
         summ[i] += summ[i-1]+data[i]
         one += data[i]
      ans = one
      left = 0
      right = one-1
      while right <n:
         if left == 0:
            temp = summ[right]
         else:
            temp = summ[right] - summ[left-1]
         ans = min(ans,one-temp)
         right+=1
         left+=1
      return ans
ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

ইনপুট

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

আউটপুট

3