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