474. Ones and Zeroes

474. Ones and Zeroes

Question

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Solution 1

0-1背包问题的升级版。经典的背包问题只有一种容量,而这个问题实际等于有两种容量。

经典背包问题需要用二维数组动态规划,分别为物品和容量。
而这道题需要用三维数组动态规划,分别为字符串,0的容量和1的容量。

我们采用一个三维数组dp[i][j][k]保存可取最多物品的数量
对于每个物品i,我们都可以取(数量+1)或不取(保持上一个物品的状态)。
j和k相当于分别记录了取“0”的总数和“1”的总数

遍历三个维度,并计算字符串中0和1的个数。

  • 如果当总容量大于当前物品中zeros和ones的数量,则可以取当前的物品

    • 如果取当前的物品,则dp[]数组的总数等于上一个物品的状态加一,即dp[i-1][j-zeros][k-ones]。
    • 也可以不取当前的物品,则dp[]数组的总数直接保持上一个物品的状态
  • 如果当前背包总容量小于zeros和ones的数量,则不能取当前物品。

    • 数组dp[]保持上一个物品的状态

时间复杂度:O(lmn + L),L是数组中所有字符串长度之和。
空间复杂度:O(lmn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][][] dp = new int[strs.length+1][m+1][n+1];

for(int i = 1; i <= strs.length; i++){
int zeros = 0, ones = 0;
for(char c : strs[i-1].toCharArray()){
if(c == '0') zeros++;
else ones++;
}

for(int j = 0; j <= m; j++){
for(int k = 0; k <= n; k++){
if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
else dp[i][j][k] = dp[i-1][j][k];
}
}
}
return dp[strs.length][m][n];
}
}

Solution 2

由于dp[i][][]的上一个状态只涉及到dp[i-1][][],因此我们可以采用滚动数组,去掉数组的一个维度,压缩空间。
此时需要从m到zeros,从n到ones倒序遍历,保证dp[i][][]转移过来的是dp[i-1][][]的元素。

此时的空间复杂度降低为O(mn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];

for(String s : strs){ //记录每个位置对应的0和1数量
int zeros = 0, ones = 0;
for(char c : s.toCharArray()){
if(c == '0') zeros++;
else ones++;
}

for(int i = m; i >= zeros; i--){
for(int j = n; j >= ones; j--){
dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
}
}
}
return dp[m][n];
}
}

Solution 3

递归+记忆化搜索,保存并返回每个位置的最大长度。
如果位置越界则返回0。
如果memo[i][zero][one]不为0,则返回memo[i][zero][one]。

如果当前字符串的“0”和“1”的个数大于剩余的“0”和“1”的个数,则可以取当前字符串,递归下一个位置并加一。
也可以不取当前的字符串,递归下一个位置。当前位置memo[i][zero][one]等于两者中的最大值。

否则无法取当前字符串,直接递归下一个位置。当前位置等于0。

Code

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
class Solution {
String[] s;
int[] zeros, ones;
int[][][] memo;
public int findMaxForm(String[] strs, int m, int n) {
s = strs;
zeros = new int[strs.length];
ones = new int[strs.length];
memo = new int[strs.length][m+1][n+1];

for(int i = 0; i < strs.length; i++){ //记录每个位置对应的0和1数量
for(int j = 0; j < strs[i].length(); j++){
if(s[i].charAt(j) == '0') zeros[i]++;
else ones[i]++;
}
}
return dfs(0, m, n);
}

private int dfs(int i, int zero, int one){
if(i >= s.length){
return 0;
}
if(memo[i][zero][one] != 0) return memo[i][zero][one];

int maxPossibleSubset = 0;

if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
}
memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
return memo[i][zero][one];

}
}
Author

Xander

Posted on

2022-05-23

Updated on

2022-05-23

Licensed under

Comments