LeetCode474. 一和零

474. 一和零


一、题目

给你一个二进制字符串数组 strs 和两个整数 mn

请你找出并返回 strs 的最大子集的长度,该子集中 最多m0n1

如果 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背包

我们将这个问题与01背包问题联系起来:

  • 物品:字符串数组strs中的每个字符串可以看作一个物品。
  • 重量:每个字符串有两个重量,分别是0的数量(zeroNum)和1的数量(oneNum)。
  • 价值:每个字符串的价值都是1,因为我们的目标是找到最大子集的长度,价值即为长度。

问题的限制条件如下:

  • 背包容量1:最多有m个0。
  • 背包容量2:最多有n个1。

思考过程

  1. 首先,我们需要找到一个动态规划的状态表示。题目要求找出一个最大子集,这个子集中最多有m个0和n个1。我们可以用一个二维数组dp来表示状态,其中dp[i][j]表示在限制条件下最多可以包含i个0和j个1的子集的最大长度。

  2. 接下来,我们需要找到状态转移方程,也就是如何从一个状态转移到下一个状态。对于每个字符串strs[i],我们需要考虑两种情况:

    • 如果选择不包含这个字符串,那么dp[i][j] = dp[i-1][j],表示不使用这个字符串,保持前一个状态的值。
    • 如果选择包含这个字符串,我们需要减去这个字符串中0和1的数量(zeroNum和oneNum),然后更新dp[i][j]。具体来说,dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)。这表示如果选择包含这个字符串,我们可以在前一个状态的基础上加1,但是要确保不超过限制条件;或者说如果原状的个数更多,那么维持原状。
  3. 最后,我们需要遍历所有的字符串并填充dp数组,然后返回dp[m][n]作为最终答案。

代码

class Solution {
public:
    //找到字符串中0和1数量
    void countNum(string str, int &a, int &b){
        for(int i = 0; i < str.size(); i++){
            if(str[i] == '1'){
                b++;
            }else{
                a++;
            }
        }
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        //dp[i][j]代表i个0和j个1情况下最多子集数量
        vector<vector<int>> dp(m+1,vector<int>(n+1, 0));
        for(string str: strs){
            int oneNum = 0;
            int zeroNum = 0;
            countNum(str, zeroNum, oneNum);
            for(int i = m; i >= zeroNum; i--){
                for(int j = n; j >= oneNum; j--){
                    dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
};

方法二:01背包三维数组

其他思路与上面差不多,就先忽略,下面是一些细节性的部分:

初始化

首先,对于第一个字符串 strs[0],我们需要计算其包含的0和1的数量,分别记为 zero_pone_p。接着,我们初始化 dp[0][i][j] 数组,其中 i 表示可用的0的数量, j 表示可用的1的数量。初始化规则是:

  • 如果 zero_p 不超过可用的0数量 i,并且 one_p 不超过可用的1数量 j,则 dp[0][i][j] 被设为1,表示可以选择该字符串。

这一步确保了在考虑第一个字符串时,我们只考虑了可行的情况。

填写 dp 数组

接下来,我们遍历字符串数组 strs,从第二个字符串开始(因为第一个字符串已经处理过了),计算每个字符串中0和1的数量,分别为 zeroNumoneNum

然后,我们使用嵌套的循环遍历可用的0和1的数量(jk),并填充 dp 数组:

  • 如果 j 小于 zeroNum 或者 k 小于 oneNum,则说明当前字符串不能选择,因此 dp[i][j][k] 等于上一个状态 dp[i-1][j][k]

  • 否则,我们有两个选择:不选择当前字符串(继承上一个状态)或选择当前字符串(当前状态等于上一个状态减去当前字符串的0和1数量再加1)。我们选择这两者中的较大值。

最终,dp[strs.size()-1][m][n] 包含了所有字符串的最优解,表示在限制条件下可以获得的最大子集长度。

class Solution {
public:
    void countNum(string str, int &a, int &b){
        for(int i = 0; i < str.size(); i++){
            if(str[i] == '1'){
                b++;
            }else{
                a++;
            }
        }
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        //dp[i][j][k]代表在0到i个元素中,j个0和k个1的最大子集
        vector<vector<vector<int>>> dp(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));
        //初始化
        int one_p = 0;
        int zero_p = 0;
        countNum(strs[0],one_p,zero_p);
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(one_p <= i && zero_p <= j){
                    dp[0][i][j] = 1;
                }
            }
        }
        //填写dp数组
        for(int i = 1; i < strs.size(); i++){
            int oneNum = 0;
            int zeroNum = 0;
            countNum(strs[i], zeroNum, oneNum);
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j < zeroNum || k < oneNum){
                        dp[i][j][k] = dp[i-1][j][k];
                    }else{
                        dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
                    }
                    
                }
            }
        }
        return dp[strs.size()-1][m][n];
    }
};