ধরুন আমাদের একটি বাইনারি স্ট্রিং আছে, আমাদের স্ট্রিং-এর যেকোনো জায়গায় সব 1-কে একত্রে গোষ্ঠীভুক্ত করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক সোয়াপ খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি "10101001101" এর মত হয়, তাহলে আউটপুট হবে 3, কারণ সম্ভাব্য সমাধান হল "00000111111"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ডেটা :=প্রদত্ত স্ট্রিং থেকে বিটগুলির একটি তালিকা
-
একটি সেট করুন :=0, n:=ডেটা অ্যারের দৈর্ঘ্য
-
n আকারের একটি অ্যারের যোগফল তৈরি করুন এবং এটি 0 দিয়ে পূরণ করুন, যোগফল [0] সেট করুন :=ডেটা[0]
-
এক :=এক + ডেটা[0]
-
1 থেকে n – 1
রেঞ্জের জন্য i-
summ[i] :=summ[i - 1] + data[i]
-
one :=one + data[i]
-
-
উত্তর :=এক
-
বাম :=0, ডানে :=এক – ১
-
ডানদিকে
-
বাম যদি 0 হয়, তাহলে temp :=summ[right], অন্যথা temp :=summ[right] –
- সমষ্টি[বাম - 1]
-
উত্তর :=সর্বনিম্ন উত্তর, এক – টেম্প
-
ডান এবং বাম 1 দ্বারা বাড়ান
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution(object):
def solve(self, data):
data = list(map(int, list(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.solve("10101001101")) ইনপুট
"10101001101"
আউটপুট
3
