我們給了一個長度為「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中文網其他相關文章！
