Задание 24 · Обработка символьной информации
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Все подтемы учат одному — проходу по строке, где по дороге помнят только нужное; задача темы о самом длинном корректном выражении решается в подтеме 6. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Строка и цепочка»: один проход: current и best. Точками отмечены новые строки.
- Подтема 2, «Условия на соседей»: пара соседей — сброс до 1.
- Подтема 3, «Образцы и блоки»: образец — pattern[current % m].
- Подтема 4, «Скользящее окно»: окно: while двигает левый край.
- Подтема 6, «Числа и выражения»: выражение — регулярным выражением. Ответ задачи темы — 172.
От подтемы к подтеме меняется только то, что помнят: длину цепочки, предыдущий символ, место в образце, границы окна. Подтема 5 помнит позиции нужных символов, а дополнительный урок — выражения с условиями и баланс.
Карта темы
Каждая подтема дала свой способ помнить нужное, и любое решение собирается из них. Сверху — путь от файла к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Строкаopen(…).readline().strip()
- Один проходчто помнить по дороге
- Ответдлина, позиция или число
1Строка и цепочка
currentдлина цепочки, которая кончается здесьbestобновлять после каждого символа
2Условия на соседей
- запретный символсброс до 0
- запретная парасброс до 1
range(1, len(s))у первого символа нет соседа слева
3Образцы и блоки
pattern[current % m]какой символ ждём следующим- вхожденияс перекрытиями — не count
4Скользящее окно
- не более Kwhile count > K двигает левый край
- ровно Kответ только при count == K
5Позиции и границы
- K подрядпо списку позиций нужных символов
- −1 и len(s)искусственные границы по краям
6Числа и выражения
(?:0|[1-9][0-9]*)число без ведущих нулейre.finditerвсе совпадения, длина каждого
7Выражения с условиями и балансдополнительный урок
- баланспервые появления разности в словаре
Как решать
Любое задание 24 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Для сложного условия напиши медленную проверку: перебери все куски строки из десяти символов и сравни ответ с быстрой программой. Для файла такой перебор не годится, а для короткой строки — в самый раз.
Частые ошибки
Семь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- перевод строки
open(…).readline()→open(…).readline().strip(). Спроси себя: нет ли лишнего символа в конце строки?подтема 1- best при обрыве
- best обновляют только при разрыве цепочки → после каждого символа. Спроси себя: а если лучшая цепочка — в самом конце?подтема 1
- s[i − 1] при i = 0
range(len(s))→range(1, len(s)). Спроси себя: с кем сравнится первый символ?подтема 2- сброс до 0
- на запретной паре current = 0 → current = 1. Спроси себя: не начинает ли второй символ новую цепочку?подтема 2
- count и перекрытия
'ABABA'.count('ABA')→ проход с перекрытиями: ABA дважды. Спроси себя: могут ли вхождения налезать друг на друга?подтема 3- if вместо while
- левую границу окна сдвинули один раз → while, пока окно не станет допустимым. Спроси себя: а если лишняя буква не первая в окне?подтема 4
- числа как строки
- наибольшее число — max по строкам → max по int. Спроси себя: что больше: '45' или '131'?подтема 6
Итог
Тема пройдена: от цепочки одинаковых символов до задачи темы с ответом 172. Вот что взять с собой.
- ПорядокСтрока, что помнить, проход, ответ, проверка.
- Цепочкаcurrent и best после каждого символа.
- Окноwhile двигает левый край, пока окно недопустимо.
- ВыраженияРегулярное выражение и re.finditer.
- Задача темыСамое длинное корректное выражение — 172 символа.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Почему все куски строки из миллиона символов не перебрать?
ОтветСкрыть ответ
Их около 5 · 10¹¹. Поэтому строку проходят один раз и помнят только нужное.
Самая длинная цепочка одинаковых подряд в AABBBBCCAAA?
ОтветСкрыть ответ
4 — BBBB.
Окно «не более двух A» в строке BABAACB: какое самое длинное?
ОтветСкрыть ответ
5 — BAACB: в нём две A, а любой кусок длиннее захватывает третью.
Корректное ли выражение 12+05*3? А 12+0*3?
ОтветСкрыть ответ
Первое нет: у 05 ведущий ноль. Второе да: 0 — само число без ведущих нулей.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Наибольшее число в файле
Текстовый файл 24-5.txt состоит из заглавных латинских букв и десятичных цифр. Числом считается последовательность цифр, ограниченная отличными от цифр символами, началом или концом строки. Определите наибольшее число в файле.
Введите число.
Подсказка
re.findall(r'[0-9]+', s) и сравнение через int, не как строки.
Решение
89242025401723.
Решение программой
import re s = open('24-5.txt').readline().strip()numbers = re.findall(r'[0-9]+', s)print(max(int(x) for x in numbers))Ответ: 89242025401723
Гласные не рядом
Текстовый файл 24-9.txt содержит только заглавные латинские буквы. Определите максимальное количество идущих подряд символов, среди которых никакие две гласные (A, E, I, O, U, Y) не стоят рядом.
Введите число.
Подсказка
Запрещённая пара — две гласные подряд.
Решение
89: при паре гласных сброс до 1 — вторая гласная начинает новый фрагмент.
Решение программой
s = open('24-9.txt').readline().strip() vowels = 'AEIOUY'current = best = 0for i in range(len(s)): if i > 0 and s[i - 1] in vowels and s[i] in vowels: current = 1 else: current += 1 best = max(best, current)print(best)Ответ: 89
Q, X, Z не более 40 раз
Для файла 24-9.txt определите максимальное количество идущих подряд символов, среди которых каждая из букв Q, X, Z встречается не более 40 раз.
Введите число.
Подсказка
Скользящее окно со словарём счётчиков.
Решение
4237: на каждую из трёх букв свой счётчик; окно сжимается, когда превышен счётчик только что добавленной буквы.
Решение программой
s = open('24-9.txt').readline().strip() count = {c: 0 for c in 'QXZ'}left = best = 0for right in range(len(s)): c = s[right] if c in count: count[c] += 1 while count[c] > 40: if s[left] in count: count[s[left]] -= 1 left += 1 best = max(best, right - left + 1)print(best)Ответ: 4237
Одна буква на концах
Для файла 24-9.txt определите максимальную длину фрагмента, который начинается и заканчивается одной и той же буквой из набора A, B, C, D, E, F и не содержит эту букву внутри.
Введите число.
Подсказка
Концы — соседние вхождения одной буквы: части s.split(c) между ними.
Решение
355: для каждой буквы c фрагменты — части s.split(c)[1:-1] между соседними вхождениями, длина фрагмента — длина части плюс 2.
Решение программой
s = open('24-9.txt').readline().strip() last = {}best = 0for i in range(len(s)): c = s[i] if c in 'ABCDEF': if c in last: best = max(best, i - last[c] + 1) last[c] = iprint(best)Ответ: 355
Корректная сумма
Текстовый файл 24-6.txt состоит из десятичных цифр и знаков «+» и «*». Определите максимальное количество символов в непрерывной последовательности, которая является корректной суммой: целые неотрицательные числа без ведущих нулей, между соседними числами ровно один знак «+», других знаков нет.
Введите число.
Подсказка
Шаблон суммы: число, затем повторения «+ число»; знак * обрывает сумму.
Решение
67: шаблон number + r'(?:\+' + number + r')*'; знак * обрывает сумму.
Решение программой
import re s = open('24-6.txt').readline().strip() number = r'(?:0|[1-9][0-9]*)'pattern = number + r'(?:\+' + number + r')*'print(max(len(m.group()) for m in re.finditer(pattern, s)))Ответ: 67