ในบทช่วยสอนนี้ เราจะค้นหาจำนวนศูนย์ที่ต้องพลิกเพื่อให้ได้จำนวนสูงสุดของ 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
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
