[Algorithm] 474. Ones and Zeroes
and ALGORITHM
2023-09-14 09:00:48 时间
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 n1s
respectively. On the other hand, there is an array with strings consisting of only0s
and1s
.Now your task is to find the maximum number of strings that you can form with given m
0s
and n1s
. Each0
and1
can be used at most once.Note:
- The given numbers of
0s
and1s
will both not exceed100
- 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".
/** * @param {string[]} strs * @param {number} m * @param {number} n * @return {number} */ var findMaxForm = function(strs, m, n) { if(!strs || strs.length === 0) return 0; let dp = [...Array(m+1)].map(_ => Array(n+1).fill(0)); strs.forEach(str=>{ const [zero, one] = calculateBinary(str); for(let i = m; i >= zero; i--){ for(let j = n ; j >= one; j--){ dp[i][j] = Math.max(dp[i][j],dp[i - zero][j - one] + 1); } } }) return dp[m][n] }; var calculateBinary = function(str){ let zero = 0, one = 0; for(let i = 0 ; i < str.length ; i++){ if(str[i] === "1") one++; else zero++; } return [zero, one]; }
相关文章
- [Linear Algebra] Matrices and Vectors
- [Algorithm] 122. Best Time to Buy and Sell Stock II
- 机器学习入门06 - 训练集和测试集 (Training and Test Sets)
- [Algorithm] 122. Best Time to Buy and Sell Stock II
- [Algorithm] Fibonacci Sequence - Anatomy of recursion and space complexity analysis
- [Algorithm] Construct a Binary Tree and Binary Search
- [Algorithm] Find Max Items and Max Height of a Completely Balanced Binary Tree
- [Algorithm] Heap data structure and heap sort algorithm
- [Redux] Avoiding Object Mutations with Object.assign() and ...spread
- [AngularJS] Extract predicate methods into filters for ng-if and ng-show
- MIT算法导论——第三讲.The Divide-and-Conquer
- 论文解读(Cluster-GCN)《Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks》