专栏首页眯眯眼猫头鹰的小树杈leetcode474. Ones and Zeroes

leetcode474. Ones and Zeroes

题目要求

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:

The given numbers of 0s and 1s will both not exceed 100
The size of given string array won't exceed 600.
 

Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
 

Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

已知有m个0和n个1,问最多能构成数组中多少个数字。已知每个0和1只能使用一次。

思路和代码

先是用深度优先遍历的思想进行了实现,结果很明显是超时了。接着采用动态规划的思想,其实这题就是背包问题的一个演化。假设已知道m个0和n个1能够从数组中前i个元素最多拼成多少个元素,则m个0和n个1能够从数组中前i+1个元素能够拼成最多的元素个数有如下两个场景:

  1. 第i+1个字符串的0的个数和1的个数分别小于m和n,则有两种选择,分别是选择该字符串和不选择该字符串,选择该字符串的话,maxi+1[n] = 1 + maxi[n-numOfOne(str)], 如果不选择的话,maxi+1[n] = maxi-1[n]。从两个选项中选择一个最大的即可。
  2. 否则的话,maxi+1[n] = maxi[n]

代码如下:

    public int findMaxForm2(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (String s : strs) {
            int[] count = count(s);
            for (int i=m;i>=count[0];i--) 
                for (int j=n;j>=count[1];j--) 
                    dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);
        }
        return dp[m][n];
    }
        
    public int[] count(String str) {
        int[] res = new int[2];
        for (int i=0;i<str.length();i++)
            res[str.charAt(i) - '0']++;
        return res;
     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 547. Friend Circles

    There are N students in a class. Some of them are friends, while some are not. T...

    眯眯眼的猫头鹰
  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • 377. Combination Sum IV

    有一个不包含重复值的正整数数组nums,问从数组中选择几个数,其和为target,这样的数的组合有几种?

    眯眯眼的猫头鹰
  • LeetCode 3: 无重复字符的最长子串

    Given a string, find the length of the longest substring without repeating chara...

    爱写bug
  • LeetCode 828. 统计子串中的唯一字符(中心扩展)

    我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符,并返回唯一字符的个数。

    Michael阿明
  • IIS Crypto – Windows 2008(R2) IIS下启用SSL的TLS1.1和TLS1.2好工具

    近期苹果要求App都用ssl安全连接了,以后会有越来越多的网站普及SSL。今天介绍的IIS Crypto是一个免费工具,用于在Windows 2008,2012...

    崔文远TroyCui
  • linux命令sed与awk是干什么用的

    非常强大的文本操纵工具,sed,awk,grep 这个三个命令 都是操作文本文件的 unix系统有几个特点: 对于内核而言,unix文件都是字节序列。io设备也...

    Albert陈凯
  • 2020测试工具索引

    在整理过程中,我会尽量去官网找到官方对该工具的描述,包括中文和英文,保证原汁原味。

    测试老树
  • 详解Python中的逻辑运算符and or 和not

    其次,逻辑操作符and 和or 也称作短路操作符(short-circuitlogic)或者惰性求值(lazy evaluation):它们的参数从左向右解析,...

    紫旭Blog - blog.zixutech.cn
  • 专题报告:海洋生物声学的探测与分类与深度学习(CS SD)

    019年11月21-22日,约30名研究人员齐聚加拿大BC省维多利亚州,参加由子午线组织、加拿大海洋网主办的“海洋生物声学深度学习检测与分类”研讨会。出席了研讨...

    用户6853689

扫码关注云+社区

领取腾讯云代金券