所有的LeetCode題解索引，可以看這篇文章——【算法和數(shù)據(jù)結(jié)構(gòu)】LeetCode題解。
一、題目
二、解法
??思路分析：本題要找strs數(shù)組的最大子集，這個子集最多含有
m
m
m個0和
n
n
n個1。本題也可以抽象成一個01背包的問題。其中，strs內(nèi)的元素就是物品，而
m
m
m和
n
n
n就是背包的維度。
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表最多有i個0和j個1的strs的最大子集的大小。遞歸數(shù)組可以由
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
?
z
e
r
o
N
u
m
]
[
j
?
o
n
e
N
u
m
]
+
1
)
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
dp[i][j]=max(dp[i][j],dp[i?zeroNum][j?oneNum]+1)得出。和文章【算法與數(shù)據(jù)結(jié)構(gòu)】算法與數(shù)據(jù)結(jié)構(gòu)知識點中的01背包滾動數(shù)組一樣，循環(huán)需要從后往前進行，否則會將strs重復(fù)計算。
??程序如下：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 默認(rèn)初始化為0
for (string str : strs) { // 遍歷物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
復(fù)雜度分析：文章來源：http://www.zghlxwxcb.cn/news/detail-814523.html
- 時間復(fù)雜度： O ( K ? m ? n ) O(K*m*n) O(K?m?n)，K為strs的長度。
- 空間復(fù)雜度： O ( m ? n ) O(m*n) O(m?n)。
三、完整代碼
# include <iostream>
# include <vector>
# include <string>
using namespace std;
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 默認(rèn)初始化為0
for (string str : strs) { // 遍歷物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
int main() {
Solution s1;
vector<string> strs = { "10", "0001", "111001", "1", "0" };
int m = 5;
int n = 3;
int result = s1.findMaxForm(strs, m, n);
cout << result << endl;
system("pause");
return 0;
}
end文章來源地址http://www.zghlxwxcb.cn/news/detail-814523.html
到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】474、LeetCode一和零的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
