এই টিউটোরিয়ালে, আমরা সে জেরোগুলো বের করব যেগুলো ফ্লিপ করলে অ্যারেতে সর্বোচ্চ কমsekutিভ ১ পাওয়া যাবে।
আমরা স্লাইডিং উইন্ডো অ্যাপ্রোচ ব্যবহার করব সমস্যাটি সমাধান করতে। সমস্যাটি সমাধানের ধাপগুলো:
- অ্যারে এবং ম্যাক্স জেরো ফ্লিপ ইনিশিয়ালাইজ করুন।
- উইন্ডো স্টার্টিং, এন্ডিং ইনডেক্স এবং দৈর্ঘ্য ইনিশিয়ালাইজ করুন।
- সর্বোচ্চ কমsekutিভ ১-এর সাবঅ্যারে দৈর্ঘ্য এবং স্টার্টিং ইনডেক্স স্টোর করুন।
- অ্যারেতে ইটারেট করুন যতক্ষণ এন্ডিং ইনডেক্স অ্যারে দৈর্ঘ্য পাড় না করে।
- যদি জেরো কাউন্ট ম্যাক্স জেরো কাউন্টের চেয়ে কম হয় তবে এন্ডিং ইনডেক্স বাড়ান এবং জেরো কাউন্ট বাড়ান যদি কারেন্ট ভ্যালু জেরো হয়।
- যদি জেরো কাউন্ট ম্যাক্স জেরো কাউন্টের চেয়ে বেশি হয় তবে স্টার্টিং ইনডেক্স বাড়ান এবং জেরো কাউন্ট কমান যদি কারেন্ট ভ্যালু জেরো হয়।
- যদি কারেন্ট উইন্ডো দৈর্ঘ্য প্রিভিয়াসের চেয়ে বেশি হয় তবে ম্যাক্স উইন্ডো আপডেট করুন।
- অ্যারেতে ইটারেট করুন এবং উইন্ডো স্টার্টিং ইনডেক্স ব্যবহার করে জেরো ইনডেক্স প্রিন্ট করুন।
উদাহরণ
কোডটি দেখি।
#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
উপসংহার
টিউটোরিয়ালে যদি কোনো প্রশ্ন থাকে, তবে কমেন্ট সেকশনে জানান।
