Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số dương. Nhiệm vụ của chúng ta là Tìm số lượng phép toán hợp nhất tối thiểu để tạo ra một mảng palindrome.
Mảng Palindrome tương tự như chuỗi palindrome, các phần tử ở chỉ mục i và n-i phải giống nhau.
Ví dụ
{5, 1, 7, 2, 7, 1, 5} Mô tả sự cố - Chúng ta cần tạo mảng palindrome bằng cách thực hiện các phép toán trên nó. Và hoạt động duy nhất hợp lệ trên mảng là hoạt động hợp nhất, trong đó chúng tôi sẽ thêm các phần tử tại chỉ mục i và i + 1.
Chúng ta cần trả về số lượng tối thiểu các phép toán như vậy cần thiết để tạo makethe mảng palindrome đã cho.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 1, 7, 6, 1, 5} Đầu ra
2
Giải thích
Chúng tôi cần hai hoạt động hợp nhất,
Hợp nhất các phần tử ở chỉ mục 0 và 1, tạo thành mảng {5, 7, 6, 1, 5}.
Sau khi hợp nhất các phần tử này ở chỉ mục 2 và 3, tạo thành mảng {5, 7, 7, 5}.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm số phép toán để tạo chuỗi palindrome. Điều này được thực hiện bằng cách sử dụng hai con trỏ bắt đầu và kết thúc. Nếu cả hai điểm gặp nhau, tức là start ==end thì mảng là palindrome. Vì vậy, chúng tôi sẽ lặp lại cho con trỏ bắt đầu và kết thúc và thực hiện hoạt động dựa trên các điều kiện này -
-
Nếu arr [start] ==arr [end], điều này có nghĩa là đối với chỉ mục hiện tại, mảng thỏa mãn điều kiện palindrome. For sẽ chuyển chúng đến chỉ mục tiếp theo. I E. bắt đầu ++ và kết thúc--.
-
Nếu arr [start]> arr [end], trong trường hợp này chúng ta cần thực hiện thao tác hợp nhất cho chỉ mục cuối và tăng Số lượng hợp nhất lên 1.
-
Nếu arr [start]
Chúng tôi sẽ trả về số lượng hợp nhất khi bắt đầu ==kết thúc.
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 findMergeCount(int arr[], int n){
int mergeCount = 0;
int start = 0;
int end = n-1;
while(start <= end){
if (arr[start] == arr[end]){
start++;
end--;
}
else if (arr[start] > arr[end]){
end--;
arr[end] += arr[end+1] ;
mergeCount++;
} else {
start++;
arr[start] += arr[start-1];
mergeCount++;
}
}
return mergeCount;
}
int main(){
int arr[] = {4, 1, 7, 6, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The minimum number of merge operations required to make the array palindrome is "<<findMergeCount(arr, n);
return 0;
} Đầu ra
The minimum number of merge operations required to make the array palindrome is 2