C语言重构【474】一和零

痛定思痛。 2023-01-07 10:05 124阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个二进制字符串数组 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 。

#### 方案： ####

*  思路在注释中，这里简单讲下，我认为这是一道二维动态规划的题（虽然是三维dp数组），其公式如下：[参考地址][Link 1]  
    ![在这里插入图片描述][20210116181446440.png]
 *  需要注意的是i=0的第一个二维一定得初始化为0，我这里本来想用三维vector，结果不知道咋初始化～，后来还是用了原始方法
 *  值得一提的是，可以先把每个字符串的0，1个数事先算出来，再调用就可以减少很多计算量，同时也简化了题目。

class Solution
    { 
    public:
        int findMaxForm(vector<string> &strs, int m, int n)
        { 
            int len = strs.size();
            //dp[i][j][k] i=len;j=m;k=n;
            // vector<vector<vector<int>>> dp(len+1,vector<int>(m+1,vector<int>(n+1)));
            int dp[len + 1][m + 1][n + 1];
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= n; k++)
                    dp[0][j][k] = 0;
    
            //先数清每个串0，1个数
            // vector<vector<int>> tmp(len,vector<int>(2,0));
            int tmp[len][2];
            for (int i = 0; i < len; i++)
            { 
                //count
                int cn = 0, cm = 0;
                for (int j = 0; j < strs[i].size(); j++)
                    if (strs[i][j] == '0')
                        cm++;
                    else if (strs[i][j] == '1')
                        cn++;
                tmp[i][0] = cm;
                tmp[i][1] = cn;
            }
            //再填dp
            //dp[i][j][k] =dp[i-1][j][k] (不放)
            // =dp[i-1][j-m][k-n]+1 (放，这里注意需要考虑jk比mn小的问题,mn是某个字符串01个数)
            for (int i = 1; i <= len; i++)
                for (int j = 0; j <= m; j++)
                    for (int k = 0; k <= n; k++)
                        if (k < tmp[i - 1][1] || j < tmp[i - 1][0])
                            //背包空间不够，不能放
                            dp[i][j][k] = dp[i - 1][j][k];
                        else 
                            //背包空间足够，可以考虑放
                            dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - tmp[i - 1][0]][k - tmp[i - 1][1]] + 1);
            return dp[len][m][n];
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(len*m*n)
 *  空间复杂度：O(len*m*n)；其他的计数为小头（2\*len）

[Git]: https://github.com/ch98road/leetcode
[Link 1]: https://leetcode-cn.com/problems/ones-and-zeroes/solution/dong-tai-gui-hua-zhuan-huan-wei-0-1-bei-bao-wen-ti/
[20210116181446440.png]: /images/20221119/5f2f9e6b4c774bc88c4fa5b667b1b12c.png