Termo da sequência look-and-say
A missão
Problema
A sequência look-and-say começa com “1”. Cada termo seguinte é formado lendo o termo anterior em voz alta, em sequências de dígitos iguais: “1” é um 1, o que dá “11”; “11” são dois 1, o que dá “21”; “21” é um 2 e depois um 1, o que dá “1211”. Dado n de pelo menos 1, retorne o n-ésimo termo como string.
Exemplos
Input: n = 4
Output: "1211"
Input: n = 5
Output: "111221"
Por quê: "1211" se lê como um 1, um 2, dois 1
Input: n = 1
Output: "1"
Por quê: edge case: o primeiro termo já é dado, não há nada a descrever
Dicas
0 / 3
O n-ésimo termo é definido inteiramente a partir do termo anterior. Esse é exatamente o formato de uma definição recursiva.
O caso base é n igual a 1. Para qualquer n maior, primeiro obtenha o termo n − 1 e depois descreva-o.
Para descrever uma string, percorra-a em sequências: a partir do início de uma sequência, avance enquanto o dígito continuar o mesmo, depois escreva o tamanho da sequência seguido do dígito e continue de onde a sequência terminou.
- Tempo-alvo
- O(1.31ⁿ)
- Espaço-alvo
- O(1.31ⁿ)
Restrições
- n ≥ 1
Solução
A definição já é recursiva: o termo 1 é “1”, e o termo n é a descrição do termo n − 1. Descrever uma string significa dividi-la em sequências de dígitos iguais e escrever cada sequência como o seu tamanho seguido do dígito, o que uma passada com dois índices resolve. A recursão tem n níveis de profundidade, o que não é problema para os valores pequenos de n usados com esta sequência, já que os termos crescem cerca de um terço a cada passo. O tempo e o espaço são proporcionais ao tamanho total dos termos produzidos, dominado pelo tamanho do n-ésimo termo.
def look_and_say(n):
if n == 1:
return "1" # base case
prev, out, i = look_and_say(n - 1), [], 0
while i < len(prev):
j = i
while j < len(prev) and prev[j] == prev[i]:
j += 1 # extend the run of prev[i]
out.append(str(j - i) + prev[i]) # count, then digit
i = j
return "".join(out)
print(look_and_say(4)) # -> 1211
print(look_and_say(5)) # -> 111221
print(look_and_say(1)) # -> 1
print(look_and_say(8)) # -> 1113213211Travou na ideia, e não no código? O básico de recursão explica isso.