İç içe listeyi düzleştir
Görev tanımı
Problem
Sana öğeleri ya tam sayı ya da herhangi bir derinlikte iç içe geçmiş başka listeler olan bir liste veriliyor. Yapıyı soldan sağa okurken göründükleri sırayla her tam sayıyı tutan tek bir düz liste döndür. Boş listeler hiçbir katkı yapmaz.
Örnekler
Input: items = [1, [2, [3, 4]], 5]
Output: [1, 2, 3, 4, 5]
Neden: derinlik okuma sırasını değiştirmez
Input: items = [[], [[]], [1]]
Output: [1]
Neden: herhangi bir derinlikteki boş listeler kaybolur
Input: items = []
Output: []
Neden: edge case: okunacak hiçbir şey yok
İpuçları
0 / 3
Bütün yapıya değil, tek bir öğeye bak. Yalnız iki tür öğe var ve biri kolay.
İç içe bir liste aynı problemin minyatürüdür. Dış listeyi çözen fonksiyon içtekini zaten çözer.
Öğeleri bir kez dolaş. Bir tam sayıyı doğrudan sonuca ekle; bir liste için fonksiyonu onun üzerinde çağır ve dönenle sonucu genişlet. Boş liste doğal temel durumdur.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- items are integers or lists, nested to any depth
Çözüm
Her öğe ya tutulacak bir değerdir ya da aynı problemin daha küçük bir kopyası; özyinelemenin (recursion) tam olarak işlendiği şekil de bu. Öğeleri sırayla dolaşmak okuma sırasını korur, alt sonuçla genişletmek de iç içeliği çıktıda görünmez tutar. Boş liste özel bir durum gerektirmez: döngü basitçe hiç çalışmaz. Her tam sayı ve her liste düğümü bir kez ziyaret edilir; toplam düğüm sayısında zaman O(n), stack de iç içelik kadar derine iner.
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([])) # -> []Kodda değil de fikirde mi takıldın? Özyineleme temelleri bunu anlatıyor.