मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग है, हमें सभी 1's को स्ट्रिंग में किसी भी स्थान पर एक साथ समूहित करने के लिए आवश्यक न्यूनतम स्वैप की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट "10101001101" है, तो आउटपुट 3 होगा, क्योंकि संभावित समाधान "00000111111" है।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (स्लाइडिंग विंडो + प्रीफिक्स सम):
data := दी गई स्ट्रिंग से बिट्स की सूची।one := 0,n := len(data)।summआकार n की सरणी बनाएं और 0 से भरें,summ[0] = data[0]।one += data[0]।iको 1 सेn-1तक:summ[i] = summ[i-1] + data[i];one += data[i]।ans := one।left := 0,right := one - 1।जब तक
right < n:यदि
left == 0तोtemp = summ[right], अन्यथाtemp = summ[right] - summ[left-1]।ans = min(ans, one - temp)।right += 1;left += 1।
ansलौटाएं।
उदाहरण
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
