Yan yana 1 olmayan ikili string'ler
Görev tanımı
Problem
Bir n uzunluğu verildiğinde, o uzunluktaki ve hiçbir iki 1'in yan yana durmadığı her ikili string'i döndür. String'leri artan sırada döndür.
Örnekler
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Neden: 011, 110 ve 111'in her biri iki 1'i yan yana koyuyor
Input: n = 1
Output: ["0", "1"]
Input: n = 0
Output: [""]
Neden: edge case: boş string, sıfır uzunluktaki tek string
İpuçları
0 / 3
2 üzeri n string'in hepsini üretip elemek, kuralı daha ikinci karakterde bozmuş string'lere iş harcar. Kötü bir string'i bozulduğu anda durdurabilir misin?
String'i karakter karakter kur. Her konumda seçenekler 0 ve 1; 1'e yalnız önceki karakter 1 değilse izin var.
0 ekleyip özyineleyen ve onu geri çıkaran, sonra yalnız string boşsa ya da 0 ile bitiyorsa 1 ekleyip özyineleyen ve onu geri çıkaran özyinelemeli bir yardımcı yaz. 0'ı 1'den önce denemek string'leri artan sırada üretir.
- Hedef zaman
- O(n · 1.62ⁿ)
- Hedef alan
- O(n · 1.62ⁿ)
Çözüm
Her konum karar ağacında 0 ve 1 olmak üzere iki dallı bir seviyedir; kural da önceki karakter zaten 1 olduğunda 1 dalını budar. Budanmış bir dal hiç keşfedilmez, bu yüzden aramanın ulaştığı her yaprak geçerli bir string'dir ve sonradan hiçbir şey elenmez. Her seviyede 0'ı 1'den önce denemek yaprakları artan sırada ziyaret eder. Geçerli string sayısı Fibonacci sayıları gibi büyür ve her birini birleştirmek O(n) tutar; zaman O(n · F(n + 2)), özyineleme (recursion) de çıktı dışında O(n) ek alan kullanır.
def no_adjacent_ones(n):
result, path = [], []
def build():
if len(path) == n:
result.append("".join(path))
return
path.append("0")
build()
path.pop()
if not path or path[-1] == "0": # prune: a 1 may not follow a 1
path.append("1")
build()
path.pop()
build()
return result
print(no_adjacent_ones(3)) # -> ['000', '001', '010', '100', '101']
print(no_adjacent_ones(1)) # -> ['0', '1']
print(no_adjacent_ones(0)) # -> ['']Kodda değil de fikirde mi takıldın? Karar ağacı bunu anlatıyor.