474. 一和零——【Leetcode每日刷题】

桃扇骨 2024-03-25 13:02 69阅读 0赞

### 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 <= 600
 *  1 <= strs\[i\].length <= 100
 *  strs\[i\] 仅由 ‘0’ 和 ‘1’ 组成
 *  1 <= m, n <= 100

#### 思路：(动态规划) ####

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

#### 代码：(Java) ####

public class FindMaxForm {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String[] strs = {
        "10", "0001", "111001", "1", "0"};
    		int m = 5, n = 3;
    		System.out.println(findMaxForm(strs, m, n));
    	}
    	public static int findMaxForm(String[] strs, int m, int n) {
        
    		
    		int[][] dp = new int[m + 1][n+ 1];
    		int m_0, n_1;
    		
    		for(String str : strs) {
        
    			m_0 = numM(str);
    			n_1 = str.length() - m_0;
    			
    			if(m_0 > m || n_1 > n) {
        
    				continue;
    			}
    			
    			for(int i = m; i >= m_0; i--) {
        
    				for(int j = n; j >= n_1; j--) {
        
    					dp[i][j] = Math.max(dp[i][j], dp[i - m_0][j - n_1] + 1);
    				}
    			}
    			
    		}
    		return dp[m][n];
    
        }
    	private static int numM(String str) {
        
    		// TODO Auto-generated method stub
    		int num = 0;
    		for(int i = 0; i < str.length(); i++) {
        
    			if(str.charAt(i) == '0') {
        
    				num++;
    			}
    		}
    		return num;
    	}
    }

##### 运行结果：![在这里插入图片描述][06266ef0b5d145709d2cf3137e961a19.png] #####

##### 复杂度分析： #####

*  **时间复杂度**： O ( l e n ∗ m ∗ n ) O(len\*m\*n) O(len∗m∗n), len为数组的长度，m 、n 分别为题目所给 0 ， 和 1 的个数。
 *  **空间复杂度**： O ( m ∗ n ) O(m\*n) O(m∗n)，m 、n 分别为题目所给 0 ， 和 1 的个数。

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[06266ef0b5d145709d2cf3137e961a19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c6a1c66f0a7540f587aca0473ab6df1e.png
[Link 1]: https://leetcode.cn/problems/ones-and-zeroes/description/