1472. 设计浏览器历史记录

English Version

题目描述

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

• BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
• void visit(string url) 从当前页跳转访问 url 对应的页面  。执行此操作会把浏览历史前进的记录全部删除。
• string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
• string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

 

示例：

输入：
["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]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

 

提示：

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage 和 url 都只包含 '.' 或者小写英文字母。
• 最多调用 5000 次 visit， back 和 forward 函数。

解法

Python3

列表实现。

class BrowserHistory:

    def __init__(self, homepage: str):
        self.urls = []
        self.cur = -1
        self.tail = -1
        self.visit(homepage)

    def visit(self, url: str) -> None:
        self.cur += 1
        if self.cur < len(self.urls):
            self.urls[self.cur] = url
        else:
            self.urls.append(url)
        self.tail = self.cur

    def back(self, steps: int) -> str:
        self.cur = max(0, self.cur -steps)
        return self.urls[self.cur]

    def forward(self, steps: int) -> str:
        self.cur = min(self.tail, self.cur + steps)
        return self.urls[self.cur]

# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

栈实现。

class BrowserHistory:

    def __init__(self, homepage: str):
        self.s1 = []
        self.s2 = []
        self.cur = homepage

    def visit(self, url: str) -> None:
        self.s2.clear()
        self.s1.append(self.cur)
        self.cur = url

    def back(self, steps: int) -> str:
        while steps > 0 and self.s1:
            self.s2.append(self.cur)
            self.cur = self.s1.pop()
            steps -= 1
        return self.cur

    def forward(self, steps: int) -> str:
        while steps > 0 and self.s2:
            self.s1.append(self.cur)
            self.cur = self.s2.pop()
            steps -= 1
        return self.cur


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

Java

列表实现。

class BrowserHistory {
    private List<String> urls;
    private int cur = -1;
    private int tail = -1;

    public BrowserHistory(String homepage) {
        urls = new ArrayList<>();
        visit(homepage);
    }

    public void visit(String url) {
        ++cur;
        if (cur < urls.size()) {
            urls.set(cur, url);
        } else {
            urls.add(url);
        }
        tail = cur;
    }

    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return urls.get(cur);
    }

    public String forward(int steps) {
        cur = Math.min(tail, cur + steps);
        return urls.get(cur);
    }
}

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory obj = new BrowserHistory(homepage);
 * obj.visit(url);
 * String param_2 = obj.back(steps);
 * String param_3 = obj.forward(steps);
 */

栈实现。

class BrowserHistory {
    private Deque<String> s1;
    private Deque<String> s2;
    private String cur;

    public BrowserHistory(String homepage) {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
        cur = homepage;
    }

    public void visit(String url) {
        s2.clear();
        s1.push(cur);
        cur = url;
    }

    public String back(int steps) {
        while (steps > 0 && !s1.isEmpty()) {
            s2.push(cur);
            cur = s1.pop();
            --steps;
        }
        return cur;
    }

    public String forward(int steps) {
        while (steps > 0 && !s2.isEmpty()) {
            s1.push(cur);
            cur = s2.pop();
            --steps;
        }
        return cur;
    }
}

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory obj = new BrowserHistory(homepage);
 * obj.visit(url);
 * String param_2 = obj.back(steps);
 * String param_3 = obj.forward(steps);
 */

...