474. Ones and Zeros

发表于 | 分类于

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:

The given numbers of 0s and 1s will both not exceed 100
The size of given string array won't exceed 600.

Example 1:

1
2
3
4
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

1
2
3
4
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

解法1：

这个的解释还算可以,来自于leetcode discuss:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
The idea is to build up the solution for 0..m zeros and 0..n ones, from only knowing 1 string, 2 strings, ..., up to n strings.
For example, for array = {"10", "0", "1"}, m = 1, n = 1.
    for first string "10":
        zero = 0, one = 0
        zero = 1, one = 0
        zero = 0, one = 1
        zero = 1, one = 1, can form "10" [+1]
    continue on the second string "0", with previous knowledge of string "10":
        zero = 0, one = 0
        zero = 1, one = 0, can form "0" [+1]
        zero = 0, one = 1
        zero = 1, one = 1, can form "0" [+1] or 1 string ("10"), known from previous string
    continue on the last string "1", with previous knowledge of strings "10" and "0":
        zero = 0, one = 0
        zero = 1, one = 0, can't form "1", but we know it can form 1 string ("0") from previous set of strings
        zero = 0, one = 1, can form "1" (+1)
        zero = 1, one = 1, (can form "1" and 1 more string ("0") with zero = 1, one = 0, known from previous set of strings) or (1 string ("10"), known from previous set of strings)
Hence, at the end, we know that with zero = 1, one = 1, with string "10", "0", and "1", the maximum number of strings we can form is 2.

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int[] count = count(str);
            for (int i = m; i >= count[0]; i--) {
                for (int j = n; j >= count[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
    private static int[] count(String s) {
	int[] result = new int[2];
	char[] array = s.toCharArray();
	for (int i : array) {
	    result[i - '0']++;
	}
	return result;
    }
}

解法2： 背包解法

此题实际上是一个背包问题，背包问题的本质是：
求一个最大或者最小，给定一定的限定条件。这里的限定条件是有限的0和1。
背包就构建一个n维数组，dp[i][j][k]表示前i个数，用jk两个限定条件所能达到的最大结果。

lang: java
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
37
38
39
40
41
42
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int strn = strs.length;
        int[][][] dp = new int[strn + 1][m + 1][n + 1];
        // dp[l][i][j] means up to first l strings, with m zeros and n ones, the max number of strings it can form
        // do[l][i][j] = Math.max(dp[l - 1][i - zero[l]][j - zero[l][i - ones]] + 1, dp[l - 1][i][j]）；
        for (int l = 1; l <= strn; l++) {
            int[] current = count(strs[l - 1]);   // count current number of zeros and ones
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (i >= current[0] && j >= current[1]) {
                        dp[l][i][j] = Math.max(dp[l][i][j], dp[l - 1][i - current[0]][j - current[1]] + 1);
                    }
                    dp[l][i][j] = Math.max(dp[l][i][j], dp[l - 1][i][j]);
                }
            }
        }
        return dp[strn][m][n];
    }
    private int[] count(String str) {
        // count number of ones and zeros in the string
        int[] res = new int[2];
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                res[0]++;
            } else {
                res[1]++;
            }
        }
        return res;
    }
}