Как найти максимальную последовательность обеих значений?
Задача:
У вас есть последовательность бросков монеты. Каждый бросок записан в массиве. Вам необходимо вычислить самую длинную последовательность из орлов и самую длинную последовательность из решек
пример входных данных: ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
пример выходных: Самая длинная последовательность решек: 4 Самая длинная последовательность орлов: 3
я нашел только 1 решение и то оно на javascript - https://www.youtube.com/watch?v=9QxC__IU6jM
мой код: он не полный
n = ['орел', 'орел', 'решка', 'решка', 'орел', 'решка', ]
countR = []
countO = []
for i in n:
if i == 'орел':
countO.append(1)
elif i == 'решка':
countR.append(1)
print(len(countO), len(countR))
Ответы (3 шт):
можно решить в лоб, как тестовая задача - очень неплохая
в вашем случае вы приводите неправильный код - он подсчитывает только общее кол-во орлов и решек, вам же нужно определять, что последовательность только орлов закончена и считать результат, т.е. в вашем случае код надо было бы дополнить:
countR = []
countO = []
for i in n:
if i == 'орел':
# считаем длину countR И если она больше максимальной - запоминаем
# сбрасываем массив countR в 0
countO.append(1)
elif i == 'решка':
# считаем длину countL И если она больше максимальной - запоминаем
# сбрасываем массив countL в 0
countR.append(1)
но тут вопрос такой - а зачем вам тогда вообще массивы, если вы можете считать кол-во через переменную?
а можно мыслить чуть нестандартно и тогда можно делать однострочные развраты
n = ['орел', 'орел', 'решка', 'решка', 'орел', 'решка', ]
print(max(map(len, ''.join(map(lambda key: {'орел': '*', 'решка': '+'}.get(key, '*'), n)).split('*'))))
одна строчка для орлов и решек:
res = max(map(len, ''.join(map(lambda key: {'орел': '*', 'решка': '+'}.get(key, '*'), n)).split('*'))), max(map(len, ''.join(map(lambda key: {'орел': '*', 'решка': '+'}.get(key, '+'), n)).split('+')))
ну или если поджать:
res = [max(map(len, ''.join(map(lambda key: {'орел': '*', 'решка': '+'}.get(key, i), n)).split(i))) for i in ('*', '+')]
Если решать в лоб, то надо завести две переменные: heads_ending_here - число орлов подряд до этого места в списке и max_heads_so_far - максимальное число орлов подряд до сих пор.
Если встретился орёл, то heads_ending_here увеличивается на единицу, иначе сбрасывается в ноль.
Каждый раз когда heads_ending_here растёт надо обновить max_heads_so_far.
В начале цикла обе переменные нулевые. В конце в max_heads_so_far будет нужный вам ответ.
tosses = ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
max_heads_so_far = 0
heads_endging_here = 0
for t in tosses:
if t == 'орел':
heads_endging_here += 1
if heads_endging_here > max_heads_so_far:
max_heads_so_far = heads_endging_here
else:
heads_endging_here = 0
print('орлы', max_heads_so_far)
Добавим решки:
tosses = ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
max_heads_so_far = 0
max_tails_so_far = 0
heads_endging_here = 0
tails_endging_here = 0
for t in tosses:
if t == 'орел':
heads_endging_here += 1
if heads_endging_here > max_heads_so_far:
max_heads_so_far = heads_endging_here
tails_endging_here = 0
if t == 'решка':
heads_endging_here = 0
tails_endging_here += 1
if tails_endging_here > max_tails_so_far:
max_tails_so_far = tails_endging_here
print('орлы', max_heads_so_far)
print('решки', max_tails_so_far)
Решения выше не используют возможности стандартной библиотеки Питона. А в ней есть itertools.groupby который хорошо подходит к задаче. groupby сам нарезает список на группы одинаковых элементов, нам нужно только посчитать длины групп и обновить максимумы:
import itertools
tosses = ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
max_heads_so_far = 0
max_tails_so_far = 0
for t, group in itertools.groupby(tosses):
group_length = sum(1 for _ in group)
if t == 'орел':
if group_length > max_heads_so_far:
max_heads_so_far = group_length
if t == 'решка':
if group_length > max_tails_so_far:
max_tails_so_far = group_length
print('орлы', max_heads_so_far)
print('решки', max_tails_so_far)
Меня беспокоит в коде выше дублирование. Две переменные для максимумов обрабатываются совершенно одинаково. Исправим это - заведем словарь, который хранит текущие максимумы. Вот так:
import itertools
tosses = ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
maxima_so_far = {'орел': 0, 'решка': 0}
for t, group in itertools.groupby(tosses):
group_length = sum(1 for _ in group)
if group_length > maxima_so_far[t]:
maxima_so_far[t] = group_length
for t, m in maxima_so_far.items():
print(t, m)
Последний штрих - избавимся от фиксированной структуры словаря. Пусть записи добавляются только при необходимости. Вместо обращения dict[key] используем dict.get(key, 0). Если ключа в словаре ещё нет, вернётся ноль. То что нужно. Теперь код сможет обрабатывать списки с любыми значениями:
import itertools
tosses = ['орел', 'орел', 'решка', 'орел', 'решка', 'решка', 'решка', 'решка']
maxima_so_far = {}
for t, group in itertools.groupby(tosses):
group_length = sum(1 for _ in group)
if group_length > maxima_so_far.get(t, 0):
maxima_so_far[t] = group_length
for t, m in maxima_so_far.items():
print(t, m)
добавлю в копилку еще одно решение (бонусом выводит еще и длину минимальной последовательности):
n = ['орел', 'орел', 'орел', 'решка', 'решка', 'орел', 'решка', 'решка', 'решка']
d = {'орел':[0], 'решка':[0]}
s = []
for i in n + ['end']:
if s and i not in s:
d[s[0]].append(len(s))
s.clear()
s.append(i)
print(f'MAX: орел {max(d["орел"])}, решка {max(d["решка"])}')
print(f'MIN: орел {min(d["орел"])}, решка {min(d["решка"])}')
результат:
MAX: орел 3, решка 3
MIN: орел 1, решка 2
код работает достаточно просто:
Проходим циклом по списку бросков n, записываем в список s какая сторона монеты выпала до тех пор пока не выпадет противоположная сторона. Когда выпадает другая сторона, записываем в соответствующий список словаря d длину списка s и очищаем список s. Итого, в словаре d имеем списки длин всех последовательностей орлов и решек. Стандартной функцией max находим длины наибольших (заодно можем и наименьших).
Чтобы в цикле не потерялась последняя последовательность бросков, к списку n добавлено значение 'end'.