问题陈述
我们给出了一个长度为“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”变量并将其初始化为零，以存储字符串中乘法算术运算符的总数。
PageAdmin企业网站管理系统4.0.25下载PageAdmin企业网站管理系统V4.0，基于微软最新的MVC框架全新开发，强大的后台管理功能，良好的用户操作体验，可热插拔的插件功能让扩展更加灵活和开放，全部信息表采用自定义表单，可任意自定义扩展字段，支持一对一，一对多的表映射.....各种简单到复杂的网站都可以轻松应付。 PageAdmin V4.0.25更新日志： 1、重写子栏目功能，解决之前版本子栏目数据可能重复的问题 2
步骤 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”变量中获取最小值。
示例
#includeusing 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 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 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)，因为我们使用列表来存储算术运算符的顺序。
