Trong hướng dẫn này, chúng ta sẽ tìm số lượng các số 0 cần được lật lại để có được số lượng lớn nhất các số 1 liên tiếp trong mảng.
Chúng tôi sẽ sử dụng cách tiếp cận cửa sổ trượt để giải quyết vấn đề. Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo mảng và các số 0 tối đa được lật.
-
Khởi tạo cửa sổ bắt đầu, kết thúc chỉ mục cùng với độ dài.
-
Lưu trữ mảng con tối đa có độ dài và chỉ số bắt đầu của 1 liên tiếp.
-
Lặp lại trên mảng cho đến khi các chỉ mục kết thúc vượt qua độ dài của mảng.
-
Nếu số 0 nhỏ hơn số 0 tối đa thì hãy tăng chỉ số kết thúc và đếm số 0 nếu giá trị hiện tại bằng 0.
-
Nếu số 0 lớn hơn số 0 tối đa thì hãy tăng chỉ số bắt đầu và giảm số 0 nếu giá trị hiện tại bằng 0.
-
Cập nhật cửa sổ tối đa nếu độ dài cửa sổ hiện tại lớn hơn cửa sổ trước đó.
-
Lặp lại trên mảng và in các chỉ mục bằng không bằng cách sử dụng chỉ mục bắt đầu cửa sổ.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
The indexes are 5 7
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.