携手创造，共同成长！这是我参加「日新计划 8 月更文挑战」的第15天，点击查看活动概况
标题
给你一个二进制字符串数组 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 <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 ‘0’ 和 ‘1’ 组成
- 1 <= m, n <= 100
解题思路
根据题意，本题能够转化为 01 背包问题。strs 数组里的元素就是物品，每个物品都是一个！而 m 和 n 适当于是一个背包，两个维度的背包。
第一步，确认dp数组以及下标的含义：
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
第二步，确认递推公式：
dp[i][j] 能够由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就能够是 dp[i – zeroNum][j – oneNum] + 1。然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i – zeroNum][j – oneNum] + 1);
第三步，数组初始化：
01背包的dp数组初始化为0就能够。
第四步，确认遍历次序：
01背包是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
代码实现
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
int oneNum, zeroNum;
for(String str: strs){
oneNum = 0;
zeroNum = 0;
for(char ch : str.toCharArray()){
if (ch == '0'){
zeroNum++;
} else {
oneNum++;
}
}
for(int i = m; i >= zeroNum; i--){
for(int j = n; j >= oneNum; j--){
dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum][j-oneNum] + 1);
}
}
}
return dp[m][n];
}
}
最终
- 时刻复杂度：O(lmn + L)，其间 l 是数组 strs 的长度，m 和 n 分别是 0 和 1 的容量，L 是数组 strs 中的一切字符串的长度之和。
- 空间复杂度：O(mn)，其间 m 和 n 分别是 0 和 1 的容量。
我是杰少，如果您觉的我写的不错，那请给我 点赞+评论+保藏 后再走哦！
往期文章：
- 使用虚幻引擎主动化东西实现主动化部署
- 如安在 UE4 中制作一扇主动敞开的大门
- 如安在 UE4 顶用代码去控制人物移动
- 怎么给 UE4 场景添加游戏人物
- UE4：Android 渠道开发实践攻略
- UE4 开发避坑攻略（继续更新）
- 新年开工啦，放个小焰火庆祝一下
- 聊聊与苹果审核员的爱恨情仇(下)
- 聊聊与苹果审核员的爱恨情仇(上)
- 一名普通东西人的 2021 | 2021年终总结
- 二叉树刷题总结：二叉查找树的特点
- 二叉树总结：二叉树的特点
- 二叉树总结：二叉树的修改与结构
- StoreKit2 有这么香？嗯，我试过了，真香
- 看完这篇文章，再也不怕面试官问我怎么结构二叉树啦！
- 那帮做游戏的又想让大家氪金，太坏了！
- 手把手带你撸一个网易云音乐主页 | 适配篇
- 手把手带你撸一个网易云音乐主页（三）
- 手把手带你撸一个网易云音乐主页（二）
- 手把手带你撸一个网易云音乐主页（一）
- 代码要写注释吗？写你就输了
- Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿
- iOS 高雅的处理网络数据，你真的会吗？不如看看这篇
- UICollectionView 自定义布局！看这篇就够了
请你喝杯 ☕️ 点赞 + 重视哦～
- 阅读完记得给我点个赞哦，有 有动力
- 重视大众号— HelloWorld杰少，第一时刻推送新姿态
最终，创造不易，如果对大家有所协助，期望大家点赞支持，有什么问题也能够在评论区里讨论～**
