หาตำแหน่งศูนย์ที่ควรพลิกเพื่อให้ได้ 1 ติดต่อกันมากที่สุดใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ดัชนีของศูนย์ (0) ที่ควรพลิกเป็น 1 เพื่อให้ได้ ลำดับ 1 ติดต่อกันยาวที่สุด ในอาร์เรย์บाइनนารี โดยกำหนดจำนวนศูนย์สูงสุดที่พลิกได้ (maxZeroes)

อัลกอริทึม: Sliding Window (หน้าต่างเลื่อน)

รักษาหน้าต่าง [start, end) ที่มีศูนย์ไม่เกิน maxZeroes ตัว ขยาย end เมื่อศูนย์ ≤ maxZeroes, ยุบ start เมื่อเกิน

ขั้นตอนการแก้ปัญหา

1. กำหนดอาร์เรย์และ maxZeroes
2. เริ่มต้น start=0, end=0, zeroesCount=0
3. เก็บ bestWindowCount (ความยาวหน้าต่างดีที่สุด) และ bestWindowStartIndex
4. วนลูปขยาย end:
   • ถ้า zeroesCount ≤ maxZeroes: ขยาย end, นับศูนย์
   • ถ้า zeroesCount > maxZeroes: ยุบ start, ลดนับศูนย์
5. อัปเดต bestWindow เมื่อหน้าต่างปัจจุบันยาวกว่า
6. พิมพ์ดัชนีของศูนย์ในหน้าต่างที่ดีที่สุด

ตัวอย่างโค้ด

#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

คำอธิบาย: พลิกดัชนี 5 และ 7 (ค่า 0→1) ได้ลำดับ 1 ติดต่อกันยาว 6 ตัว (ดัชนี 4-9)

สรุป

Sliding Window แก้ปัญหานี้ใน O(n) เวลาและ O(1) พื้นที่ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ