İçeriğe geç

Geri ve ileri geçmişi

Kolay#doubly-linked-list#design~20 dk

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

Hedef zaman
O(n + Σk)
Hedef alan
O(n)

Kodda değil de fikirde mi takıldın? Çift yönlü bağlı listeler bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case