Задачи с ограниченным количеством в №24

Задачи с ограниченным количеством в №24

Продолжаем смотреть жесткий тип 24 задач, который ненавидят многие ребята из клуба "98") Разбираемся сразу на практике, взял задачу с bank-kege.ru, условие и другой способ - в посте выше! А сегодня самый хайп: 2.1 - главный способ, которому все преподы учат своих учеников, 2.2 - его улучшение от меня, а 2.3 - просто экзотический прикольчик)

✅ Повторяющиеся комбинации

✅ Запрещённые комбинации

👉 Ограниченное количество

✅ Анализ индексов

➡️ Метод двух указателей (сейчас)

🔜 Двойной цикл и split() + join()

🔜 Сложные шаблоны

🔜 Несколько строк

🔜 Частотный анализ

2⃣ Метод двух указателей

Идея: Есть 2 указателя - левый и правый индекс, рассматриваем подстроку между ними. Правый перебираем просто циклом for, а левый двигаем сами так, чтобы между ними было не больше 100 букв T, а строка была максимально расширенной влево. Если в строке менее 100 Т, можно спокойно считать ее подходящей и обновлять максимум, строки со 100 буквами Т их просто "обгонят". Остается в каждой итерации просто обновлять максимум. Для движения левого указателя тоже есть несколько способов:

1️⃣ Цикл while, самый популярный

Суть: Пока количество T больше 100, двигаем левый указатель на следующий индекс. Если текущая буква оказалась T, уменьшаем их количество на 1.

Код:

s = open('24.10017.txt').readline()

l = 0

cnt_T = 0

mx = 0

for r in range(len(s)):

if s[r] == 'T':

cnt_T += 1

while cnt_T > 100:

if s[l] == 'T':

cnt_T -= 1

l += 1

mx = max(mx, r - l + 1)

print(mx)

2️⃣ Список с индексами

Суть: Добавляем в список индексы входящих букв T, как только их больше 100 (то есть 101), сдвигаем левый указатель сразу на следующий индекс после самой левой T в списке и удаляем ее оттуда.

Код:

s = open('24.10017.txt').readline()

l = 0

ind_T = []

mx = 0

for r in range(len(s)):

if s[r] == 'T':

ind_T.append(r)

if len(ind_T) > 100:

l = ind_T[0] + 1

del ind_T[0]

mx = max(mx, r - l + 1)

print(mx)

3️⃣ Поиск индекса для сдвига методом index()

Суть: Считаем количество T как в 1 варианте, как только перевалило за 100, двигаем левый указатель сразу на следующий символ после T, которая больше не входит. Его просто находим методом index(). Но потом заменяем эту букву на другой символ, чтобы в следующий раз метод index() нашел индекс следующей буквы T. Работает гораздо дольше, не рекомендую из-за скорости.

Код:

s = open('24.10017.txt').readline()

l = 0

cnt_T = 0

mx = 0

for r in range(len(s)):

if s[r] == 'T':

cnt_T += 1

if cnt_T > 100:

l = s.index('T') + 1

s = s.replace('T', '*', 1)

cnt_T -= 1

mx = max(mx, r - l + 1)

print(mx)

Для этой конкретной задачи ответа я так и не дождался)

А теперь, чтобы закрепить в голове все эти тактики-галактики, даю мини-домашку: №24.50002. А для тех, кто совсем прошаренный - №24.30035. Задачи из базы bank-kege.ru. Разбор первой из этих уже есть на платформе, а если нужен разбор второй - пишите в комменты! Ставьте обязательно 🔥, чтобы последний пост про этот тип вышел как можно быстрее! Там, кстати, дам еще целых 2 топ способа!

#информатика

#задание24