Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2]
Output: 2
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
class Solution {
function numberOfSubarrays($nums, $k) {
return $this->atMost($nums, $k) - $this->atMost($nums, $k - 1);
}
private function atMost($nums, $k) {
$res = 0;
$left = 0;
$count = 0;
for ($right = 0; $right < count($nums); $right++) {
if ($nums[$right] % 2 === 1) $count++;
while ($count > $k) {
if ($nums[$left++] % 2 === 1) $count--;
}
$res += $right - $left + 1;
}
return $res;
}
}Ставь 👍 и забирай 📚 Базу знаний