資料結構
網路
關係資料庫管理系統 (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 次瀏覽
