Derinlik ağırlıklı iç içe toplam
Görev tanımı
Problem
Bir liste tam sayılar ve herhangi bir derinlikte iç içe geçmiş başka listeler tutuyor. Dış listedeki öğeler 1. derinlikte, onun içindeki bir listedeki öğeler 2. derinlikte duruyor ve böyle devam ediyor. Her tam sayının bulunduğu derinlikle çarpımlarının toplamını döndür.
Örnekler
Input: items = [[1, 1], 2, [1, 1]]
Output: 10
Neden: 2. derinlikteki dört tane 1, 8 eder; 1. derinlikteki 2 de 2 eder
Input: items = [1, [4, [6]]]
Output: 27
Neden: 1 * 1 + 4 * 2 + 6 * 3
Input: items = [[[]]]
Output: 0
Neden: edge case: tam sayı olmayan derin iç içelik hiçbir şey eklemez
İpuçları
0 / 3
Her tam sayının yanında yazmayan fazladan bir bilgiye ihtiyacı var: onu kaç listenin çevrelediği.
Bu bilgi geri dönerken değil, aşağı inerken bilinir. Bir parametre onu her çağrıdan yaptığı çağrılara taşıyabilir.
Bir liste ve derinliğini alan bir fonksiyon yaz. Öğeler üzerinde döngü kur: bir tam sayı çarpı derinliği ekle, iç içe bir liste için de fonksiyonu onun üzerinde derinlik artı birle çağırmanın sonucunu ekle. Dış çağrıyı 1. derinlikte başlat.
- Hedef zaman
- O(n)
- Hedef alan
- O(d)
Kısıtlar
- items are integers or lists, nested to any depth
Çözüm
Bir tam sayının derinliği tamamen dış listeden ona inen yolla belirlenir; yani aşağı doğru akan bir bilgidir, bu da onu bir dönüş değeri değil bir parametre yapar. Her çağrı kendi tam sayılarını kendisine verilen derinlikle ağırlıklandırarak ekler ve içindeki listelere derinlik artı bir geçirir; kısmi toplamlar da dönüş değerleri olarak yukarı akar. Boş bir liste basitçe sıfır döndürür. Her tam sayı ve her liste bir kez ziyaret edilir; toplam öğe sayısında zaman O(n), call stack de iç içelik kadar derindir.
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([[[]]])) # -> 0Kodda değil de fikirde mi takıldın? Yukarı döndür ya da aşağı aktar bunu anlatıyor.