微客导航 » 文章资讯 » 使用给定的规则在C ++中查找数组的最小可能大小

使用给定的规则在C ++中查找数组的最小可能大小

2024-02-21 18:29:03 135

在这个问题中，我们得到了一个由n个数字和一个整数k组成的数组。我们的任务是使用给定的删除元素规则，找到数组的最小可能大小。

问题描述-我们需要最小化数组中元素的数量。通过使用跟随删除操作，可以一次删除的元素数为3。如果三个元素满足两个给定条件，则可以删除。

孔1-三个元素应该相邻。

条件2-两个相邻元素之间的差为k，即arr[i+1]=arr[i]+k和arr[i+2]=arr[i+1]+k。

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

输入

{4, 6, 8, 4, 1, 5 }, k = 2

输出结果

解释

对于索引0、1、2，可以执行一次删除操作。

解决方法

解决这个问题有些棘手，因为在完成一个删除操作后，可能会看到间接删除操作。例如，我们在5、6、7处删除元素。在删除之后，新数组可能具有现在满足删除条件的元素3、4、5。可以使用动态编程方法解决具有重叠子问题的此类问题。为此，我们将维护一个DP[]矩阵来存储子问题的结果，以便在以后需要时访问它们，这称为记忆。

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

示例

#include 
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
   if (DP[start][end] != -1)
      return DP[start][end];
   if ( (end-start + 1) < 3)
      return end-start +1;
   int minSize = 1 + calcMinSize(arr, start+1, end, k);
   for (int i = start+1; i<=end-1; i++){
      for (int j = i+1; j <= end; j++ ){
         if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
            2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
            minSize = min(minSize, calcMinSize(arr, j+1, end, k));
         }
      }
   }
   return (DP[start][end] = minSize);
}
int main() {
   int arr[] = {4, 6, 8, 4, 1, 5 };
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   memset(DP, -1, sizeof(DP));
   cout<<"移除后阵列的最小可能大小为 "<输出结果移除后阵列的最小可能大小为 3

返回顶部
3162201930
czq8825@qq.com

使用给定的规则在C ++中查找数组的最小可能大小

输入

解释

解决方法

示例

热门推荐

随机推荐