Soma aninhada ponderada por profundidade
A missão
Problema
Uma lista contém inteiros e outras listas, aninhadas em qualquer profundidade. Os itens da lista externa ficam na profundidade 1, os itens de uma lista dentro dela na profundidade 2, e assim por diante. Retorne a soma de cada inteiro multiplicado pela profundidade em que ele está.
Exemplos
Input: items = [[1, 1], 2, [1, 1]]
Output: 10
Por quê: quatro números 1 na profundidade 2 dão 8, e o 2 na profundidade 1 dá 2
Input: items = [1, [4, [6]]]
Output: 27
Por quê: 1 * 1 + 4 * 2 + 6 * 3
Input: items = [[[]]]
Output: 0
Por quê: edge case: um aninhamento profundo sem inteiros não soma nada
Dicas
0 / 3
Cada inteiro precisa de um fato extra que não está escrito ao lado dele: quantas listas o envolvem.
Esse fato é conhecido na descida, não na volta. Um parâmetro pode levá-lo de cada chamada para as chamadas que ela faz.
Escreva uma função que recebe uma lista e a profundidade dela. Percorra os itens: some um inteiro vezes a profundidade e, para uma lista aninhada, some o resultado de chamar a função sobre ela com a profundidade mais um. Comece a chamada externa na profundidade 1.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(d)
Restrições
- items are integers or lists, nested to any depth
Solução
A profundidade de um inteiro é decidida inteiramente pelo caminho da lista externa até ele; é uma informação que flui para baixo, o que a torna um parâmetro, e não um valor de retorno. Cada chamada soma os próprios inteiros ponderados pela profundidade que recebeu e passa a profundidade mais um para as listas dentro dela, enquanto as somas parciais sobem de volta como valores de retorno. Uma lista vazia simplesmente retorna zero. Cada inteiro e cada lista é visitado uma vez, então o tempo é O(n) no número total de itens, e a pilha de chamadas (call stack) é tão profunda quanto o aninhamento.
def weighted_sum(items, depth=1):
total = 0
for item in items:
if isinstance(item, list):
total += weighted_sum(item, depth + 1) # depth travels down
else:
total += item * depth # sums travel back up
return total
print(weighted_sum([[1, 1], 2, [1, 1]])) # -> 10
print(weighted_sum([1, [4, [6]]])) # -> 27
print(weighted_sum([[[]]])) # -> 0Travou na ideia, e não no código? Retornar para cima ou passar para baixo explica isso.