电子商务网站建设合同标准范文,装修家具,烟台微网站,网站开发w亿玛酷1流量订制474. 一和零
题目链接#xff1a;474. 一和零
题目描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度#xff0c;该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素#xff0c;集合 x 是集合 y 的 子…474. 一和零
题目链接474. 一和零
题目描述
给你一个二进制字符串数组 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 。提示
1 strs.length 6001 strs[i].length 100strs[i] 仅由 0 和 1 组成1 m, n 100
算法分析
之前的背包问题中对于背包的描述只有一种维度那就是背包的容量。
而这道题需要对背包有两种约束维度也就是0和1的个数mn我们可以看成是容量a和容量b。
而每一个字符串我们看作一个物品它有两个属性即0的个数和1的个数。
接下来我们按照动态规划五部曲来。
定义dp数组及下表含义
对于dp[i][j]我们将其定义为容量ab分别为ij的背包最多能装下的物品数量为dp[i][j]。
递推公式
类似于一种维度背包的递推公式dp[j]max(dp[j],dp[j-weigth[i]value[i]);
我们只需要将背包的一维属性变成二维就可以了dp[i][j]max(dp[i][j],dp[i-mNumb][j-nNumb]1);
初始化
dp[0][0]0,容量a,b皆为0的背包所能装下的物品数量为0。
遍历顺序
先遍历物品在遍历背包容量对于背包容量的两种维度可以任意顺序遍历但必须都是倒叙遍历。
打印dp数组
对于这道题dp数组的所表示的含义比较难理解打印出来去推导验证的话也是比较困难的。
代码如下
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m 1][n 1];//dp[m][n]表示0的个数m1的个数为n的集合的元素个数for(int i 0; i strs.length; i) {//遍历每个元素int mNum 0;//记录每个元素种0的个数int nNum 0;//记录每个元素种1的个数for(int j 0; j strs[i].length(); j) {if(strs[i].charAt(j) 0) mNum;else nNum;}//倒叙遍历每个元素中0和1的个数for(int j m; j mNum; j--) {for(int k n; k nNum; k--) {dp[j][k] Math.max(dp[j][k], dp[j - mNum][k - nNum] 1);}}}return dp[m][n];}
}
总结
这道题还是比较难的对于背包的属性需要考虑两个维度0的个数和1的个数不过我们只需要将其看成容量a和容量b就可以了还是01背包的思路。
