इस ट्यूटोरियल में, हम ज़ीरो काउंट खोजने जा रहे हैं, जिन्हें ऐरे में लगातार 1 की अधिकतम संख्या प्राप्त करने के लिए फ़्लिप करने की आवश्यकता है।
हम समस्या को हल करने के लिए स्लाइडिंग विंडो दृष्टिकोण का उपयोग करने जा रहे हैं। आइए समस्या को हल करने के लिए चरणों को देखें।
-
फ़्लिप करने के लिए सरणी और अधिकतम शून्य प्रारंभ करें।
-
लंबाई के साथ विंडो प्रारंभ, समाप्ति अनुक्रमणिका प्रारंभ करें।
-
लगातार 1 की लंबाई और प्रारंभिक अनुक्रमणिका की अधिकतम उप सरणी संग्रहीत करें।
-
अनुक्रमणिका समाप्त होने तक सरणी पर पुनरावृति करें सरणी लंबाई को पार कर जाती है।
-
यदि शून्यों की संख्या अधिकतम शून्य से कम है, तो समाप्ति सूचकांक में वृद्धि करें और यदि वर्तमान मान शून्य है तो शून्य की गणना करें।
-
यदि शून्यों की संख्या अधिकतम शून्य की संख्या से अधिक है तो प्रारंभिक सूचकांक में वृद्धि करें और यदि वर्तमान मान शून्य है तो शून्य की संख्या घटाएं।
-
अधिकतम विंडो अपडेट करें यदि वर्तमान विंडो की लंबाई पिछले एक से अधिक है।
-
सरणी पर पुनरावृति करें और विंडो आरंभिक अनुक्रमणिका का उपयोग करके शून्य अनुक्रमणिका प्रिंट करें।
उदाहरण
आइए कोड देखें।
#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
int start = 0, end = 0;
int zeroesCount = 0;
int bestWindowCount = 0, bestWindowStartIndex = 0;
while (end < n) {
if (zeroesCount <= maxZeroes) {
if (arr[end] == 0) {
zeroesCount++;
}
end++;
}
if (zeroesCount > maxZeroes) {
if (arr[start] == 0) {
zeroesCount--;
}
start++;
}
if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
bestWindowCount = end - start;
bestWindowStartIndex = start;
}
}
cout << "The indexes are ";
for (int i = 0; i < bestWindowCount; ++i) {
if(arr[bestWindowStartIndex + i] == 0)
cout << bestWindowStartIndex + i << " ";
}
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int maxZeroes= 2;
zeroesIndexes(arr, maxZeroes, 10);
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
The indexes are 5 7
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।