查找在C ++中进行数组回文的最小合并操作数

在这个问题中，我们得到了一个由n个正数组成的数组arr []。我们的任务是找到进行阵列回文的最小合并操作数。

回文数组与回文字符串相似，索引i和ni的元素应相同。

示例

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

问题描述-我们需要通过对其执行操作来使阵列回文。并且在数组上唯一有效的操作是合并操作，在合并操作中，我们将在索引i和i + 1处添加元素。

我们需要返回使给定数组回文所需的最小数量的此类操作。

让我们举个例子来了解这个问题，

输入

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

输出结果

2

解释

我们需要两个合并操作，

合并索引为0和1的元素将形成数组{5，7，6，6，1，5}。

合并索引2和3的元素后，形成数组{5，7，7，5}。

解决方法

解决该问题的一种简单方法是找到使字符串回文的操作数。这是通过使用两个指针start和end来完成的。如果两个点都相遇，即开始==结束，则该数组为回文。因此，我们将循环搜索起点和终点指针，并根据以下条件执行操作-

• 如果arr [start] == arr [end]，则对于当前索引，该数组满足回文条件。对于将它们移到下一个索引。即开始++和结束-。

• 如果arr [start]> arr [end]，在这种情况下，我们需要对end索引执行合并操作，并将mergeCount递增1。

• 如果arr [start] <arr [end]，在这种情况下，我们需要对起始索引执行合并操作，并将mergeCount递增1。

当开始==结束时，我们将返回合并计数。

该程序说明了我们解决方案的工作原理，

示例

#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<<"使阵列回文所需的最小合并操作数为 "<<findMergeCount(arr, n);
   return 0;
}

输出结果

使阵列回文所需的最小合并操作数为 2