474. 一和零

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 125 阅读 / 850 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

思路:

m,n为背包容量,str是物品列表,价值为1

代码:

class Solution {
public:
    void count(int& m,int& n, string& str){
        for(auto ch:str){
            if(ch=='0')   m++;
            else    n++;
        }
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(auto str:strs){
            int m_num=0, n_num=0;
            count(m_num,n_num,str);
            for(int i=m;i>=m_num;i--){
                for(int j=n;j>=n_num;j--){
                    dp[i][j]=max(dp[i][j],dp[i-m_num][j-n_num]+1);
                }
            }
        }
        return dp[m][n];
    }
};
0

评论区