LeetCode-474. Ones and Zeroes

LeetCode-474. 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 = 3Output: 4Explanation: 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 = 1Output: 2Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

题解：

想到dp但是没想到如何分割子问题，参考了高赞答案。

逆向实现问题分割，每添加一个字符串，动态将m，n降为0的过程分割。

class Solution {public: int findMaxForm(vector& strs, int m, int n) { int l = strs.size(); vector zeros(l, 0); vector ones(l, 0); vector> dp(m + 1, vector (n + 1, 0)); for (int j = 0; j < l; j++) { string s = strs[j]; for (int i = 0; i < s.length(); i++) { if (s[i] == '0') { zeros[j]++; } else if (s[i] == '1') { ones[j]++; } } } for (int k = 0; k < l; k++) { for (int i = m; i >= zeros[k]; i--) { for (int j = n; j >= ones[k]; j--) { dp[i][j] = max(dp[i - zeros[k]][j - ones[k]] + 1, dp[i][j]) ; } } } return dp[m][n]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。