Trace
6.6 每日一题
传送门：https://leetcode-cn.com/problems/ones-and-zeroes/
Problem
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路
和01背包类似，每个字符串的0和1的数量为代价，要求选尽可能多的字符串。
预处理：
先用两个$vector$记录每个字符串中0和1的数量。
状态表示：
f[i][j][k]
集合：从前$i$个物品中选，0的数量不超过$j$，1的数量不超过$k$的选法。
属性：选的字符串个数的最大值。
状态转移：
如果第$i$个字符串不可选，即zero[i]>j||one[i]>k，转移方程f[i][j][k]=f[i-1][j][k]；
如果第$i$个字符串可选，即j>=zero[i-1]&&k>=one[i-1]，可以分为两种情况，选和不选。
不选：f[i][j][k]=f[i-1][j][k]
选：f[i][j][k]=f[i-1][j-zero[i]][k-one[i]]+1
取二者中的较大值。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
int f[601][101][101];
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> zero;
vector<int> one;
for(int i=0;i<strs.size();i++){
int z_sum=0;
int o_sum=0;
for(int j=0;j<strs[i].size();j++){
if(strs[i][j]=='0'){
z_sum++;
}
else{
o_sum++;
}
}
zero.push_back(z_sum);
one.push_back(o_sum);
}
for(int i=1;i<=strs.size();i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=n;k++){
f[i][j][k]=f[i-1][j][k];
if(j>=zero[i-1]&&k>=one[i-1]){
f[i][j][k]=max(f[i][j][k], f[i-1][j-zero[i-1]][k-one[i-1]]+1);
}
}
}
}
return f[strs.size()][m][n];
}
};
|
$l$为$strs.size()$，时间复杂度$O(lmn)$，空间复杂度$O(lmn$)，
优化
f[i][j][k]只和f[i-1][j][k]的状态有关，可以将$i$压缩。
每个字符串只有选和不选两种情况，类似01背包，压缩后倒序遍历，保证f[i][j][k]由f[i-1][j][k]推得而不是由f[i][j][k]推得。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
int f[101][101];
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> zero;
vector<int> one;
for(int i=0;i<strs.size();i++){
int z_sum=0;
int o_sum=0;
for(int j=0;j<strs[i].size();j++){
if(strs[i][j]=='0'){
z_sum++;
}
else{
o_sum++;
}
}
zero.push_back(z_sum);
one.push_back(o_sum);
}
for(int i=1;i<=strs.size();i++){
for(int j=m;j>=zero[i-1];j--){
for(int k=n;k>=one[i-1];k--){
f[j][k]=max(f[j][k], f[j-zero[i-1]][k-one[i-1]]+1);
}
}
}
return f[m][n];
}
};
|
