Как проверить наибольшее количество одинаковых элементов рядом друг с другом?

#python #algorithm

#python #алгоритм

Вопрос:

Итак, у меня есть строка, которая содержит ТОЛЬКО 0 и 1. Что я хочу сделать, так это проверить наименьшее количество одинаковых элементов рядом друг с другом, поэтому, когда это число ‘01010011’ = 2 (два раза по 1 и два раза по 0), когда число ‘0101010’ = 1, когда число ‘01111111000000111100000101000011111’ = 4 и т.д. Еще одна вещь, которую я могу предположить — всегда будет одинаковое наименьшее число 0 и 1. Это то, что я пробовал, но это не работает:

 bits = '1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011'

y = 0
x = 100
for i in range(len(bits) - 1):
    if list(bits[i]) == list(bits[i 1]) and list(bits[i]) == ["1"]:
        if y == 0 and x > 1:
            y  = 2
            x = 99
        else:
            y  = 1
    elif x == 100 and ["1"] in (list(bits[i]), list(bits[i 1])):
        x = 1
        break
    else:
        if 0 < x > y > 0:
            x = y
        y = 0

1. Вы имели в виду только 0 и 1 с (вместо 1 и 2 с)? Кроме того, «‘010111100010000111’ number = 4» не совсем, есть 3 0 и 3 1?

2. Да, я не знаю, почему я сказал 1 и 2. И вы правы во втором, у меня был удар или что-то в этом роде во время написания этого

Ответ №1:

Если его только 0 и 1:

 len(max(max(bits.split('0'),  key=len), max(bits.split('1'), key=len), key=len))

Сложность во времени и пространстве O(N) .

Идея разделения на основе ‘0’, а затем ‘1’ довольно очевидна. Это даст вам два списка, в которых есть смежные 0 и пустые строки, а также 1 и пустые строки соответственно. Мы берем самый большой len из обоих списков.

Я опубликовал приведенный выше ответ только потому, что нахожу его забавным 1-liner. Вы можете / должны улучшить сложность пространства, O(1) т. Е.

Перебор строки
Увеличение локальной переменной на количество одинаковых символов, виденных до сих пор, и обновление максимального значения, видимого в процессе
Сброс локального счетчика при обнаружении другого символа, т.е. при разрыве непрерывности.

Ответ №2:

Есть забавное решение с использованием регулярных выражений:

 import re
min(map(len, re.findall(r'0{2,}|1{2,}', bits)))

Объяснение:

0{2,} находит все подстроки с 2 последовательными 0 или более
1{2,} находит все подстроки с 2 последовательными 1 или более
0{2,}|1{2,} находит любой из этих критериев
re.findall возвращает все найденные последовательные цифры в списке
map(len, lst) применяет len функцию к каждому элементу в списке lst
min находит наименьшее значение, то есть длину самой короткой найденной строки из последовательных цифр.