Leetcode 474 一和零

这篇具有很好参考价值的文章主要介绍了Leetcode 474 一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题意理解

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

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

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

        

        将字符串0和1的个数看作是该字符串的两个维度,假设将其看作物品的重量和体积。

        那么m和n就是对背包的限制:承重量为m, 体积为的背包。

        求元素最多的子集,该问题可以转换为:求装满承重量m体积n的背包最多有放多少件物品。

        所以该问题被转换为一个二维的0-1背包问题。

解题思路

        首先理解题意将其转换为0-1背包问题。

        其次,此处的动态滚动数组是二维的:

        dp[i][j]表示:装满承重i,体积为j的背包最多有多少件物品。

        之前的递推公式为:

        dp[j]=max(dp[j],dp[j-weight[i]]+values[i])

        此处递推公式做些许调整:

        dp[i][j]=max(dp[i][j],dp[i-weight[i]][j-vomule[i]]+1)

        初始化:

                对于背包为0 的物品装满需要0件物品。

1.动态规划:动态滚动数组求解二维0-1背包问题

任然是采用动态规划五部曲来求解该问题,不同之处在于此处的背包是一个二维限制的背包,此处的dp滚动数组是二维的。

public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(int[] tmp:dp) Arrays.fill(tmp,0);
        int countZero=0,countOne=0;
        //遍历物品
        for(int i=0;i<strs.length;i++){
            //计算0/1个数
            countZero=0;
            countOne=0;
            for(char c:strs[i].toCharArray()){
                if(c=='0') countZero++;
                if(c=='1') countOne++;
            }
            //遍历m
            for(int w=m;w>=0;w--){
                //遍历n
                for(int v=n;v>=0;v--){
                    if(countZero<=w&&countOne<=v){
                        dp[w][v]=Math.max(dp[w][v],dp[w-countZero][v-countOne]+1);
                    }
                }
            }
        }
        return dp[m][n];
    }

2.分析

时间复杂度

        O(m×n×str_len)

空间复杂度

        O(m×n)文章来源地址https://www.toymoban.com/news/detail-798113.html

到了这里,关于Leetcode 474 一和零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode题目详解】第九章 动态规划 part05 1049. 最后一块石头的重量 II 494. 目标和 474.一和零(day43补)

    有一堆石头,用整数数组  stones 表示。其中  stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x 和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那么两块石头都会被完全粉碎; 如果  x != y

    2024年02月09日
    浏览(38)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(41)
  • 算法训练第四十三天|1049. 最后一块石头的重量 II 、494. 目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II 参考:https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分

    2023年04月09日
    浏览(38)
  • 474. 一和零

    目录 1、题目描述 2、思路:动态规划01背包 2.1、确定dp数组及下标含义 2.2、确定递归数组 2.3、初始化 2.4、确定遍历顺序 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是

    2024年02月03日
    浏览(22)
  • 力扣:474. 一和零(动态规划)(01背包)

    给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。 示例 1 : 输入: strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3 输出:

    2024年01月22日
    浏览(36)
  • 力扣第474题 一和零 c++ 动态规划 01背包

    474. 一和零 中等 相关标签 数组   字符串   动态规划 给你一个二进制字符串数组  strs  和两个整数  m  和  n  。 请你找出并返回  strs  的最大子集的长度,该子集中  最多  有  m  个  0  和  n  个  1  。 如果  x  的所有元素也是  y  的元素,集合  x  是集合  y

    2024年02月06日
    浏览(38)
  • leetcode 动态规划(最后一块石头的重量II、目标和、一和零)

    力扣题目链接(opens new window) 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x = y。那么粉碎的可能结果如下: 如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那

    2024年02月03日
    浏览(47)
  • day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

    目录: 1049. 最后一块石头的重量 II 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那

    2024年02月12日
    浏览(35)
  • 【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月03日
    浏览(41)
  • Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    本题物品的重量为stones[i],物品的价值也为stones[i]。 对应着01背包里的物品重量weight[i]和 物品价值value[i]。 确定dp数组以及下标的含义 dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j] 。 确定递推公式 01背包的递推公式为:dp[j] = ma

    2024年04月23日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包