Look-and-say dizisinin terimi
Görev tanımı
Problem
Look-and-say dizisi "1" ile başlıyor. Sonraki her terim, önceki terimi eşit rakam blokları halinde sesli okuyarak yapılıyor: "1" bir tane 1'dir, "11" verir; "11" iki tane 1'dir, "21" verir; "21" bir tane 2 sonra bir tane 1'dir, "1211" verir. En az 1 olan n verildiğinde, n. terimi bir string olarak döndür.
Örnekler
Input: n = 4
Output: "1211"
Input: n = 5
Output: "111221"
Neden: "1211" bir tane 1, bir tane 2, iki tane 1 diye okunur
Input: n = 1
Output: "1"
Neden: edge case: ilk terim verilmiş, tarif edilecek bir şey yok
İpuçları
0 / 3
n. terim tamamen kendisinden önceki terimle tanımlanır. Bu tam olarak özyinelemeli bir tanımın şekli.
Temel durum, n'in 1'e eşit olması. Daha büyük her n için önce n eksi 1. terimi al, sonra onu tarif et.
Bir string'i tarif etmek için onu bloklar halinde dolaş: bir bloğun başından rakam aynı kaldıkça ilerle, sonra bloğun uzunluğunu ve ardından rakamı yaz ve bloğun bittiği yerden devam et.
- Hedef zaman
- O(1.31ⁿ)
- Hedef alan
- O(1.31ⁿ)
Kısıtlar
- n ≥ 1
Çözüm
Tanım zaten özyinelemeli: 1. terim "1"dir, n. terim de n eksi 1. terimin tarifidir. Bir string'i tarif etmek onu eşit rakam bloklarına bölmek ve her bloğu uzunluğu ve ardından rakam olarak yazmaktır; bunu iki indeksli tek bir geçiş yapar. Özyineleme (recursion) n seviye derindir; bu dizinin kullanıldığı küçük n'ler için sorun değil, çünkü terimler her adımda kabaca üçte bir büyür. Zaman ve alan üretilen terimlerin toplam uzunluğuyla orantılıdır; buna da n. terimin uzunluğu baskındır.
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)) # -> 1113213211Kodda değil de fikirde mi takıldın? Özyineleme temelleri bunu anlatıyor.