首页  >  文章  >  后端开发  >  通过对数组元素应用“+”和“*”操作可以得到的最小数字

通过对数组元素应用“+”和“*”操作可以得到的最小数字

WBOY
WBOY转载
2023-08-31 20:57:06727浏览

通过对数组元素应用“+”和“*”操作可以得到的最小数字

问题陈述

我们给出了一个长度为“N”的数组,其中包含一些正整数。另外,我们给出了长度为“N-1”的字符串,仅包含“*”和“+”字符,其中“*”是乘法运算符,“+”是加法运算符。我们要求对数组元素进行算术运算,以获得最小的正整数值。

示例

输入

array = [1,2,3], str = “*+”

输出

5

说明

它是 ((1*2) + 3) 的结果值。

输入

array = [3, 3, 3, 3], str = ‘*++’

输出

15

说明

它执行 array[0]*array[1],等于 9,并表示结果 1。之后,它将 result1 与 array[2] 相加,等于 12,并表示为 result2。接下来,它将 result2 添加到数组 [3],等于 15。

输入

array =  [1, 3, 5, 6], str = “**+”

输出

21

说明

它是 ((1*3*5) + 6) 的结果值。

方法一

我们将使用位掩码来解决此方法中的问题。

每当我们有两个选择时,我们就可以使用位掩码。在这里,我们要求以任意顺序应用算术运算,但我们需要在给定字符串的乘法和算术运算之间进行选择

因此,位掩码使我们能够获得所有可能的方式来排列两个算术运算符。之后,我们可以对每路进行算术运算,并检查结果是否为最小值。

让我们通过示例输入来清楚上述逻辑。在下面的示例中,数组 = [1. 3, 5, 6],字符串 = “*++”。

这里,字符串长度为3。因此,我们总共可以有8(2^3)个位掩码,分别是000, 001, 010, 100, 110, 101, 011, 111。

现在,如果我们假设“1”为“*”,“0”为“+”运算符,我们就可以得到字符串中给出的算术运算符的所有排列。

然而,只有当“1”的总数等于“*”运算符的数量,并且“0”的数量等于“+”运算符的数量时,我们才应该使用任何排列。

算法

用户应按照以下算法来实现上述方法。

  • 步骤 1 - 定义“totalMul”变量并将其初始化为零,以存储字符串中乘法算术运算符的总数。

  • 步骤 2 - 使用 for 循环迭代给定的字符串。如果当前字符等于“*”,则将“totalMul”变量的值增加 1。

  • 步骤 3 - 使用for循环获取X等于字符串长度时的所有可能位掩码。这里,'len'是数组长度,'len - 1'是字符串长度。

  • 步骤 4 - 定义“setBitCount”变量来存储当前掩码中设置的位数。另外,定义“order”列表来存储算术运算的当前顺序。

  • 步骤 5 - 在 for 循环中,使用另一个 for 循环来获取当前掩码中设置位的总数 (‘1’)。左移1位j,与I进行&运算,判断第j位是否置位。

  • 步骤 6 - 如果当前位是设置位,则增加“setBitCount”变量的值并将“*”推入顺序向量中;否则,将“+”推入顺序向量中。

  • 第7步 - 如果setBitCount的值等于totalMul的值相同,则意味着我们可以使用当前掩码来安排算术运算;否则,我们将进入下一次迭代。

  • 第 8 步 - 在 if 语句中,使用“deque”数据结构定义“currentQueue”来存储数组元素。

  • 步骤 9 - 遍历 'order' 列表。如果当前字符是 '*',则弹出队列中的最后一个元素,并将其与当前数组索引处的元素相乘。

  • 第 10 步 - 如果“orders”列表中的当前字符为“+”,则将当前数组元素推送到“currentQueue”中。

  • 第 11 步 - 使用 while 循环从“currentQueue”中弹出所有元素并对所有元素求和。

  • 第 12 步 - 使用 min() 函数从“minimum”和“sum”变量中获取最小值。

示例

#include <bits/stdc++.h>
using namespace std;

// Function to get the minimum number by applying mathematical operations in any order.
int getMinimumSum(int array[], int len, string str){
   // to store a total number of multiplication operators in the string.
   int totalMul = 0;
   for (int i = 0; i < (int)str.size(); i++){
      // increment totalMul if the current character is '*'
      if (str[i] == '*')
         totalMul += 1;
      }
   // store maximum number value in the result.
   int minimum = 1000000;
   // Iterate over all the possible masks and find the minimum value by applying arithmetic operations.
   for (int i = 0; i < (1 << (len - 1)); i++){
      // to store the number of bits set in the mask.
      int setBitCount = 0;
      // to store the order of the operators.
      vector<char> order;
      // finding a total number of mask bits in the current mask 'i'. If the current bit is set to bit, push '*' in the order vector; else, push '+'.
      for (int j = 0; j < len - 1; j++){
         if ((1 << j) & (i)){
            setBitCount += 1;
            order.push_back('*');
         } else {
            order.push_back('+');
         }
      }
      // if the set bit count is equal to the total number of multiplication operators, then only apply the operations.
      if (setBitCount == totalMul){
         // queue to store the current elements.
         deque<int> currentQueue;
         // push the first element in the queue.
         currentQueue.push_back(array[0]);
         for (int j = 0; j < len - 1; j++) {
            // get the current operator from the order vector.
            if (order[j] == '*'){
               // if the current operator is '*', multiply the last element in the queue with the next element in the array.
               int temp = currentQueue.back();
               currentQueue.pop_back();
               temp = temp * array[j + 1];
               // push a new value
               currentQueue.push_back(temp);
            } else {
               // if current operator is '+', then push the next element in the array in the queue.
               currentQueue.push_back(array[j + 1]);
            }
         }
         int sum = 0;
         // Add all the elements in the queue.
         while (currentQueue.size() > 0){
            int temp = currentQueue.front();
            sum += temp;
            currentQueue.pop_front();
         }
         // get the minimum value.
         minimum = min(minimum, sum);
      }
   }
   return minimum;
}

int main(){
   int array[] = {1, 3, 5, 6};
   string str = "*++";
   int len = sizeof(array) / sizeof(array[0]);
   cout << "Minimum number value can be achieved is : " << getMinimumSum(array, len, str);
   return 0;
}

输出

Minimum number value can be achieved is : 14
  • 时间复杂度 - O(2N-1*N),其中 N 是数组的长度。当我们迭代所有位掩码时,在其中,我们使用 for 循环来计算当前掩码中设置位的总数,它是 O(2N-1*N)。

  • 空间复杂度 − O(N),因为我们使用列表来存储算术运算符的顺序。

以上是通过对数组元素应用“+”和“*”操作可以得到的最小数字的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除