Сложность: medium
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.length); i++) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0) {
int[] count = countzeroesones(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
len++;
}
}
if (zeroes <= m && ones <= n)
maxlen = Math.max(maxlen, len);
}
return maxlen;
}
public int[] countzeroesones(String s) {
int[] c = new int[2];
for (int i = 0; i < s.length(); i++) {
c[s.charAt(i) - '0']++;
}
return c;
}
}Ставь 👍 и забирай 📚 Базу знаний