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