1.题目基本信息
1.1.题目描述
你有一个只支持单个标签页的 浏览器 ,最开始你浏览的网页是 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 。
1.2.题目地址
https://leetcode.cn/problems/design-browser-history/description
2.解题方法
2.1.解题思路
构建双栈的数据结构,backStack栈为历史访问记录栈,其栈顶表示当前页面,forwardStack为前进能访问的栈。
2.2.解题步骤
第一步,设计双栈数据结构
第二步,当访问新url时,直接将url添加到backStack顶部,为新的当前页面,同时清空forwardStack栈中前进访问的url
第三步,当回退时,只需从backStack栈顶弹出,同时将弹出的url加到forwardStack栈顶即可(需要保证backStack不为空,因为栈顶为当前页面必须保证存在)
第四步,当前进时,只需从forwardStack栈顶弹出url并添加到backStack栈顶(直到forwardStack为空,前进访问的url可以没有)
3.解题代码
Python代码
class BrowserHistory:
# 关键:构建双栈的数据结构,backStack栈为历史访问记录栈,其栈顶表示当前页面,forwardStack为前进能访问的栈。第一步,设计双栈数据结构。第二步,当访问新url时,直接将url添加到backStack顶部,为新的当前页面,同时清空forwardStack栈中前进访问的url。第三步,当回退时,只需从backStack栈顶弹出,同时将弹出的url加到forwardStack栈顶即可(需要保证backStack不为空,因为栈顶为当前页面必须保证存在)。第四步,当前进时,只需从forwardStack栈顶弹出url并添加到backStack栈顶(直到forwardStack为空,前进访问的url可以没有)
def __init__(self, homepage: str):
# backStack的栈顶维护为当前页面
self.backStack=[]
self.forwardStack=[]
self.backStack.append(homepage)
def visit(self, url: str) -> None:
self.backStack.append(url)
self.forwardStack.clear()
def back(self, steps: int) -> str:
for i in range(steps):
if len(self.backStack)>1:
self.forwardStack.append(self.backStack.pop())
return self.backStack[-1]
def forward(self, steps: int) -> str:
for i in range(steps):
if len(self.forwardStack)>0:
self.backStack.append(self.forwardStack.pop())
return self.backStack[-1]
C++代码
class BrowserHistory {
public:
stack<string> backStack;
stack<string> forwardStack;
BrowserHistory(string homepage) {
backStack.push(homepage);
}
void visit(string url) {
backStack.push(url);
while(!forwardStack.empty()){
forwardStack.pop();
}
}
string back(int steps) {
for(int i=0;i<steps;++i){
if(backStack.size()>1){
string tempUrl=backStack.top();
forwardStack.push(tempUrl);
backStack.pop();
}
}
return backStack.top();
}
string forward(int steps) {
for(int i=0;i<steps;++i){
if(!forwardStack.empty()){
string tempUrl=forwardStack.top();
backStack.push(tempUrl);
forwardStack.pop();
}
}
return backStack.top();
}
};