Description
設計一個瀏覽器歷史紀錄系統。
BrowserHistory(homepage)初始化，visit(url)訪問新頁面（清除前進歷史），back(steps)回退最多 steps 步，forward(steps)前進最多 steps 步。
Example:
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”]
Intuition#
核心思路：使用雙向鏈結串列模擬瀏覽器的前進/後退功能，visit 時截斷前進歷史。
- 瀏覽器歷史本質是一個可以前後移動的序列
- visit 新頁面時，當前位置之後的所有歷史都要清除
- 可以用 ArrayList（簡單）或雙向鏈結串列（更貼近實際）
Approaches#
1: ArrayList#
- 概念: 用 ArrayList 儲存歷史，cursor 指向當前位置，visit 時截斷 cursor 之後的部分
- 時間複雜度: visit
O(1)均攤, back/forwardO(1) - 空間複雜度:
O(n)- n 為訪問過的頁面數
class BrowserHistory(homepage: String) {
private val history = ArrayList<String>()
private var cursor = 0
init {
history.add(homepage)
}
fun visit(url: String) {
// 清除 cursor 之後的歷史
while (history.size > cursor + 1) {
history.removeAt(history.size - 1)
}
history.add(url)
cursor++
}
fun back(steps: Int): String {
cursor = maxOf(0, cursor - steps)
return history[cursor]
}
fun forward(steps: Int): String {
cursor = minOf(history.size - 1, cursor + steps)
return history[cursor]
}
}⭐2: Doubly Linked List#
- 概念: 每個頁面是一個節點，curr 指向當前頁面，visit 時將新節點接在 curr 後面並截斷後續
- 時間複雜度: visit
O(1), back/forwardO(steps) - 空間複雜度:
O(n)
class BrowserHistory(homepage: String) {
private class Node(val url: String) {
var prev: Node? = null
var next: Node? = null
}
private var curr = Node(homepage)
fun visit(url: String) {
val node = Node(url)
curr.next = node
node.prev = curr
curr = node
}
fun back(steps: Int): String {
var remaining = steps
while (remaining > 0 && curr.prev != null) {
curr = curr.prev!!
remaining--
}
return curr.url
}
fun forward(steps: Int): String {
var remaining = steps
while (remaining > 0 && curr.next != null) {
curr = curr.next!!
remaining--
}
return curr.url
}
}🔑 Takeaways#
- Pattern: 瀏覽器歷史是雙向鏈結串列的經典應用場景，前進/後退對應鏈結串列的雙向遍歷
- 關鍵技巧: visit 時截斷前進歷史，在鏈結串列中只需將 curr.next 指向新節點即可（舊的前進歷史會被 GC 回收）