# 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".```

## 思路和代码

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...

• ### LeetCode 828. 统计子串中的唯一字符（中心扩展）

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

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

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

• ### linux命令sed与awk是干什么用的

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

• ### 2020测试工具索引

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

• ### 详解Python中的逻辑运算符and or 和not

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

• ### 专题报告:海洋生物声学的探测与分类与深度学习（CS SD）

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