码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 力扣:474.一和零


    力扣:474.一和零
    题目:
    给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

    请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
    如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

    dp数组含义:
    dp[i][j] :0~n个物品放入容量为i个0,j个1的背包中的最大价值

    递归公式:
    dp[i][j] = max(dp[i][j],dp[j-当前值几个0][j-当前值几个1]+1)

    初始化:
    dp【i】【j】要么选择原先的dp【i】【j】(即初始化的dp【i】【j】)要么选择新计算的值,会选择两者中较大的那一个。

    • 如果dp【i】【j】是选择原先的dp【i】【j】即初始化的dp【i】【j】,又因为此时是从物品数为0开始遍历,按照含义来说其值应该是0。
    • 如果dp【i】【j】选择的是新计算的值,dp【i】【j】是从二者中选择更大的值,那么这个初始化的dp【i】【j】就不能够大于新计算的值,新计算的值恒大于0。所以初始化的dp【i】【j】为0即可。

    遍历顺序:
    遍历背包重量所有可能性
    遍历1个物品放入所有可能性重量的背包
    遍历2个物品放入所有可能性重量的背包
    遍历n个物品放入所有可能性重量的背包,此时才能够确保dp【i】【j】选择的是dp[j-zeronum][j-onenum]+1的时候,此值是已知的。
    此时只需要确保dp【i】【j】选择的是dp[j-zeronum][j-onenum]+1的时候,此值是已知的即可,那么先遍历i,j都可以。

    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[j-zeronum][j-onenum]+1);
                    }
                }
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 相关阅读:
    Java游戏服务器开发之概念扫盲
    MBR、GPT、LVM分区
    ES6 入门教程 29 ArrayBuffer 29.3 复合视图 & 29.4 DataView 视图 & 29.5 二进制数组的应用
    System.ArgumentException: 已添加了具有相同键的项
    Java学习笔记——Collection之Queue
    手把手实操|深度剖析电商贷款风控相关细节(电商贷模型)
    小程序中如何开启分销
    Tomcat设置IP黑名单和白名单server.xml
    《C和指针》笔记23: 指针的指针
    一文浅谈Mockito使用
  • 原文地址:https://blog.csdn.net/qq_56762247/article/details/126202567
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号