如何建立自己的摄影网站,网络营销专业的职业生涯规划,公司网页设计项目简历,服务器镜像wordpress【LetMeFly】1472.设计浏览器历史记录#xff1a;一个数组完成模拟#xff0c;单次操作均O(1)
力扣题目链接#xff1a;https://leetcode.cn/problems/design-browser-history/
你有一个只支持单个标签页的 浏览器 #xff0c;最开始你浏览的网页是 homepage #xff0c…【LetMeFly】1472.设计浏览器历史记录一个数组完成模拟单次操作均O(1)
力扣题目链接https://leetcode.cn/problems/design-browser-history/
你有一个只支持单个标签页的 浏览器 最开始你浏览的网页是 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 201 url.length 201 steps 100homepage 和 url 都只包含 . 或者小写英文字母。最多调用 5000 次 visit back 和 forward 函数。
解题方法数组模拟
使用一个大小可变的数组模拟浏览器(标签页)历史记录。初始值只有一个元素homepage。
使用now变量记录当前页面的下标使用right记录最后一个页面的下标。
同时做到历史记录数组只增不减要减小就左移right指针。这样能避免一些重复开辟和释放空间带来的性能损耗。
visit now 如果now超过了历史记录数组的大小则将当前页面push到历史记录数组中 否则直接将history[now]记为当前页面 right now。这是因为一旦访问新页面则无法再“forward” 并不需要真的将“无法forward到的页面”从数组中移除直接等待新访问页面将其覆盖即可 back now max(0, now - step)然后直接返回history[now] forward now min(right, now step)然后直接返回history[now] 时间复杂度 O ( N 2 ) O(N^2) O(N2)空间复杂度 O ( N log N ) O(N\log N) O(NlogN)
AC代码
C
/** Author: LetMeFly* Date: 2025-02-26 13:16:28* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-26 13:37:36*/
class BrowserHistory {
private:vectorstring history;int now, right;
public:BrowserHistory(string homepage) {history.push_back(homepage);now right 0;}void visit(string url) {if (now history.size()) {history.push_back(url);} else {history[now] url;}right now;}string back(int steps) {now max(0, now - steps);return history[now];}string forward(int steps) {now min(right, now steps);return history[now];}
};/*** 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);*/执行用时分布14ms击败92.71%消耗内存分布60.61MB击败96.09%
Python Author: LetMeFly
Date: 2025-02-26 13:38:49
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-26 13:41:11class BrowserHistory:def __init__(self, homepage: str):self.history [homepage]self.now self.right 0def visit(self, url: str) - None:self.now 1if self.now len(self.history):self.history.append(url)else:self.history[self.now] urlself.right self.nowdef back(self, steps: int) - str:self.now max(0, self.now - steps)return self.history[self.now]def forward(self, steps: int) - str:self.now min(self.right, self.now steps)return self.history[self.now]# 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
/** Author: LetMeFly* Date: 2025-02-26 13:41:42* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-26 13:45:07*/
import java.util.List;
import java.util.ArrayList;class BrowserHistory {private ListString history;private int now, right;public BrowserHistory(String homepage) {history new ArrayList();now right 0;history.add(homepage);}public void visit(String url) {if (now history.size()) {history.add(url);} else {history.set(now, url);}right now;}public String back(int steps) {now Math.max(0, now - steps);return history.get(now);}public String forward(int steps) {now Math.min(right, now steps);return history.get(now);}
}/*** 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);*/Go
/** Author: LetMeFly* Date: 2025-02-26 13:45:43* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-26 13:49:00*/
package maintype BrowserHistory struct {history []stringnow,right int
}func Constructor(homepage string) BrowserHistory {history : make([]string, 1)history[0] homepagereturn BrowserHistory{history: history,now: 0,right: 0,}
}func (this *BrowserHistory) Visit(url string) {this.nowif this.now len(this.history) {this.history append(this.history, url)} else {this.history[this.now] url}this.right this.now
}func (this *BrowserHistory) Back(steps int) string {this.now max(0, this.now - steps)return this.history[this.now]
}func (this *BrowserHistory) Forward(steps int) string {this.now min(this.right, this.now steps)return this.history[this.now]
}/*** Your BrowserHistory object will be instantiated and called as such:* obj : Constructor(homepage);* obj.Visit(url);* param_2 : obj.Back(steps);* param_3 : obj.Forward(steps);*/同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ 千篇源码题解已开源
