C++ 从字符串数组中找到由A个0和B个1组成的最长子集的长度

在这个问题中，我们需要找到包含最多A个0和B个1的最长子集。我们所需要做的就是使用数组元素找到所有可能的子集，并找到包含最多A个0和B个1的最长子集。

在本教程中，首先我们将学习使用递归方法解决这个问题。然后，我们将使用动态规划方法优化代码。

问题描述 − 我们得到一个包含N个二进制字符串的数组。同时，我们给出了整数A和B。我们需要使用给定的二进制字符串创建最长的子集，使其不超过A个0和B个1。

示例

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()函数来计算给定二进制字符串中的0的总数。

• 步骤1.1 − 将’count’变量初始化为0。

• 步骤1.2 − 使用for循环遍历字符串。

• 步骤1.3 − 如果第i个索引处的字符是’0’，则将’cnt’的值增加1。

• 步骤1.4 − 返回’cnt’变量的值。

• 步骤2 − getMaxSubsetLen()返回整数值，并且带有vector arr、int A、int B和index作为参数。

• 步骤3 − 在函数内部定义基本情况。如果索引等于向量的大小，或者A和B的值都为零，则返回0。

• 步骤4 − 现在，计算索引处字符串中0的总数。

• 步骤5 − 从字符串长度中减去1的总数，以找到1的总数。

• 步骤6 − 将’first’变量初始化为0。

• 步骤7 − 如果0和1的总数都小于A和B，则包括当前的二进制字符串。存储1加上对函数的递归调用的返回值。在进行递归调用时，从A和B中减去0和1。

• 步骤8 − 排除当前的字符串，并将结果值存储在’second’变量中。

• 步骤9 − 返回first和second中的最大值。

示例

#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的三维向量，用于存储前一个状态的结果。在列表中，我们将在索引’I’处存储当总零等于A且1个等于B时的子集长度。同时，将其作为getMaxSubsetLen()函数的参数传递。

• 步骤3 - 定义基本情况，就像我们在上述方法中所做的那样。

• 步骤4 - 如果dpTable[A][B][index]的值大于0，则意味着状态已经计算过，返回其值。

• 步骤5 - 计算当前字符串中零和一的总数。

• 步骤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)，因为我们需要填充一个三维列表来获取结果。

空间复杂度 – O(A*B*N)，因为我们在动态规划方法中使用了三维列表。