当前位置： 正文

使用reduce操作的金字塔形式（先升后降）连续数组

03-19 面试题/算法&算力分析 274

本文概述

我们连续排列了N块(其中N> 2)个不同高度的石头。任务是从给定的石头阵列中制成金字塔。在金字塔中, 宝石的高度从1开始, 增加1, 直到达到某个值x, 然后减小1, 直到再次达到1, 即宝石应为1, 2, 3, 4…x – 1, x , x – 1, x – 2…1.除金字塔外的所有其他石头的高度都应为0。我们不能将任何石头从其当前位置移开, 但是, 通过支付1的费用, 我们可以减少石头的高度。我们希望将建造金字塔的成本降至最低。输出建造该金字塔的最低成本。

例子：

Input  : 1 2 3 4 2 1
Output : 4
The best pyramid that can be formed in this case is: 
1 2 3 2 1 0
The cost is thus:
(4 - 2) + (2 - 1) + (1 - 0) = 4

Input  : 1 5 2
Output : 4
We make a pyramid 1 2 1

Input  : 1 2 1
Output : 0
We already have a pyramid, we do not need to do any 
further construction.

通过使用简单的逻辑, 我们可以证明建造成本最低的金字塔将是最大高度的金字塔。同样, 两个高度相同的庙宇的建造成本也相同。

可以显示如下：

假设将所有石头拆除到0高度的成本为x。

假设将高度为h的太阳穴拆除为高度0的成本为y。

然后, 如果有可能用给定的石头建造一个高度为h的太阳穴, 其成本将为x – y。

通过使用此方法, 我们可以将方法简化为两个主要步骤：

1.确定可以形成的最大高度的金字塔。

2.计算建造此类金字塔的成本。

假设我们知道金字塔的放置位置, 那么第二步可以以O(N)时间复杂度完成。

因此, 我们的重点应该放在降低步骤1的时间复杂度上。

天真的方法

对于数组中的每个位置, 我们可以假定金字塔从该点开始。然后, 我们发现从1开始构造最大高度的庙宇的成本, 直到不可能达到更高的高度为止, 也就是说, 假设高度为1的金字塔最大, 然后假设高度为2, 依此类推。然后从所有这些成本中选择最低成本。

该方法使用时间复杂度为O(N ^ 3)。

改进方法

对于每个位置, 假设它是太阳穴的中心。移至该点的左右, 并尝试找到寺庙的最大高度。

这可以通过将位置i处的镜腿的最大高度设置为H(i)来实现, 其中H(i)是该点上的石头的高度。然后, 我们向左移动。如果此时石材的高度小于H(i)– 1, 则我们将最大高度设置为H(i – 1)+1。这样, 我们确定每个位置的最大高度。

该方法使用时间复杂度为O(N ^ 2)。

动态规划方法

通过稍微修改上述算法, 我们可以尝试获得O(N)方法。从左侧开始, 然后向右移动, 找到可以在该位置创建的最大高度金字塔。假设该位置右侧数组的一部分是左侧的镜像。如果H(i)是位置i处石头的高度, 则maxHeight(i)= Minimum(H(i), i, maxHeight(i – 1))

可以解释如下：

最大可能的高度不能超过H(i), 因为我们只能减小石头的高度, 而不能增加。

最大可能的高度不能超过i, 因为金字塔必须从高度1开始。

最大可能的高度不能超过石头之前的最大可能高度– 1, 因为每步石头必须增加1。

我们计算从右到左的相似值。然后, 我们为每个位置取这些值中的最小值。然后, 通过确定最大值, 我们可以计算出构建金字塔的最小成本。

C ++

//Program to find minimum cost for pyramid
//from given array
#include <iostream>
using namespace std;
  
#define ull unsigned long long
  
//Returns minimum cost to form a pyramid
ull minPyramidCost(ull arr[], ull N)
{
     //Store the maximum possible pyramid height
     ull *left = new ull[N];
     ull *right = new ull[N];
  
     //Maximum height at start is 1
     left[0] = min(arr[0], (ull)1);
  
     //For each position calculate maximum height
     for ( int i = 1; i <N; ++i)
         left[i] = min(arr[i], min(left[i - 1] + 1, (ull)i + 1));
  
     //Maximum height at end is 1
     right[N - 1] = min(arr[N - 1], (ull)1);
  
     //For each position calculate maximum height
     for ( int i = N - 2; i>= 0; --i)
         right[i] = min(arr[i], min(right[i + 1] + 1, N - i));
  
     //Find minimum possible among calculated values
     ull tot[N];
     for ( int i = 0; i <N; ++i)
         tot[i] = min(right[i], left[i]);
  
     //Find maximum height of pyramid
     ull max_ind = 0;
     for ( int i = 0; i <N; ++i)
         if (tot[i]> tot[max_ind])
             max_ind = i;
  
     //Calculate cost of this pyramid
     ull cost = 0;
     ull height = tot[max_ind];
  
     //Calculate cost of left half
     for ( int x = max_ind; x>= 0; --x)
     {
         cost += arr[x] - height;
         if (height> 0)
             --height;
     }
  
     //Calculate cost of right half
     height = tot[max_ind] - 1;
     for ( int x = max_ind + 1; x <N; ++x)
     {
         cost += arr[x] - height;
         if (height> 0)
             --height;
     }
     return cost;
}
  
//Driver code
int main()
{
     ull arr[] = {1, 2, 3, 4, 2, 1};
     ull N = sizeof (arr)/sizeof (arr[0]);
     cout <<minPyramidCost(arr, N);
     return 0;
}

Java

//Java program to find minimum cost for 
//pyramid from given array
import java.util.*;
  
class GFG{
  
//Returns minimum cost to form a pyramid
static int minPyramidCost( int arr[], int N)
{
      
     //Store the maximum possible pyramid height
     int left[] = new int [N];
     int right[] = new int [N];
  
     //Maximum height at start is 1
     left[ 0 ] = Math.min(arr[ 0 ], 1 );
  
     //For each position calculate maximum height
     for ( int i = 1 ; i <N; ++i)
         left[i] = Math.min(arr[i], Math.min(left[i - 1 ] + 1 , i + 1 ));
                                           
     //Maximum height at end is 1
     right[N - 1 ] = Math.min(arr[N - 1 ], 1 );
  
     //For each position calculate maximum height
     for ( int i = N - 2 ; i>= 0 ; --i)
         right[i] = Math.min(arr[i], Math.min(right[i + 1 ] + 1 , N - i));
                                             
     //Find minimum possible among
     //calculated values
     int tot[] = new int [N];
     for ( int i = 0 ; i <N; ++i)
         tot[i] = Math.min(right[i], left[i]);
  
     //Find maximum height of pyramid
     int max_ind = 0 ;
     for ( int i = 0 ; i <N; ++i)
         if (tot[i]> tot[max_ind])
             max_ind = i;
  
     //Calculate cost of this pyramid
     int cost = 0 ;
     int height = tot[max_ind];
  
     //Calculate cost of left half
     for ( int x = max_ind; x>= 0 ; --x)
     {
         cost += arr[x] - height;
         if (height> 0 )
             --height;
     }
  
     //Calculate cost of right half
     height = tot[max_ind] - 1 ;
     for ( int x = max_ind + 1 ; x <N; ++x) 
     {
         cost += arr[x] - height;
         if (height> 0 )
             --height;
     }
     return cost;
}
  
//Driver code
public static void main(String[] args)
{
     int arr[] = { 1 , 2 , 3 , 4 , 2 , 1 };
     int N = arr.length;
      
     System.out.print(minPyramidCost(arr, N));
}
}
  
//This code is contributed by chitranayal

Python3

# Program to find minimum cost for pyramid
# from given array
  
# Returns minimum cost to form a pyramid
def minPyramidCost(arr: list , N):
  
     # Store the maximum possible pyramid height
     left = [ 0 ] * N
     right = [ 0 ] * N
  
     # Maximum height at start is 1
     left[ 0 ] = min (arr[ 0 ], 1 )
  
     # For each position calculate maximum height
     for i in range ( 1 , N):
         left[i] = min (arr[i], min (left[i - 1 ] + 1 , i + 1 ))
  
     # Maximum height at end is 1
     right[N - 1 ] = min (arr[N - 1 ], 1 )
  
     # For each position calculate maximum height
     for i in range (N - 2 , - 1 , - 1 ):
         right[i] = min (arr[i], min (right[i + 1 ] + 1 , N - i))
  
     # Find minimum possible among calculated values
     tot = [ 0 ] * N
     for i in range (N):
         tot[i] = min (right[i], left[i])
  
     # Find maximum height of pyramid
     max_ind = 0
     for i in range (N):
         if tot[i]> tot[max_ind]:
             max_ind = i
  
     # Calculate cost of this pyramid
     cost = 0
     height = tot[max_ind]
  
     # Calculate cost of left half
     for x in range (max_ind, - 1 , - 1 ):
         cost + = arr[x] - height
         if height> 0 :
             height - = 1
  
     # Calculate cost of right half
     height = tot[max_ind] - 1
     for x in range (max_ind + 1 , N):
         cost + = arr[x] - height
         if height> 0 :
             height - = 1
  
     return cost
  
# Driver Code
if __name__ = = "__main__" :
     arr = [ 1 , 2 , 3 , 4 , 2 , 1 ]
     N = len (arr)
     print (minPyramidCost(arr, N))
  
# This code is contributed by
# sanjeev2552

输出如下：

4

这种方法运行时间为O(N)。

微信公众号
手机浏览(小程序)
0
分享到：

猜你喜欢

用php找出字符串中连续重复次数最多的字符，你有方法吗？
面试题/算法&算力分析

05-06 2127
php编写函数取得上一月的最后一天
面试题/算法&算力分析

04-11 1173
php自定义错误处理器
面试题/算法&算力分析

04-11 749
PHP错误级别错误类型
面试题/算法&算力分析

04-11 775
php去掉字段文本的所有html标签
面试题/算法&算力分析

04-11 747
php写出一个正则表达式，过虑网页上的所有JS/VBS脚本（即把script标记及其内容都去掉）
面试题/算法&算力分析

04-11 728
没有账号？ 忘记密码？