IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 2021-12-7 474. 一和零(动态规划) -> 正文阅读

[数据结构与算法]2021-12-7 474. 一和零(动态规划)

注:

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

提示:
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

题解:
定义dp数组
定义三维数组 dp,其中 dp[i][j][k] 表示在前 i 个字符串中,使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量。假设数组 str 的长度为 l,则最终答案为 dp[l][m][n]。

初始化dp
当没有任何字符串可以使用时,可以得到的字符串数量只能是 0,因此动态规划的边界条件是:当 i=0 时,对任意0≤j≤m 和 0≤k≤n,都有 dp[i][j][k]=0。

状态转移方程
当 1≤i≤l 时,对于 strs 中的第 i 个字符串(计数从 1 开始),首先遍历该字符串得到其中的 0 和 1 的数量,分别记为 zeros 和 ones,然后对于 0≤j≤m 和 0≤k≤n,计算 dp[i][j][k] 的值。

当 0 和 1 的容量分别是 j 和 k 时,考虑以下两种情况:

  • 如果 j<zeros 或k<ones,则不能选第 i 个字符串,此时有 dp[i][j][k]=dp[i?1][j][k];

  • 如果 j≥zeros 且 k≥ones,则如果不选第 i 个字符串,有 dp[i][j][k]=dp[i?1][j][k],如果选第 i 个字符串,有 dp[i][j][k]=dp[i?1][j?zeros][k?ones]+1,dp[i][j][k] 的值应取上面两项中的最大值。

因此状态转移方程如下:
在这里插入图片描述

复杂度分析
时间复杂度:O(lmn + L),其中 l 是数组 strs 的长度,m 和 n 分别是 0 和 1 的容量,L 是数组 strs 中的所有字符串的长度之和。

空间复杂度:O(lmn)。

class Solution {
public:
    vector<int> getZeroOne(string str){
        vector<int> res(2);
        for(char c:str){
            res[c-'0']++;
        }
        return res;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>> dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1)));
        for(int i=1;i<=strs.size();i++){
            string str=strs[i-1];
            vector<int> t;
            t=getZeroOne(str);
            int zero=t[0];
            int one=t[1];
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){     
                    if(j<zero||k<one){
                        dp[i][j][k]=dp[i-1][j][k];
                    }
                    else {
                        dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1);
                    }
                }
            }
        }
        return dp[strs.size()][m][n];
    }
};

优化空闲复杂度至O(mn)

class Solution {
public:
    vector<int> getZeroOne(string str){
        vector<int> res(2);
        for(char c:str){
            res[c-'0']++;
        }
        return res;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=strs.size();i++){
            string str=strs[i-1];
            vector<int> t;
            t=getZeroOne(str);
            int zero=t[0];
            int one=t[1];
            for(int j=m;j>=zero;j--){
                for(int k=n;k>=one;k--){     
                    dp[j][k]=max(dp[j][k],dp[j-zero][k-one]+1);
                }
            }
        }
        return dp[m][n];
    }
};
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-08 14:04:10  更:2021-12-08 14:06:17 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/10 2:13:10-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码