資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢使陣列成為迴文串所需的最小合併操作次數
在這個問題中，我們給定一個包含 n 個正數的陣列 arr[]。我們的任務是查詢使陣列成為迴文串所需的最小合併操作次數。
迴文陣列類似於迴文串，索引 i 和 n-i 處的元素應該相同。
示例
{5, 1, 7, 2, 7, 1, 5}問題描述 - 我們需要透過對陣列進行操作來使其成為迴文串。並且對陣列唯一有效的操作是合併操作，其中我們將索引 i 和 i+1 處的元素相加。
我們需要返回使給定陣列成為迴文串所需的此類操作的最小數量。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {4, 1, 7, 6, 1, 5}輸出
2
解釋
我們需要兩個合併操作，
將索引 0 和 1 處的元素合併，使陣列變為 {5, 7, 6, 1, 5}。
在此之後，將索引 2 和 3 處的元素合併，使陣列變為 {5, 7, 7, 5}。
解決方案方法
解決此問題的一個簡單方法是找到使字串成為迴文串的操作次數。這是透過使用兩個指標 start 和 end 來完成的。如果兩個指標相遇，即 start == end，則陣列為迴文串。因此，我們將迴圈 start 和 end 指標，並根據以下條件執行操作：
如果 arr[start] == arr[end]，這意味著對於當前索引，陣列滿足迴文串條件。我們將它們移動到下一個索引。即 start++ 和 end--。
如果 arr[start] > arr[end]，在這種情況下，我們需要對 end 索引執行合併操作並將 mergeCount 加 1。
如果 arr[start] < arr[end]，在這種情況下，我們需要對 start 索引執行合併操作並將 mergeCount 加 1。
當 start == end 時，我們將返回 mergeCount。
程式說明了我們解決方案的工作原理，
示例
#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;
}輸出
The minimum number of merge operations required to make the array palindrome is 2
更新於: 2021年3月12日
744 次檢視
廣告