Điền 1 vào mảng bằng ít lần lặp lan truyền nhất trong C++

Cho mảng arr[] n phần tử 0 hoặc 1. Nhiệm vụ: điền 1 vào toàn mảng dùng ít lần lặp lan truyền hàng xóm nhất.

Ví dụ:

Đầu vào: arr[] = {0, 1, 1, 0, 0, 1}

Đầu ra: 1

Phương pháp giải

Quy tắc: nếu arr[i] = 1 => arr[i-1] và arr[i+1] biến thành 1 sau 1 lần lặp.

Xét các khối 0 giữa các 1:

• Trường hợp 1: Khối 0 giữa hai 1. Số lần = số_0 / 2 (làm tròn lên).
• Trường hợp 2: Khối 0 ở đầu/cuối mảng chỉ bên cạnh một 1. Số lần = số_0.
• Trường hợp 3: Không có 1 nào => không thể điền, trả về -1.

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

int countIterationFill1(int arr[], int n) {
    bool oneFound = false;
    int iterationCount = 0;
    for (int i = 0; i < n;) {
        if (arr[i] == 1)
            oneFound = true;
        while (i < n && arr[i] == 1)
            i++;
        int zeroCount = 0;
        while (i < n && arr[i] == 0) {
            zeroCount++;
            i++;
        }
        if (oneFound == false && i == n)
            return -1;
        int itrCount;
        if (i < n && oneFound == true) {
            if ((zeroCount & 1) == 0)
                itrCount = zeroCount / 2;
            else
                itrCount = (zeroCount + 1) / 2;
            zeroCount = 0;
        } else {
            itrCount = zeroCount;
            zeroCount = 0;
        }
        iterationCount = max(iterationCount, itrCount);
    }
    return iterationCount;
}

int main() {
    int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number of iterations to fill 1's is " << countIterationFill1(arr, n);
    return 0;
}

Kết quả

The number of iterations to fill 1's is 2