Achatar uma lista aninhada
A missão
Problema
Você recebe uma lista cujos itens são inteiros ou outras listas, aninhadas em qualquer profundidade. Retorne uma única lista plana com todos os inteiros, na ordem em que aparecem quando você lê a estrutura da esquerda para a direita. Listas vazias não contribuem com nada.
Exemplos
Input: items = [1, [2, [3, 4]], 5]
Output: [1, 2, 3, 4, 5]
Por quê: a profundidade não muda a ordem de leitura
Input: items = [[], [[]], [1]]
Output: [1]
Por quê: listas vazias em qualquer profundidade desaparecem
Input: items = []
Output: []
Por quê: edge case: não há absolutamente nada para ler
Dicas
0 / 3
Olhe para um único item em vez da estrutura inteira. Só existem dois tipos de item, e um deles é fácil.
Uma lista aninhada é o mesmo problema em miniatura. A função que resolve a lista externa já resolve a interna.
Percorra os itens uma vez. Acrescente um inteiro direto ao resultado; para uma lista, chame a função sobre ela e estenda o resultado com o que voltar. A lista vazia é o caso base natural.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- items are integers or lists, nested to any depth
Solução
Cada item é um valor a guardar ou uma cópia menor do mesmo problema, que é exatamente o formato para o qual a recursão existe. Percorrer os itens em ordem preserva a ordem de leitura, e estender o resultado com o sub-resultado deixa o aninhamento invisível na saída. A lista vazia não precisa de tratamento especial: o loop simplesmente nunca roda. Cada inteiro e cada nó de lista é visitado uma vez, então o tempo é O(n) no número total de nós, e a pilha de chamadas (call stack) fica tão profunda quanto o aninhamento.
def flatten(items):
flat = []
for item in items:
if isinstance(item, list):
flat.extend(flatten(item)) # a nested list is a smaller problem
else:
flat.append(item)
return flat
print(flatten([1, [2, [3, 4]], 5])) # -> [1, 2, 3, 4, 5]
print(flatten([[], [[]], [1]])) # -> [1]
print(flatten([])) # -> []Travou na ideia, e não no código? O básico de recursão explica isso.