C++で配列回文を作成するためのマージ操作の最小数を見つけます

この問題では、n個の正の数で構成される配列arr []が与えられます。私たちのタスクは、配列回文を作成するためのマージ操作の最小数を見つけることです。

回文配列 回文文字列に似ているため、インデックスiとn-iの要素は同じである必要があります。

例

{5, 1, 7, 2, 7, 1, 5}

問題の説明 −アレイパリンドロームに対して操作を実行して、アレイパリンドロームを作成する必要があります。そして、配列で有効な唯一の操作は、インデックスiとi+1に要素を追加するマージ操作です。

与えられた配列回文を作成するために必要なそのような操作の最小数を返す必要があります。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 1, 7, 6, 1, 5}

出力

2

説明

2つのマージ操作が必要です

インデックス0と1の要素をマージすると、配列は{5、7、6、1、5}になります。

このインデックス2と3の要素をマージした後、配列{5、7、7、5}を作成します。

ソリューションアプローチ

この問題の簡単な解決策は、文字列回文を作成するための操作の数を見つけることです。これは、開始と終了の2つのポインターを使用して行われます。両方のポイントが一致する場合、つまりstart ==endの場合、配列は回文です。したがって、開始ポインタと終了ポインタをループし、これらの条件に基づいて操作を実行します-

• arr [start] ==arr [end]の場合、これは現在のインデックスに対して、arraysがパリンドローム条件を満たしていることを意味します。 Forはそれらを次のインデックスに移動します。つまりstart++とend--。

• arr [start]> arr [end]の場合、この場合、終了インデックスに対してマージ操作を実行し、mergeCountを1つインクリメントする必要があります。

• arr [start]

start==endのときにマージカウントを返します。

ソリューションの動作を説明するプログラム

例

#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