C语言重构【474】一和零

文章目录

所有题目源代码: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数组),其公式如下:参考地址
    C语言重构【474】一和零
  • 需要注意的是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(lenmn)
  • 空间复杂度:O(lenmn);其他的计数为小头(2*len)
上一篇:刷题-力扣-14


下一篇:14. 最长公共前缀【测试岗常见算法题】