從一個字串陣列中找出由A個0和B個1組成的最長子集的長度

在這個問題中，我們需要找到最多包含A個0和B1的最長子集。我們需要做的就是使用陣列元素找到所有可能的子集，並找到包含最多 A 0 和 B1 的最長子集。

在本教程中，首先，我們將學習遞歸方法來解決問題。之後，我們將使用動態規劃的方法來最佳化程式碼。

問題陳述 - 我們給了一個包含 N 個二進位字串的陣列。此外，我們也給出了 A 和 B 整數。我們需要使用給定的二進位字串來建立最長的子集，使其不包含超過 A 0 和 B1。

範例

Input –  arr = {"101", "0", "101", "0", "1"}, A = 2, B = 1

Output – 3

說明

最長的子集是{ "0", "0", "1"}，包含2個0和1個1。

Input –  arr = {"0", "101", "0", "1"}, A = 3, B = 3

Output – 3

說明

最長的子集是{"0", "101", "0", "1"}，3個0和3個1。

方法 1

在本節中，我們將學習一種使用遞歸的簡單方法。我們將使用陣列元素來建構所有可能的子集，並找到包含 A 0 和 B 1 的最長子集。

演算法

• 步驟 1 - 定義 countZeros() 函數來計算給定二進位字串中零的總數。

• 步驟 1.1 - 將「count」變數初始化為零。

• 步驟 1.2 - 使用 for 迴圈遍歷字串。

• 步驟 1.3 - 如果第 i 個索引處的字元為“0”，則將“cnt”的值增加 1。

• 步驟 1.2 - 傳回「cnt」變數的值。

• 步驟 2 - getMaxSubsetLen() 傳回整數值並採用向量 arr、int A、int B 和索引作為參數。

• 步驟 3 - 定義函數內的基本情況。如果索引等於向量的大小，或 A 和 B 的值都為零，則傳回 0。

• 第 4 步 - 現在，計算索引處字串中零的總數。

• 第 5 步 - 從字串長度中減去 1 的總數，即可得出 1 的總數。

• 第 6 步 - 將「第一個」變數初始化為 0。

• 步驟 7 - 如果 0 和 1 的總數分別小於 A 和 B，則包含目前的二進位字串。儲存 1 函數遞歸呼叫的返回值。在進行遞歸呼叫時，從 A 和 B 減去 0 和 1。

• 第 8 步 - 排除目前字串並將結果值儲存在「第二個」變數中。

• 第 9 步 - 傳回第一個和第二個的最大值。

範例

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> arr, int A, int B, int index){

   // base case
   // if all the strings are traversed, or A + B becomes 0
   if (index == arr.size() || A + B == 0){
      return 0;
   }
   
   // total number of 0's in arr[index] string
   int zero = countZeros(arr[index]);
   
   // total number of 1's in arr[index] string
   int one = arr[index].size() - zero;
   
   // Stores the length of the subset, if arr[i] is included.
   int first = 0;
   
   // if the number of 0's and 1's in arr[index] is less than or equal to A and B, respectively, then include the string
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(arr, A - zero, B - one, index + 1);
   }
   
   // Stores the length of the subset, if arr[i] is not included.
   int second = getMaxSubsetLen(arr, A, B, index + 1);
   
   // return the maximum of the first and second
   return max(first, second);
}

// Driver Code
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " <<getMaxSubsetLen(arr, A, B, 0);
   return 0;
}

輸出

The maximum length of the subset consisting at most A 0s and B 1s is - 3

時間複雜度 - O(2N)，因為我們使用 N 個陣列元素來找到所有可能的子集。

空間複雜度 - O(1)

方法2

我們在本節中對上述方法進行了最佳化。我們使用動態規劃的方法來解決這個問題。它儲存前一個狀態的結果，以降低問題的時間複雜度。

演算法

• 第 1 步 - 定義 countZeros() 函數來計算特定二進位字串中零的總數，就像我們在上述方法中所做的那樣。

• 步驟 2 - 建立一個大小為 A x B x N 的 3 維向量來儲存先前狀態的結果。在清單中，當總 0 等於 A 且 1 等於 B 時，我們將在索引「I」處儲存子集的長度。此外，將其作為 getMaxSubsetLen() 函數的參數傳遞。

• 第 3 步 - 按照我們在上述方法中所做的定義基本情況。

• 步驟 4 - 如果 dpTable[A][B][index] 的值大於 0，則表示狀態已計算並傳回其值。

• 第 5 步 - 計算目前字串中 0 和 1 的總數。

• 第 6 步 - 取得包含和排除目前字串後的結果值。

• 第7 步驟 - 使用max() 函數取得第一個和第二個的最大值，並將其儲存在dpTable[A][B][index] 中後返回

範例

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> array, int A, int B, int index, vector<vector<vector<int>>> &dpTable){

   // base case
   if (index == array.size() || A + B == 0){
      return 0;
   }
   
   // return if already calculated
   if (dpTable[A][B][index] > 0){
      return dpTable[A][B][index];
   }
   
   // total number of 0's in the current string
   int zero = countZeros(array[index]);
   
   // total number of 1's in the current string
   int one = array[index].size() - zero;
   
   // to store the length of the subset can be formed by including the current string
   int first = 0;
   
   // if the total number of 0's and 1's in the current string is less than or equal to A and B, respectively
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(array, A - zero, B - one, index + 1, dpTable);
   }
   
   // to store the length of the subset can be formed by excluding the current string
   int second = getMaxSubsetLen(array, A, B, index + 1, dpTable);
   
   // store the maximum of the first and second, and return
   return dpTable[A][B][index] = max(first, second);
}
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   vector<vector<vector<int>>> dpTable(A + 1, vector<vector<int>>(B + 1, vector<int>(arr.size() + 1, 0)));
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " << getMaxSubsetLen(arr, A, B, 0, dpTable);
   return 0;
}

輸出

The maximum length of the subset consisting at most A 0s and B 1s is - 3

時間複雜度 - O(A*B*N)，因為我們需要填入 3D 清單才能得到結果。

空間複雜度 - O(A*B*N)，因為我們使用 3D 清單進行動態規劃方法。

以上是從一個字串陣列中找出由A個0和B個1組成的最長子集的長度的詳細內容。更多資訊請關注PHP中文網其他相關文章！