Задача: 1248. Count Number of Nice Subarrays
Сложность: 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⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
def numberOfSubarrays(nums, k):
def atMost(nums, k):
count = 0
left = 0
res = 0
for right in range(len(nums)):
if nums[right] % 2 == 1:
count += 1
while count > k:
if nums[left] % 2 == 1:
count -= 1
left += 1
res += right - left + 1
return res
return atMost(nums, k) - atMost(nums, k - 1)
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
def numberOfSubarrays(nums, k):
def atMost(nums, k):
count = 0
left = 0
res = 0
for right in range(len(nums)):
if nums[right] % 2 == 1:
count += 1
while count > k:
if nums[left] % 2 == 1:
count -= 1
left += 1
res += right - left + 1
return res
return atMost(nums, k) - atMost(nums, k - 1)
Ставь 👍 и забирай 📚 Базу знаний