474. Ones and Zeroes

474. Ones and Zeroesopen in new window

🟠 🔖 数组 字符串 动态规划 🔗 LeetCodeopen in new window

题目

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

Return _the size of the largest subset ofstrs 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.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] consists only of digits '0' and '1'.
1 <= m, n <= 100

题目大意

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

解题思路

思路一：动态规划

这个问题可以使用动态规划来解决，与 0-1 背包问题有一些相似之处。

可以定义一个三维动态规划数组 dp，其中 dp[i][j][k] 表示在前 i 个字符串中使用 j 个 '0' 和 k 个 '1' 的条件下，最大子集的长度。

动态规划的状态转移方程如下：

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1)

其中，zeros 表示第 i 个字符串中 '0' 的个数，ones 表示第 i 个字符串中 '1' 的个数。

接下来，遍历每个字符串，更新动态规划数组，最后返回 dp[len][m][n]，表示使用最多 m 个 '0' 和 n 个 '1' 条件下得到的最大字符串数目。

这个解法的时间复杂度和空间复杂度都是 O(len * m * n)，其中 len 是字符串数组的长度。

思路二：压缩状态的动态规划

注意到 dp[i][j][k] 都是通过上一行 dp[i-1][..][..] 转移过来的，再之前所有行的数据都不会再使用了。所以，我们可以对动态规划进行状态压缩，将三维 dp 数组压缩为二维，节约空间复杂度：

dp[j][k] 表示在当前元素中，使用 j 个 '0' 和 k 个 '1' 的条件下，最大子集的长度；
遍历 strs 数组中的每个字符串 str，并更新 dp 数组。需要注意的是 j 和 k 应该从后往前反向遍历，确保了我们在更新当前状态时所依赖的状态已经被正确计算；
状态转移方程：dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1)；
最终结果存储在 dp[m][n] 中；

这个解法的时间复杂度是 O(len * m * n)，其中 len 是字符串数组的长度，空间复杂度是 O(m * n)。

代码

动态规划

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
	const len = strs.length;
	const dp = new Array(len + 1)
		.fill(0)
		.map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)));

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

压缩状态的动态规划

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
	const len = strs.length;
	const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
	for (let str of strs) {
		const zeros = [...str].filter((i) => i == '0').length;
		const ones = str.length - zeros;

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

474. Ones and Zeroes

# 474. Ones and Zeroesopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：动态规划

# 思路二：压缩状态的动态规划

# 代码

# 相关题目

474. Ones and Zeroesopen in new window

题目

题目大意

解题思路

思路一：动态规划

思路二：压缩状态的动态规划

代码

相关题目