Tìm chỉ số 0 cần thay bằng 1 để có chuỗi 1 liên tục dài nhất trong mảng nhị phân - Tập 2 trong C++

Khái niệm

Cho mảng chỉ chứa 0 và 1, tìm vị trí của 0 cần thay bằng 1 để có chuỗi 1 liên tục dài nhất. Độ phức tạp thời gian mong đợi O(n) và không gian phụ O(1).

Đầu vào

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

Đầu ra

Chỉ số 10

Giả sử chỉ số mảng bắt đầu từ 0, thay 0 bằng 1 tại chỉ số 10 tạo ra chuỗi 1 liên tục dài nhất.

Đầu vào

arr[] = {1, 1, 1, 1, 1, 0}

Đầu ra

Chỉ số 5

Phương pháp

Sử dụng đếm số 1 ở hai bên của 0:

Ý tưởng: đếm số 1 ở hai bên của mỗi 0. Chỉ số cần tìm là chỉ số của 0 có số 1 xung quanh nhiều nhất. Các biến:

• leftCnt: số 1 bên trái 0 đang xét.
• rightCnt: số 1 bên phải 0 đang xét.
• maxIndex: chỉ số 0 có số 1 xung quanh nhiều nhất.
• lastInd: chỉ số 0 cuối cùng đã thấy.
• maxCnt: số 1 nếu 0 tại maxIndex được thay bằng 1.

Quy trình:

• Tăng rightCnt cho đến khi gặp 0 tại chỉ số i.
• Kiểm tra xem 0 này có phải 0 đầu tiên không (lastInd không hợp lệ). Nếu là đầu tiên: cập nhật lastInd = i, leftCnt = rightCnt, reset rightCnt = 0.
• Nếu không phải 0 đầu tiên: số 1 xung quanh 0 tại lastInd là leftCnt + rightCnt. Cập nhật maxCnt = leftCnt + rightCnt + 1 và maxIndex = lastInd nếu lớn hơn maxCnt hiện tại.
• Gán rightCnt thành leftCnt cho 0 tại i, lastInd = i, reset rightCnt = 0.
• Lặp lại cho các 0 tiếp theo.
• Cuối cùng, maxIndex lưu chỉ số 0 cần thay.

Ví dụ

// Chương trình C++ tìm chỉ số 0 thay bằng 1 để có chuỗi 1 dài nhất
#include <bits/stdc++.h>
using namespace std;

// Trả về chỉ số 0 cần thay bằng 1 để có chuỗi 1 liên tục dài nhất
// Trả về -1 nếu mảng không có 0
int maxOnesIndex(bool arr1[], int n1){
    int i = 0;
    int leftCnt1 = 0;
    int rightCnt1 = 0;
    int maxIndex1 = -1;
    int lastInd1 = -1;
    int maxCnt1 = 0;
    while (i < n1) {
        if (arr1[i]) {
            rightCnt1++;
        }
        else {
            if (lastInd1 != -1) {
                if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
                    maxCnt1 = leftCnt1 + rightCnt1 + 1;
                    maxIndex1 = lastInd1;
                }
            }
            lastInd1 = i;
            leftCnt1 = rightCnt1;
            rightCnt1 = 0;
        }
        i++;
    }
    // Xét 0 cuối cùng
    if (lastInd1 != -1) {
        if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
            maxCnt1 = leftCnt1 + rightCnt1 + 1;
            maxIndex1 = lastInd1;
        }
    }
    return maxIndex1;
}

// Chương trình chính
int main(){
    bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Chỉ số 0 cần thay là " << maxOnesIndex(arr1, n1);
    return 0;
}

Đầu ra

Chỉ số 0 cần thay là 10