[LeetCode] 474. Ones and Zeroes

2024-09-06 04:58

文章标签 leetcode 474 zeroes ones

本文主要是介绍[LeetCode] 474. Ones and Zeroes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/ones-and-zeroes/description/

题目

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:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4Explanation: 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:

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

题目大意

有一组字符串 string，给定 m个‘1’，与n个‘0’。选择字符串组，使用的‘1’与‘0’小于 m与n。
求最多有多少个字符串。

思路

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。

状态 dp[i][j][k]：遍历到第 i个物品（字符串），使用 j个’0’ 、 k个’1’时，能包含的最多物品数（字符串数）

状态转移方程：

 if(j-num0>=0 && k-num1>=0)dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-num0][k-num1]+1);elsedp[i][j][k] = dp[i-1][j][k];

初始化
dp[0][j][k] = 0；

class Solution {public int findMaxForm(String[] strs, int m, int n) {int [][][]dp = new int[strs.length+1][m+1][n+1];for(int i = 1;i <= strs.length;i++){int num0 = 0;int num1 = 0;for(int j = 0 ;j<strs[i-1].length();j++){if(strs[i-1].charAt(j)=='0')num0 ++;elsenum1 ++;}for(int j = 0;j<=m;j++)for(int k = 0;k<=n;k++){if(j-num0>=0 && k-num1>=0)dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-num0][k-num1]+1);elsedp[i][j][k] = dp[i-1][j][k];}}return dp[strs.length][m][n];}
}

由于 dp[i][j][k] 只用到了 dp[i-1]，所以可以用二维数组表示 dp。

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(String str:strs){int num0 = 0;int num1 = 0;for(int j = 0;j<str.length();j++){if(str.charAt(j)=='0')num0++;elsenum1++;}for(int j = m;j>=num0;j--)for(int k = n;k>=num1;k--)dp[j][k] = Math.max(dp[j][k],dp[j-num0][k-num1]+1);}return dp[m][n];}
}