透過對數組元素應用“+”和“*”操作可以得到的最小數字

問題陳述

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