数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学从字符串数组中找出包含 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’ 变量初始化为零。
步骤 1.2 - 使用 for 循环遍历字符串。
步骤 1.3 - 如果第 i 个索引处的字符是 ‘0’，则将 ‘cnt’ 的值增加 1。
步骤 1.2 - 返回 ‘cnt’ 变量的值。
步骤 2 - getMaxSubsetLen() 返回整数值，并接受向量 arr、int A、int B 和索引作为参数。
步骤 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() 函数来计算特定二进制字符串中 0 的总数，正如我们在上述方法中所做的那样。
步骤 2 - 创建一个大小为 A x B x N 的三维向量来存储先前状态的结果。在列表中，我们将存储当 0 的总数等于 A 且 1 的总数等于 B 时，索引为 ‘I’ 的子集的长度。将其作为 getMaxSubsetLen() 函数的参数。
步骤 3 - 定义基本情况，如同我们在上述方法中所做的那样。
步骤 4 - 如果 dpTable[A][B][index] 的值大于 0，则表示状态已计算，并返回其值。
步骤 5 - 计算当前字符串中 0 和 1 的总数。
步骤 6 - 包含和排除当前字符串后获取结果值。
步骤 7 - 使用 max() 函数从 first 和 second 中获取最大值，并在将其存储在 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 列表进行动态规划。
89 次浏览
