一和零(LeetCode 474)

简介: 一和零(LeetCode 474)

一和零(LeetCode 474)

Description

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

请你找出并返回 strs 的最大子集的长度,该子集中 最多m0n1

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

Sample Input 1

strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

Sample Output 1

4

Sample Tips 1

最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。

其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。

{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

Sample Input 2

strs = ["10", "0", "1"], m = 1, n = 1

Sample Output 2

2

Sample Tips 2

最大的子集是 {"0", "1"} ,所以答案是 2 。

Tips

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0''1' 组成
  • 1 <= m, n <= 100

算法思想:

多重背包是每个物品,数量不同的情况。

本题中strs 数组里的元素就是物品,每个物品都是一个!

而m 和 n相当于是一个背包,两个维度的背包

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

动规五部曲分析如下:

  1. 确定dp数组以及下标的含义

    dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

  2. 确定递推公式

    dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

    dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

    然后我们在遍历的过程中,取dp[i][j]的最大值。

    所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

    此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

    这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

  3. dp数组如何初始化

    因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

  4. 确定遍历顺序

    外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!

    那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。

    for (string str : strs) { // 遍历物品
        int oneNum = 0, zeroNum = 0;
        for (char c : str) {
            if (c == '0') zeroNum++;
            else oneNum++;
        }
        for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!
            for (int j = n; j >= oneNum; j--) {
                dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            }
        }
    }
  5. 推导dp数组

    输入["10","0001","111001","1","0"],m = 3,n = 3

    dp数组状态图为:

    下标i j:        0  1  2  3
                0   0  1  1  1
                0   1  2  2  2
                0   1  2  3  3
                0   1  2  3  3

综上分析完毕,代码如下:

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

Java代码代码如下:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
目录
相关文章
|
存储 设计模式 负载均衡
一文读懂Spring动态配置多数据源---源码详细分析(下)
一文读懂Spring动态配置多数据源---源码详细分析
2406 0
一文读懂Spring动态配置多数据源---源码详细分析(下)
|
运维 监控 应用服务中间件
自动化运维的新篇章:Ansible Playbooks入门与实战
【9月更文挑战第1天】在追求效率和稳定性的今天,自动化运维已经成为IT行业的必修课。本文将带你走进自动化工具Ansible的世界,通过实战案例深入理解Ansible Playbooks的编写和应用。文章不仅介绍基础概念,更通过具体代码示例,展示如何利用Ansible简化日常运维任务,提升工作效率。无论你是运维新手还是希望深化自动化技能的资深人士,本指南都将为你开启一段新的学习旅程。
|
9月前
|
Serverless 对象存储 人工智能
智能文件解析:体验阿里云多模态信息提取解决方案
在当今数据驱动的时代,信息的获取和处理效率直接影响着企业决策的速度和质量。然而,面对日益多样化的文件格式(文本、图像、音频、视频),传统的处理方法显然已经无法满足需求。
325 4
智能文件解析:体验阿里云多模态信息提取解决方案
|
算法 Docker Python
二十七 | 案例篇:为什么我的磁盘I/O延迟很高?
二十七 | 案例篇:为什么我的磁盘I/O延迟很高?
645 0
|
测试技术
8B尺寸达到GPT-4级性能!北大等提出医疗专家模型训练方法
【7月更文挑战第8天】北京大学等研究者提出的新方法缓解了大模型如Llama-3-8B在持续预训练时的“稳定性差距”,通过多轮次训练、高质量子语料库选择和数据混合策略,提升性能和效率。在医疗领域,他们将OpenLlama-3B性能提升至40.7%,并创建的Llama-3-Physician模型达到GPT-4级别。尽管取得突破,该方法在其他模型和领域的适用性仍需探索,且持续预训练仍资源密集。[链接: https://arxiv.org/abs/2406.14833]
214 25
|
数据采集 数据挖掘 Serverless
利用Python和Pandas库优化数据清洗流程
在数据分析项目中,数据清洗是至关重要的一步。传统的数据清洗方法往往繁琐且易出错。本文将介绍如何利用Python编程语言中的Pandas库,通过其强大的数据处理能力,实现高效、自动化的数据清洗流程。我们将探讨Pandas库在数据清洗中的应用,包括缺失值处理、重复值识别、数据类型转换等,并通过一个实际案例展示如何利用Pandas优化数据清洗流程,提升数据质量。
|
数据处理 计算机视觉 Python
图像数据处理:基本技巧与实例分析
图像数据处理:基本技巧与实例分析
394 0
|
监控 索引
配置本地端口镜像示例(1:N,单个配置观察端口)
1:N镜像是指将单个镜像端口的报文复制到N个不同的观察端口,主要适用于将报文复制到不同监控设备进行分析处理的场合。 1:N镜像需要配置多个观察端口,连接不同的监控设备。观察端口有单个配置和批量配置两种方式,而且这两种方式可同时配置。观察端口组一般在1:N镜像时使用,既可以简化配置,还可以节约观察端口索引(一个观察端口组无论包含多少个端口,仅占用一个观察端口索引)。
145 1
|
存储 测试技术 网络安全
SDN 系统方法 | 8. 网络虚拟化
SDN 系统方法 | 8. 网络虚拟化
681 0
SDN 系统方法 | 8. 网络虚拟化
|
SQL 数据可视化 数据库