मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है, हमें स्ट्रिंग में किसी भी स्थान पर सभी 1 को एक साथ समूहित करने के लिए आवश्यक न्यूनतम संख्या में स्वैप की आवश्यकता है। तो अगर इनपुट "10101001101" जैसा है, तो आउटपुट 3 होगा, जितना संभव हो समाधान "000001111111" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
डेटा:=दिए गए स्ट्रिंग से बिट्स की एक सूची
-
एक सेट करें:=0, n:=डेटा सरणी की लंबाई
-
आकार n का एक सरणी योग बनाएं, और इसे 0 से भरें, योग सेट करें [0]:=डेटा [0]
-
एक:=एक + डेटा[0]
-
मैं के लिए 1 से n - 1 की सीमा में
-
योग [i]:=योग [i - 1] + डेटा [i]
-
एक:=एक + डेटा[i]
-
-
उत्तर :=एक
-
बाएँ:=0, दाएँ:=एक – 1
-
जबकि दाएं
-
यदि बायां 0 है, तो अस्थायी:=योग [दाएं], अन्यथा अस्थायी:=योग [दाएं] -
- सारांश[बाएं - 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