Написание рекурсивной функции, которая возвращает цифру с самой длинной последовательной последовательностью

Как написать рекурсивную функцию, которая принимает значение int и возвращает цифру с самой длинной последовательной последовательностью?

Например, f(1122333) возвращает 3, а f(1223) возвращает 2

Я понятия не имею, как подойти к этой проблеме, и я как бы новичок в рекурсии вообще.

    Что-то вроде этого. Не испытано. Было интересно подумать.

    Псевдокод:

    (Предполагает целочисленное деление)

     Def number helperLongest(number myNum): Return longest(myNum, -1, 0, -1, 0) Def number longest(number myNum,number prevLongest, number numOfPrevLong, number currentLongest,number numOfLongest): If (myNum/10 < 1) //base case If (myNum == currentLongest) numOfLongest++ Else //deal with corner case of < 10 input If (numOfLongest > numOfPrevLong) prevLongest = currentLongest numOfPrevLongest = numOfLongest currentLongest = myNum numOfLongest = 1 return (numOfLongest>numOfPrevLong)?currentLongest:prevLongest Else //recurse if(myNum%10 == currentLongest) numOfLongest++; Else //have to break the chain if (numOfLongest > numOfPrevLongest) prevLongest = currentLongest numOfPrevLongest = numOfLongest currentLongest = myNum%10 numOfLongest = 1 myNewNum = myNum/10; return longest(myNewNum,prevLongest,numOfPrevLong,currentLongest,numberOfLongest); 

    В словах: пройдите цифру по цифре, начиная с конца. Если текущая последняя цифра соответствует предыдущей, увеличьте счетчик. Если это не так, и оно больше предыдущего максимума, сохраните его. Сбросьте текущую цифру до текущей последней цифры и сбросьте счетчик. Отрежьте последнюю цифру. Подайте меньшее число и всю эту информацию обратно в функцию до тех пор, пока вы не перейдете к одной последней цифре (первая цифра в исходном номере). Сравните текущий счетчик с максимальным сохранением и верните большую.

    Одна заметка: в случае привязки будет возвращена первая подстрока совпадающих чисел (которая фактически является последней подстрокой в ​​исходном числе). Если требуется другое поведение, замените два > с >= .

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

    Другими словами, с любым рекурсивным алгоритмом вам нужен базовый случай, в котором мы остановимся и что-то вернем, и рекурсивный случай, когда нам нужно вызвать функцию с измененными входами.

    Основной случай – это когда мы предоставляем число с одной цифрой. Это означает, что мы достигли конца номера. Если это так, нам нужно проверить, соответствует ли это значение текущему значению, которое в настоящее время считается последовательным. Если это значение соответствует, мы увеличиваем текущий последовательный счет на 1. Если это значение превысит текущий самый длинный последовательный счет, мы вернем эту цифру как число, которое относится к самой длинной последовательной последовательности. Если нет, мы просто возвращаем то, что это значение, прежде чем мы решили сделать эту проверку.

    Рекурсивный случай немного сложнее. Учитывая цифру, на которую мы смотрим, мы проверяем, равна ли эта цифра цифре, которая рассматривается как часть последовательного потока. Если это так, увеличьте количество этой цифры на 1, и мы проверим, превышает ли этот счет больше текущего наибольшего последовательного счета. Если это так, нам нужно обновить текущее самое длинное значение до этого значения, а также обновить самый длинный счетчик. Если это не соответствует, мы возвращаем счетчик в 1 , так как это первая цифра такого типа, с которой нужно столкнуться. Текущее значение будет соответствовать этому значению, и мы рекурсируем, где мы отправляем список значений, начиная со второго индекса, с другими обновленными переменными.

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

    Без лишнего шума это то, что я написал. Функция называется longest_consecutive_value и принимает целое число:

     # Function that determines the value that has the longest consecutive sequence def longest_consecutive_value(value): # Recursive function def longest_recursive(list_val, current_val, current_longest_val, longest_count, count): # Base case if len(list_val) == 1: # If single digit is equal to the current value in question, # increment count if list_val[0] == current_val: count += 1 # If current count is longer than the longest count, return # the single digit if count > longest_count: return list_val[0] # Else, return the current longest value else: return current_longest_val # Recursive case else: # If the left most digit is equal to the current value in question... if list_val[0] == current_val: # Increment count count += 1 # If count is larger than longest count... if count > longest_count: # Update current longest value current_longest_val = list_val[0] # Update longest count longest_count = count # If not equal, reset counter to 1 else: count = 1 # Current value is the left most digit current_val = list_val[0] # Recurse on the modified parameters return longest_recursive(list_val[1:], current_val, current_longest_val, longest_count, count) # Set up - Convert the integer into a list of numbers list_num = map(int, str(value)) # Call private recursive function with initial values return longest_recursive(list_num, list_num[0], list_num[0], 0, 0) 

    Вот несколько примеров (с использованием IPython):

     In [4]: longest_consecutive_value(1122333) Out[4]: 3 In [5]: longest_consecutive_value(11223) Out[5]: 1 In [6]: longest_consecutive_value(11223334444555555) Out[6]: 5 In [7]: longest_consecutive_value(11111111122) Out[7]: 1 In [8]: longest_consecutive_value(1122334444) Out[8]: 4 

    Обратите внимание, что если есть несколько цифр, которые имеют одинаковое количество последовательных номеров, то выводится только первое число, которое произвело эту длину последовательных чисел. Как отметил Рон Томпсон на своем посту, если вы хотите, чтобы последняя или последняя последовательная цифра удовлетворяла требованиям, используйте >= вместо > при проверке счетчиков.