Основные методы решения №24

#1 Работа с файлами

Чтение файла, состоящего из одной строки:

Файл, состоящий из нескольких строк, будем обрабатывать построчно:

#2 Линейное решение

Любую из 24 задач можно решить линейно. Для этого необходимо, как правило, рассматривать подряд идущие пары/тройки/четвёрки чисел и проверять, подходят ли они под условие

Задача 1.

Определите максимальное количество подряд идущих чисел, среди которых каждые два соседних различны.

Рассуждения:

Для каждого i-того элемента будем проверять, отличается ли он от соседнего элемента с индексом i+1. Если да — увеличиваем счётчик на 1, т. к. очередной элемент удовлетворяет условию, если же нет — сбрасываем счетчик до 1.

Решение:

Задача 2.

Сколько раз встречаются комбинации «TIK» или «TOK»?

Рассуждения:

Будем проверять подряд идущие тройки элементов. Если тройка удовлетворяет условию — увеличиваем счётчик на единицу.

Решение:

Важно: чтобы избежать ошибок с индексами при линейном решении 24 задач, нужно запомнить несложное правило. Если необходимо рассматривать  каждый элемент строки отдельно, то цикл for принимает вид:

Для пар идущих подряд элементов:

Для троек идущих подряд элементов:

Общая формула для цикла for:

#3 Методы «replace» и «split»

Метод replace заменяет часть строки на другую строку:

count – необязательный аргумент, если его не указать, будут заменены все вхождения указанной подстроки (text1).

Метод split разбивает строку по указанному в качестве параметра разделителю (в примере символ *) и возвращает список строк:

Задача 3.

В текстовом файле находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите длину самой длинной подцепочки, состоящей из символов A, C, D (в произвольном порядке).

Рассуждения:

Предположим, есть строка вида

ABBCDDABBFDBCBDFBEBEEBADF

Если убрать символы B, E, F (скажем, заменить их на символ *), останутся подстроки, подходящие под условие:

ABBCDDABBFDBCBDFBEBEEBADF

A**CDDA***D*C*D*******AD*

Осталось только убрать звёздочки и найти строку максимальной длины.

Решение:

Задача 4.

Текстовый файл содержит строку из заглавных латинских букв X, Y и Z. Определите максимальное количество идущих подряд троек символов ZXY или ZYX. 

Рассуждения: 

Заменим подходящие тройки символов на *, а затем каждый из символов на #. То есть, строка вида

будет преобразована в строку ***##*

Разделив по #, получим подстроки, удовлетворяющие условию.

Останется лишь найти длину максимальной из них.

Решение:

Как понять, что удобно воспользоваться именно этим методом?

• Из условия задачи становятся понятно, что некоторые символы лишние и, если их удалить, получить ответ очень легко
• Необходимо «разбить» тройки или пары символов (задача вида «найдите длину максимальной подстроки, в которой нет сочетания символов «...»)

Важно: С осторожностью стоит использовать метод replace, если необходимо заменять симметричную подстроку. Могут быть заменены не все ее вхождения, и, чтобы исправить это, воспользуемся следующей конструкцией:

#4 Метод «count»

Метод count позволяет узнать количество вхождений указанной подстроки или элемента в строке.

Задача 5.

Текстовый файл состоит из символов S, T, O, C, K. Сколько раз встречается в файле комбинация «KOT»?

Решение:

Задача 6.

Определите максимальное количество идущих подряд символов, среди которых нет точек, но есть не менее 3-х букв A 

Решение:

#5 Срезы

С элементами строк удобно работать, используя срезы.

С их помощью можно не только сформировать подстроку из n подряд идущих символов, но и сделать реверс строки.

Предположим, есть строка:

Стоит помнить, что правая граница среза не включается.

Осуществить реверс строки позволяет следующая конструкция:

Задача 7.

Определите количество палиндромов (последовательностей, которые читаются в обе стороны одинаково) длиной 5 символов.

Рассуждения: для каждой пятёрки подряд идущих чисел проверим, совпадает ли её запись справа налево и слева направо 

Решение:

Задача 8.

Текстовый файл состоит из символов S, T, O, C, K.

Сколько раз встречается в файле комбинация «SOCKS»? 

Решение:

#6 Словари

Есть ряд 24 задач вида «определите, какой символ/подстрока в файле встречается чаще/реже всего».

Такие задания удобно решать с использованием частотного словаря.

Задача 9.

Определите символ, который чаще всего встречается в файле перед двумя одинаковыми символами. Например, в тексте CCBAABABBCCC есть комбинации BAA, ABB, BCC и CCC. Чаще всего – 2 раза – перед двумя одинаковыми символами стоит B, в ответе для этого случая надо написать B2 (без пробелов и других разделителей). Если таких символов несколько, выведите тот, который стоит раньше в алфавите. 

Рассуждения: выясним, сколько раз перед двумя одинаковыми символами встречается каждый из допустимых элементов. Для этого создадим частотный словарь и рассмотрим всевозможные тройки подряд идущих элементов строки.

Решение:

Задача 10.

Текстовый файл содержит строку из заглавных букв A, B, C, D, E, F. Определите, сколько встречается комбинаций вида CB*BC, где на месте "*" может стоять любая буква, кроме A, B и F. В ответе укажите сначала букву, которая чаще всего встречается на месте "*", затем общее количество подходящих комбинаций. 

Рассуждения: как и в предыдущей задаче, проверим все пятерки подряд идущих элементов и, если первые два и последние два подходят под условие, будем обновлять статистику для элемента с индексом i+2.

Решение:

Ссылки на полезную документацию:

Методы работы со строками - https://pythonru.com/osnovy/strokipython

Метод replace - https://pythoninfo.ru/osnovy/replace-python

Метод split - https://pythonstart.ru/string/metod-str-split-python

Метод count - https://pythonstart.ru/string/metod-count-python

Работа со словарями - https://pythonru.com/osnovy/python-dict

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

L - левый указатель    

R - правый указатель     

Причём L <= R     

Пусть L будет отвечать за начало фрагмента, a R - за конец фрагмента     

В этом случае мы сможем определить длину фрагмента (подстроки) как разность     указателей: R - L+ 1    

Фрагмент от L. до R будем называть "хорошим",  если он подходит под наши условия.     Сдвигать L будем вперед до тех пор, пока "плохой" отрезок снова не станет "хорошим"    

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ Y встречается не более 2 раз.
Для выполнения этого задания следует написать программу.

s = 'BYCDYVYWXYZ'
k = 0  # здесь я буду хранить, сколько раз встречается Y на фрагменте от L до R
l = 0  # левый указатель (описывает начало фрагмента)
m = 0  # максимальная длина подходящего фрагмента
for r in range(len(s)):  # сдвигаю правую границу на 1
    if s[r] == 'Y':  # включил еще один Y во фрагмент - учел это
        k += 1
    while k > 2:  # сдвигаю левую границу до тех пор, пока фрагмент не станет "хорошим"
        if s[l] == 'Y':  # _ убрал один Y из фрагмента
            k -= 1
        l += 1  # сдвигаю левую границу
    # в этом месте  понимаю, что мой подотрезок "хороший"
    m = max(m, r - l + 1)
print(m)

s = "12345689012345678912345678901234567890"
b = float('inf')
s = s.replace("0"," ")
s = s.split()
print(s)
for i in s:
    if i.count('7') >= 2:
        b = min(b, len(i))
print(b)
print("=================================")

# and

s = "12345689012345678912345678901234567890"
for i in range(len(s)):
    print(i, "=", s[i], end = " ")
print()
k = l = 0
m = float("inf")
for r in range(len(s)):
    if s[r] == '7':
        k += 1
    if s[r] == '0':
        l = r + 1
        k = 0
    while k >= 2:
        print("s[r] =",s[r],"r =", r, "s[l] =", s[l], "l =", l, end = "\n")
        #input()
        m = min(m, r - l + 1)
        if s[l] == '7':
            k -= 1
        l += 1
print(m)

Ссылка на файлы для заданий 24

print(ord("0"), ord("A"),ord("B"), ord("b"),ord("!"))
print("a">"B") # индекс элемента