Geri ve ileri geçmişi
Görev tanımı
Problem
Bir ana sayfada başlayan tek bir tarayıcı sekmesinin geçmişini simüle et. Bir ziyaret mevcut sayfadan sonra yeni bir sayfa açar ve daha önce ileri gidebileceğin her sayfayı çöpe atar. k'lık bir geri başa doğru en fazla k sayfa, k'lık bir ileri de en yeniye doğru en fazla k sayfa gider; gidecek yer kalmayınca erken durur. Ana sayfa ve bir işlem listesi verildiğinde, her geri ya da ileriden sonra bulunduğun sayfayı sırasıyla döndür.
Örnekler
Input: home = "home"
ops = [("visit", "a"), ("visit", "b"), ("back", 1),
("visit", "c"), ("forward", 1), ("back", 5)]
Output: ['a', 'c', 'home']
Neden: a'dan c'yi ziyaret etmek b'yi atar, bu yüzden ileri gidecek yer yok
Input: home = "x", ops = [("back", 2), ("forward", 3)]
Output: ['x', 'x']
Neden: edge case: yeni bir sekme iki yöne de gidemez
İpuçları
0 / 3
Her sayfanın hem kendinden önceki hem sonraki sayfayı bilmesi gerekir; geri ve ileri bu bağlantılardan yalnız birini dolaşır.
Bir ziyaret ileri sayfaları tek tek silmez. Mevcut sayfayı yepyeni bir sonraki sayfaya göstermek onları tek hamlede ulaşılamaz yapar.
Sayfa başına prev ve next bağlantıları olan bir düğüm ve mevcut düğüme bir pointer tut. Ziyaret mevcut olandan sonra yeni bir düğüm bağlar ve oraya geçer; geri ve ileri de bağlantı boş olunca durarak en fazla k kez prev ya da next boyunca adım atar.
- Hedef zaman
- O(n + Σk)
- Hedef alan
- O(n)
Çözüm
Her sayfa, önündeki ve arkasındaki sayfaya bağlantıları olan bir düğümdür ve bir pointer sekmenin nerede olduğunu işaretler. Bir ziyaret mevcut olandan sonra yeni bir düğüm asar; bu, eski ileri sayfaları sessizce keser, sonra onun üzerine geçer. Geri ve ileri, prev ya da next bağlantılarını birer adım izler ve ilk eksik bağlantıda durur, bu yüzden fazla gitmeye çalışmak zararsızdır. Bir ziyaret O(1), k adımlık bir hareket O(k), alan O(ziyaret sayısı).
class Page:
def __init__(self, url, prev=None): self.url, self.prev, self.next = url, prev, None
def run_history(home, ops):
current, seen = Page(home), []
for op, arg in ops:
if op == "visit":
current.next = Page(arg, current) # the old forward pages become unreachable
current = current.next
continue
for _ in range(arg): # back or forward, at most arg steps
step = current.prev if op == "back" else current.next
if step is None:
break
current = step
seen.append(current.url)
return seen
print(run_history("home", [("visit", "a"), ("visit", "b"), ("back", 1), ("visit", "c"), ("forward", 1), ("back", 5)])) # -> ['a', 'c', 'home']
print(run_history("x", [("back", 2), ("forward", 3)])) # -> ['x', 'x']
print(run_history("x", [])) # -> []Kodda değil de fikirde mi takıldın? Çift yönlü bağlı listeler bunu anlatıyor.