数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过对数组元素应用“+”和“*”运算获得的最小数字
问题陈述
我们给定一个长度为“N”的数组，其中包含一些正整数。我们还给定一个长度为“N-1”的字符串，其中只包含“*”和“+”字符，“*”是乘法运算符，“+”是加法运算符。我们需要以某种方式对数组元素执行算术运算，以便获得最小的正整数。
示例
输入
array = [1,2,3], str = “*+”
输出
5
解释
它是((1*2) + 3)的结果值。
输入
array = [3, 3, 3, 3], str = ‘*++’
输出
15
解释
它执行 array[0]*array[1]，等于 9，并将其称为 result1。然后，它将 array[2] 与 result1 相加，等于 12，并将其称为 result2。接下来，它将 result2 与 array[3] 相加，等于 15。
输入
array = [1, 3, 5, 6], str = “**+”
输出
21
解释
它是((1*3*5) + 6)的结果值。
方法 1
我们将在这种方法中使用位掩码来解决问题。
当我们需要进行两个选择时，我们可以使用位掩码。在这里，我们需要按任意顺序应用算术运算，但我们需要从给定的字符串中选择乘法和算术运算。
因此，位掩码允许我们获得所有可能的排列方式来安排这两个算术运算符。之后，我们可以对每种方式执行算术运算，并检查结果值是否为最小值。
让我们用示例输入来说明上述逻辑。在下面的示例中，array = [1, 3, 5, 6]，str = “*++”。
这里，字符串长度为 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”变量的值并将“*”推入 order 向量；否则，将“+”推入 order 向量。
步骤 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)，因为我们使用列表来存储算术运算符的顺序。
72 次查看
