一和零(LeetCode-474)

简介: 一和零(LeetCode-474)

6. 一和零(LeetCode-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[i][j] 含义


最多能装 i 个 0  和 j 个 1  的背包的最大子集的数量

递推公式


虽然是二维的,但其实只包含背包重量这一个方面,本质还是滚动数组。

d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − n u m Z e r o ] [ j − n u m O n e ] + 1 )

其中,n u m Z e r o numZeronumZero 和 n u m O n e numOnenumOne 分别表示当前物品,即当前子集的零和一个数。相当于物品的重量。而后面的加一相当于物品的价值。为什么是一?因为加上当前物品后,最大子集数量就加一了。

数组初始化


物品价值不为负数,所以初始化为零即可

遍历顺序


先遍历物品,嵌套遍历背包,且背包遍历要倒序

测试用例


本图为最后状态



代码展示

class Solution
{
public:
    int findMaxForm(vector<string> &strs, int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int idx = 0; idx < strs.size(); idx++)
        {
            int numZero = 0, numOne = 0;
            for (char val : strs[idx])
            {
                if (val == '0')
                {
                    numZero++;
                }
                else
                {
                    numOne++;
                }
            }
            for (int i = m; i >= numZero; i--)
            {
                for (int j = n; j >= numOne; j--)
                {
                    dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1);
                }
            }
        }
        return dp[m][n];
    }
};
目录
相关文章
|
10月前
|
JSON 人工智能 算法
探索LLM推理全阶段的JSON格式输出限制方法
文章详细讨论了如何确保大型语言模型(LLMs)输出结构化的JSON格式,这对于提高数据处理的自动化程度和系统的互操作性至关重要。
1784 52
|
编解码 开发工具 Android开发
低延迟播放超高分辨率(4K+)帧率(50帧+)RTSP|RTMP流技术探讨和实现
为满足安检等场景需求,需支持4K+分辨率与50帧以上的高帧率视频流播放。实现这一目标的关键步骤包括:确保视频源支持高帧率输出、选用高性能RTSP/RTMP播放器以处理高负载视频解码、采用硬件解码以降低CPU负担、保证充足的网络带宽以维持流畅播放并控制延迟、合理配置播放器缓冲策略以适应网络波动、进行性能监控与调试以优化播放效果,以及确保播放器在多平台上的良好兼容性和表现。例如,大牛直播SDK的SmartPlayer在不同平台上实现了稳定且低延迟(150-300ms)的播放体验,支持多种视频和音频格式及多种功能,如多实例播放、事件回调、视频快照等。
574 1
|
SQL 安全 前端开发
Go语言Gin框架安全加固:全面解析SQL注入、XSS与CSRF的解决方案
Go语言Gin框架安全加固:全面解析SQL注入、XSS与CSRF的解决方案
|
存储 前端开发 JavaScript
解锁前端高手之路:Vuex 状态管理实战,从零到精通的旅程!
【8月更文挑战第27天】状态管理在大型单页应用开发中至关重要。Vue.js 通过其官方工具 Vuex 提供了一套强大且直观的 API。本文从零开始引导你逐步掌握 Vuex。首先介绍如何安装和配置,然后通过具体示例深入探讨状态(State)、变更(Mutations)、动作(Actions)以及模块化 Store 的使用方法。最后,通过购物车管理实战案例展示如何运用 Vuex 解决复杂状态管理问题。掌握这些技巧后,你将能在项目中高效地利用 Vuex。
120 1
|
Windows
[Qt5] 创建菜单栏、工具栏、核心控件和浮动窗口
[Qt5] 创建菜单栏、工具栏、核心控件和浮动窗口
332 0
|
分布式计算 Hadoop Java
使用Hadoop MapReduce分析邮件日志提取 id、状态 和 目标邮箱
使用Hadoop MapReduce分析邮件日志提取 id、状态 和 目标邮箱
209 0
|
自然语言处理 PyTorch 算法框架/工具
TextBrewer:融合并改进了NLP和CV中的多种知识蒸馏技术、提供便捷快速的知识蒸馏框架、提升模型的推理速度,减少内存占用
TextBrewer:融合并改进了NLP和CV中的多种知识蒸馏技术、提供便捷快速的知识蒸馏框架、提升模型的推理速度,减少内存占用
TextBrewer:融合并改进了NLP和CV中的多种知识蒸馏技术、提供便捷快速的知识蒸馏框架、提升模型的推理速度,减少内存占用
|
监控 Java API
Google Earth Engine(GEE)——利用sentinel-2数据
Google Earth Engine(GEE)——利用sentinel-2数据
604 0
Google Earth Engine(GEE)——利用sentinel-2数据
|
存储 编译器 C语言
19 C语言 - 结构体
19 C语言 - 结构体
80 0