Сложность: 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⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
int findMaxForm(std::vector<std::string>& strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.size()); ++i) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; ++j) {
if ((i & (1 << j)) != 0) {
auto count = countZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
++len;
}
}
if (zeroes <= m && ones <= n)
maxlen = std::max(maxlen, len);
}
return maxlen;
}
std::vector<int> countZeroesOnes(const std::string& s) {
std::vector<int> c(2, 0);
for (char ch : s) {
++c[ch - '0'];
}
return c;
}
};
Ставь 👍 и забирай 📚 Базу знаний