• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

一和零(leetcode)

开发技术 开发技术 2周前 (04-06) 7次浏览

题目链接:474. 一和零 – 力扣(LeetCode) (leetcode-cn.com)

 

题目描述:

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

请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

 

示例:

示例 1:

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5031 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 41 ,大于 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

 

 

题目分析:

解题思路
dp[i][j]表示在最多有i个0,j个1的情况下的最多个字符串个数,最外面一层循环表示的是在前s个字符串中的最优的dp[i][j].
比如在第一次遍历strs时,取得第一个字符串,先判断m和n是否大于当前这个字符串的0和1的个数,i和j分别从最大值开始,dp[i][j] = Math.max(dp[i][j],dp[i-sc[0]][j-sc[1]]+1),表示的是,d[i][j]的最优解在d[i][j]和dp[i-当前字符串0的个数][j-当前字符串1的个数]+1中选择一个最大值。
例如示例1:
第一个字符串是“10”,m=5,n=3,在第一次遍历strs时:
dp[5][3] = max(dp[5][3],dp[5-1][3-1]+1);//不放下这个字符串和放下这个字符串
dp[5][2] = max(dp[5][2],dp[5-1][2-1]+1);//遍历每个数的01个数,从m到0的数量,从n到1的数量。如果能够容纳这个数那么从dp[m-n0][n-n1]到dp[m][n]的数都会加一(表示能够容纳下这个数的最大子串个数),如果不能就维持原样

.                                                             //所以经过维护,在能容纳下m个0,n个1的最大子串个数及为dp[m][n]!
.
.
dp[1][1] = max(dp[1][1],dp[1-1][1-1]+1);
遍历完成之后,表明,前1个字符串的最优解已经完成,之后遍历第二个字符串:
dp[5][3] = max(dp[5][3],dp[5-3][3-1]+1); //这里的dp[5][3]是已经遍历完第一个字符串之后的,第二个字符串在此基础上判断,选择max中的第一个dp[5][3]表明,不加上当前这个字符串,选择后面一个表明加上当前这个字符串,那么0和1的个数就要减去当前这个字符串的0和1的个数,然后再加1。
.
.
.
dp[3][1] = max(dp[3][1],dp[3-3][1-1]+1);
之后以此类推,就能得出前strs.length()个字符串的最优dp[5][3];

作者:jjm
链接:https://leetcode-cn.com/problems/ones-and-zeroes/solution/cong-da-dao-xiao-dp-by-jjm-1p06/

 

 

代码:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#include <list>
#include <memory>
using namespace std;

int main()
{
    //m--0   n--1
    vector<string>strs = { "10", "0001", "1", "0" };
    int m = 5, n = 3;

    int dp[100][100];//字串 1 0的情况下字串最多的数量
    memset(dp, 0, sizeof(dp));
    for (int x = 0;x < strs.size();x++)
    {
        int n0 = 0, n1 = 0;
        for (char y : strs[x])//获取01个数
            y == '0' ? n0++ : n1++;

        for (int i = m;i >= n0;i--)
        {
            for (int j = n;j >= n1;j--)
            {
                dp[i][j] = max(dp[i][j], dp[i - n0][j - n1] + 1);//状态转移方程
            }
        }
    }
    cout << dp[m][n];
}

 

 


程序员灯塔
转载请注明原文链接:一和零(leetcode)
喜欢 (0)