Имеется текстовый файл, содержащий только цифры от 0 до 9. Требуется найти в нём самую длинную последовательность идущих подряд символов, в которой встречается не более трёх различных цифр, и определить, из каких символов она состоит. Если таких последовательностей несколько, выбирайте ту, что ближе к началу файла. В качестве ответа следует ввести 4 числа, разделённые пробелами: длину найденной последовательности и входящие в неё цифры в порядке возрастания. Например, для файла 247670705324423901 ответ будет таким 6067 Для небольшого файла: Для довольно большого файла:
Ответы
Ответ:
max_length = -1
digits_in_max_subseq = []
current_subseq, current_length = dict(), 0
with open("input.txt") as f:
for i, ch in enumerate(f.read()):
if ch not in current_subseq and len(current_subseq) == 3:
if current_length > max_length:
max_length = current_length
digits_in_max_subseq = list(current_subseq.keys())
items = sorted(current_subseq.items(), key=lambda item: item[1])
del current_subseq[items[0][0]]
current_length = i - items[0][1] - 1
current_subseq[ch] = i
current_length += 1
else:
items = sorted(current_subseq.items(), key=lambda item: item[1])
if len(items) == 1:
max_length = current_length
digits_in_max_subseq = [items[0][0]]
elif current_length > max_length:
max_length = current_length
digits_in_max_subseq = list(current_subseq.keys())
print(max_length, *sorted(digits_in_max_subseq))
Объяснение:
Указание на то, что файл может быть достаточно большим, намекает, что всю последовательность хранить в памяти не следует. Будем читать её посимвольно, поддерживая не более трёх последних встретившихся цифр, то, когда они последний раз встретились и текущую длину. Для определения самой длинной подпоследовательности также сохраним текущую максимальную длину подпоследовательности и цифры, из которых она состоит.
При чтении очередного символа могут возникнуть три ситуации:
1) Этот символ нам раньше не встречался, но мы пока сохранили меньше трёх цифр. Тогда сохраняем этот символ, записываем его место, увеличиваем текущую длину на 1.
2) Этот символ — один из тех, что мы сохранили. Тогда текущая подпоследовательность продолжается, записываем новое место этого символа, увеличиваем текущую длину на 1.
3) Этот символ не один из трёх сохраненных. Тогда текущая подпоследовательность окончена, сравниваем её с текущей максимальной (если она длиннее — обновляем максимум). Затем выкидываем из текущей подпоследовательности цифру, которая встретилась дальше всего, обновляем текущую длину и запоминаем новую цифру и её место.
В конце не забываем проверить подпоследовательность, которая содержит последнюю цифру.
Пример:
Пусть текущая подпоследовательность длины 17 содержит 3 различные цифры: 1 (последний раз встретилась на месте с номером 100), 2 (103) и 3 (104). Новая цифра 4, она расположена на 110 месте.
Это третий случай, нам надо обновить текущий максимум и записать новую цифру.
— до обновления длина подпоследовательности была равна 17. Сравниваем эту длину с максимальной, если она меньше — обновляем максимум
— самая давно встретившаяся цифра — 1. Если её отбросить, то начиная с символа с номером 101 и до 110 будет подпоследовательность, содержащая только 2, 3 и 4. Соответственно, меняем 1 на 4, запоминаем, что 4 встретилась в последний раз на 110 месте, и записываем новую текущую длину 110 - 100.
Программа на языке python приведена выше. Предполагается, что последовательность записана в файле input.txt и не содержит никаких других символов, кроме цифр.
#SPJ1