Trong bài toán này, chúng ta được cung cấp một bin mảng nhị phân [] bao gồm n giá trị nhị phân có giá trị là 0 và 1. Nhiệm vụ của chúng ta là tìm các phép toán tối thiểu cần thiết để làm cho Mảng đẹp.
Mảng đẹp là một loại mảng nhị phân đặc biệt bao gồm mẫu thay đổi gốc 0 và 1.
Mô tả sự cố - Chúng ta cần tìm các phép toán số bắt buộc phải có để làm cho mảng đẹp. Một hoạt động bao gồm các bước sau -
Bước 1 - Cắt mảng thành hai nửa.
Bước 2 - Đảo ngược bất kỳ một trong hai nửa.
Bước 3 - Tham gia sau đó giảm một nửa.
Chúng tôi sẽ đếm số lượng các phép toán được yêu cầu để đảm bảo rằng mảng trở thành một mảng đẹp.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
bin[] = {1, 0, 1, 0, 0, 1} Đầu ra
1
Giải thích
Chúng tôi sẽ cắt mảng, tạo một bin của mảng con [4, 5], đảo ngược nó và nối nó trở lại.
Phương pháp tiếp cận giải pháp
Giải pháp cho vấn đề này dựa trên việc tìm số lượng tối thiểu các hoạt động chuyển đổi bằng số lượng các số không liên tiếp. Các trường hợp cơ bản là -
Nếu kích thước của mảng là 1, nó là một mảng đẹp. Nếu kích thước của mảng là một số lẻ thì nó không bao giờ có thể là một mảng đẹp.
Đối với tất cả các độ dài chẵn, chúng tôi sẽ kiểm tra tổng số các ô số không liên tiếp sẽ là số hoạt động được thực hiện.
Thuật toán
Khởi tạo - zeroCount, oneCount, consZero =0
Bước 1 - if (n =1), trả về 0
Bước 2 - if (n% 2! =0), trả về -1.
Bước 3 - Vòng lặp cho i -> 0 đến n-1.
Bước 3.1 - if bin [i] ==bin [i + 1] ==0, consZero ++.
Bước 4 - if bin [n-1] ==bin [0] ==0, consZero ++.
Bước 5 - trả lại consZero.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int minOperations(int bin[], int n) {
if(n == 1)
return 0;
if(n%2 != 0)
return -1;
int consZero = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n) {
if (bin[i] == 0 && bin[i + 1] == 0)
consZero++;
}
}
if (bin[0] == bin[n - 1] && bin[0] == 0)
consZero++;
return consZero;
}
int main() {
int bin[] = { 1, 0, 1, 0, 0, 1};
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n);
return 0;
} Đầu ra
The minimum operations needed to make an Array beautiful is 1