資料結構
網路
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 次檢視
