474、一和零
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个**仅包含 0 和 1 **字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
- 给定 0 和 1 的数量都不会超过 100。
- 给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
题解
1、暴力递归
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if(strs.length == 0 || (m==0 && n==0)){
return 0;
}
return tryFindMaxForm(strs,strs.length-1,m,n);
}
// 用m，n 拼出 strs[0,i] 的 最大个数
public int tryFindMaxForm(String[] strs,int i,int m, int n){
if(i<0){
return 0;
}
int numsOf0 = 0;
int numsOf1 = 0;
String str = strs[i];
for(int j = 0;j<str.length();j++){
if(str.charAt(j) == '0'){
numsOf0++;
}else{
numsOf1++;
}
}
if(m>=numsOf0&&n>=numsOf1){
return Math.max(tryFindMaxForm(strs,i-1,m,n),
1+tryFindMaxForm(strs,i-1,m-numsOf0,n-numsOf1));
}else{
return tryFindMaxForm(strs,i-1,m,n);
}
}
// 作者：meetce-
// 链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/zi-ding-xiang-xia-ji-yi-sou-suo-zi-di-xiang-shang-/
2、自顶向下——记忆化搜索
class Solution {
private int[][][] memo;
public int findMaxForm(String[] strs, int m, int n) {
if(strs.length == 0 || (m==0 && n==0)){
return 0;
}
this.memo = new int[strs.length][m+1][n+1];
for(int i = 0;i<memo.length;i++){
for(int j=0;j<memo[i].length;j++){
Arrays.fill(memo[i][j],-1);
}
}
return tryFindMaxForm(strs,strs.length-1,m,n);
}
// 用m，n 拼出 strs[0,i] 的 最大个数
public int tryFindMaxForm(String[] strs,int i,int m, int n){
if(i<0){
return 0;
}
// 存在已经求出的解，直接返回
if(memo[i][m][n] != -1){
return memo[i][m][n];
}
int numsOf0 = 0;
int numsOf1 = 0;
String str = strs[i];
for(int j = 0;j<str.length();j++){
if(str.charAt(j) == '0'){
numsOf0++;
}else{
numsOf1++;
}
}
if(m>=numsOf0&&n>=numsOf1){
memo[i][m][n] = Math.max(tryFindMaxForm(strs,i-1,m,n),
1+tryFindMaxForm(strs,i-1,m-numsOf0,n-numsOf1));
}else{
memo[i][m][n] = tryFindMaxForm(strs,i-1,m,n);
}
return memo[i][m][n];
}
}
3、三维动态规划
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if(strs.length == 0 || (m==0 && n==0)){
return 0;
}
// dp[i][j][k] 表示j个0，k个1组成s[0...i]的最大个数，默认0
int[][][] dp = new int[strs.length][m+1][n+1];
for(int i=0;i<strs.length;i++){
int numsOf0 = 0;
int numsOf1 = 0;
String str = strs[i];
for(int j = 0;j<str.length();j++){
if(str.charAt(j) == '0'){
numsOf0++;
}else{
numsOf1++;
}
}
for(int j=m;j>=0;j--){
for(int k=n;k>=0;k--){
if(j>=numsOf0 && k >= numsOf1){
if(i==0){
dp[i][j][k] = 1;
}else{
dp[i][j][k] = Math.max(dp[i-1][j][k],1+dp[i-1][j-numsOf0][k-numsOf1]);
}
}else{
dp[i][j][k] = i>0 ? dp[i-1][j][k] : 0;
}
}
}
}
return dp[strs.length-1][m][n];
}
}
4、二维动态规划
背包问题改装，二维
用 dp(i, j) 表示使用 i 个 0 和 j 个 1，最多能拼出的字符串数目.我们递减i和j以求得最多可表示的字符串数目。
- 代码
// java
class Solution {
public int findMaxForm(String[] strs,int m, int n) {
int[][] dp = new int[m+1][n+1];
for (String s:strs) {
int[] count = countzeroesones(s);
for (int zeroes = m;zeroes >= count[0];zeroes--) {
for (int ones = n;ones >= count[1];ones--) {
dp[zeroes][ones] = Math.max(1+dp[zeroes - count[0]][ones-count[1]],dp[zeroes][ones]);
}
}
}
return dp[m][n];
}
private int[] countzeroesones(String s) {
int[] cnt = new int[2];
for (char ch:s.toCharArray()) {
cnt[ch-'0']++;
}
return cnt;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
