Dizayn Brauzer Tarixi LeetCode Həlli

Problem bəyanat

Dizayn Brauzer Tarixçəsi LeetCode Həlli – Sizdə var browser başladığınız bir tab ilə homepage və başqasını ziyarət edə bilərsiniz url, tarixinə geri qayıt steps və ya tarixdə sayı irəlilə steps.

Həyata keçirir BrauzerTarixi sinif:

• BrowserHistory(string homepage) ilə obyekti işə salır homepage brauzerin.
• void visit(string url) Baxılıb url cari səhifədən. Bütün irəliləyiş tarixini aydınlaşdırır.
• string back(int steps) Hərəkət steps tarixə qayıt. Yalnız geri dönə bilsən x tarixdə addımlar və steps > x, yalnız qayıdacaqsınız x addımlar. Cərəyanı qaytarın url tarixə qayıtdıqdan sonra ən çox steps.
• string forward(int steps) Hərəkət steps tarixdə irəli. Yalnız irəliləyə bilsəniz x tarixdə addımlar və steps > x, yalnız yönləndirəcəksiniz x addımlar. Cərəyanı qaytarın url tarixə köçürdükdən sonra ən çox steps.

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Izahat

Elementlərin əlavə edilməsi və silinməsi ilə bağlı məhdudiyyətlərə baxsaq (bu halda veb səhifəyə daxil oluruq) biz aşağıdakı məlumat strukturu ilə qarşılaşa bilərik:

1. Açar sözlər
2. Növbəti dəyərini və əvvəlki dəyərini izləyir (Yönləndirmə və geri əməliyyat üçün)
3. Elementləri yuxarıya əlavə etmək asan (Ziyarət əməliyyatı üçün)

Beləliklə, bütün bunları yerinə yetirə bilən bir məlumat strukturu var, yəni İkiqat Əlaqədar List.

Beləliklə, başı həmişə brauzerin olduğu cari səhifəni göstərəcək ikiqat əlaqəli siyahı yaradırıq.

Zibil toplayıcı/ARC yalnız heç bir şey müəyyən yaddaşa işarə etmədikdə yaddaşı boşaldacaq. Bu yaddaşın başqa bir yaddaşa işarə etməməsini tələb etmir, yaxşıdır. Sadəcə olaraq tələb edir ki, həmin yaddaşa heç bir istinad olmasın [toplanmaq/azad etmək].

Ancaq bu ikiqat əlaqəli siyahı vəziyyətində, əvvəlki referatı (həftə arayışı) etməsək, çıxılmaz vəziyyət yarana bilər.

A <—> B [çıxarma nöqtəsi] <—> C <—> D <—> E

bundan sonra da

C <—> D <—> E, bu mövcud olacaq

Kodu

Dizayn Brauzer Tarixi üçün C++ Kodu

class BrowserHistory {
public:
    string stack[5005];
    int p, t;	// current pointer, stack's top
    
    BrowserHistory(string homepage) {
        stack[p = t = 0] = homepage;
    }
    
    void visit(string url) {
        stack[t = ++p] = url;
    }
    
    string back(int steps) {
        return stack[p = max(0, p-steps)];
    }
    
    string forward(int steps) {
        return stack[p = min(t, p+steps)];
    }
};

Dizayn Brauzer Tarixi üçün Java Kodu

class BrowserHistory {
    
    public class Node{
        String url;
        Node next, prev;
        public Node(String url) {
            this.url = url;
            next = null;
            prev = null;
        }
    }
    
    Node head, curr;
    public BrowserHistory(String homepage) {
        head = new Node(homepage);
        curr = head;
    }
    
    public void visit(String url) {
        Node node = new Node(url);
        curr.next = node;
        node.prev = curr;
        curr = node;
    }
    
    public String back(int steps) {
        while (curr.prev != null && steps-- > 0) {
            curr = curr.prev;
        }
        return curr.url;
    }
    
    public String forward(int steps) {
        while (curr.next != null && steps-- > 0) {
            curr = curr.next;
        }
        return curr.url;
    }
}

Dizayn Brauzer Tarixi üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O (N)

Kosmik Mürəkkəblik

O (N)