当前位置: 首页 > news >正文

LeetCode 1472.设计浏览器历史记录:一个数组完成模拟,单次操作均O(1)

【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 <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • homepage 和 url 都只包含 '.' 或者小写英文字母。
  • 最多调用 5000 次 visit, back 和 forward 函数。

解题方法:数组模拟

使用一个大小可变的数组模拟浏览器(标签页)历史记录。初始值只有一个元素homepage

使用now变量记录当前页面的下标,使用right记录最后一个页面的下标。

同时做到:历史记录数组只增不减,要减小就左移right指针。这样能避免一些重复开辟和释放空间带来的性能损耗。

visit:

  1. now++

    如果now超过了历史记录数组的大小,则将当前页面push到历史记录数组中

    否则,直接将history[now]记为当前页面

  2. 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:vector<string> 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:11
'''
class 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 List<String> 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.now++if 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

相关文章:

LeetCode 1472.设计浏览器历史记录:一个数组完成模拟,单次操作均O(1)

【LetMeFly】1472.设计浏览器历史记录&#xff1a;一个数组完成模拟&#xff0c;单次操作均O(1) 力扣题目链接&#xff1a;https://leetcode.cn/problems/design-browser-history/ 你有一个只支持单个标签页的 浏览器 &#xff0c;最开始你浏览的网页是 homepage &#xff0c…...

AI+游戏,正在进行时!

2月&#xff0c;DeepSeek引领的AI浪潮对游戏行业造成了巨大冲击。 2月17日马斯克在社交平台宣布&#xff0c;xAI将成立一家AI游戏工作室&#xff0c;高调宣布两大核心理念&#xff0c;打破大公司的垄断&#xff0c;利用AI重构游戏体验。随后的新闻中还表示&#xff0c;团队计划…...

贪心算法精品题

1.找钱问题 本题的贪心策略在于我们希望就可能的保留作用大的5元 class Solution { public:bool lemonadeChange(vector<int>& bills) {std::map<int ,int> _map;for(auto ch:bills){if(ch 5) _map[ch];else if(ch 10){if(_map[5] 0) return false;else{_m…...

sql server 复制从备份初始化数据

参考 &#xff1a; 从备份初始化订阅&#xff08;事务&#xff09; - SQL Server | Microsoft Learn sql server 复制默认是用快照初始化数据的&#xff0c;也支持从备份初始化数据&#xff0c;参考如上...

【蓝桥杯】1.k倍区间

前缀和 #include <iostream> using namespace std; const int N100010; long long a[N]; int cnt[N]; int main(){int n, m;cnt[0] 1;cin >> n >> m;long long res 0;for(int i 1; i < n; i){scanf("%d", &a[i]);a[i] a[i-1];res cnt…...

Qt互斥锁(QMutex)的使用、QMutexLocker的使用

Qt互斥锁【QMutex】的使用、QMutexLocker的使用 Chapter1 Qt互斥锁(QMutex)的使用、QMutexLocker的使用一、QMutexLocker和QMutex实现示例图二、QMutex和QMutexLocker的关系&#xff08;个人理解&#xff09;三、QMutex使用和QMutexLocker使用1.QMutex的使用2.QMutexLocker的使…...

具身智能(Embodied AI)的物理交互基准测试:构建真实世界的智能体评估体系

文章目录 引言:从虚拟到物理的智能跃迁一、具身智能测试体系设计1.1 评估维度矩阵1.2 测试平台技术栈二、核心测试场景构建2.1 基础运动能力测试集2.2 复杂操作任务设计三、物理仿真引擎关键技术3.1 高精度接触力学模型3.2 传感器噪声模拟四、评估指标体系4.1 量化指标公式4.2…...

Javaweb后端数据库多表关系一对多,外键,一对一

多表关系 一对多 多的表里&#xff0c;要有一表里的主键 外键 多的表上&#xff0c;添加外键 一对一 多对多 案例...

鸿蒙 ArkUI 实现敲木鱼小游戏

敲木鱼是一款具有禅意的趣味小游戏&#xff0c;本文将通过鸿蒙 ArkUI 框架的实现代码&#xff0c;逐步解析其核心技术点&#xff0c;包括动画驱动、状态管理、音效震动反馈等。 一、架构设计与工程搭建 1.1 项目结构解析 完整项目包含以下核心模块&#xff1a; ├── entry…...

cv2.solvePnP 报错 求相机位姿

目录 报错信息及解决&#xff1a; cv2.solvePnP 使用例子&#xff1a; 设置初始值效果也不好 cv2.projectPoints 函数效果不好 报错信息及解决&#xff1a; File "/shared_disk/users/lbg/project/human_4d/nlf_pose/render_demo_pkl2_cal.py", line 236, in <…...

Linux实操——在服务器上直接从百度网盘下载(/上传)文件

Linux Linux实操——在服务器上直接从百度网盘下载&#xff08;/上传&#xff09;文件 文章目录 Linux前言一、下载并安装bypy工具二、认证并授权网盘账号三、将所需文件转移至目的文件夹下四、下载文件五、上传文件六、更换绑定的百度云盘账户 前言 最近收到一批很大的数据&…...

2004-2024年光刻机系统及性能研究领域国内外发展历史、差距、研究难点热点、进展突破及下一个十年研究热点方向2025.2.27

一.光刻机概述 1.1 定义与原理 光刻机是 集成电路芯片制造的核心设备 ,其工作原理基于 光学成像和化学反应 。它通过 曝光系统 将掩模版上的图形精确地转移到涂覆于硅片表面的光刻胶上。这个过程涉及复杂的物理和化学反应,主要包括以下几个步骤: 涂胶 :在硅片表面均匀涂抹…...

请求Geoserver的WTMS服务返回200不返回图片问题-跨域导致

今天碰到个奇怪问题&#xff0c;改了个页面标题再打包布署GeoServer发现调用WTMS服务失败&#xff0c;请求返回状态码200&#xff0c;返回包大小0&#xff0c;使用postman模拟请求是可以正常返回图片的。 跟之前版本对比如下&#xff1a; 正常Response请求: HTTP/1.1 200X-Fr…...

ubuntu配置jmeter

1.前提准备 系统 ubuntu server 22.04 前提条件&#xff1a;服务器更新apt与安装lrzsz&#xff1a;更新apt&#xff1a; sudo apt update安装lrzsz: 命令行下的上传下载文件工具 sudo apt install lrzszsudo apt install zip2.安装jemeter 2.1.下载jdk17 输入命令&#xf…...

《Qt动画编程实战:轻松实现头像旋转效果》

《Qt动画编程实战&#xff1a;轻松实现头像旋转效果》 Qt 提供了丰富的动画框架&#xff0c;可以轻松实现各种平滑的动画效果。其中&#xff0c;旋转动画是一种常见的 UI 交互方式&#xff0c;广泛应用于加载指示器、按钮动画、场景变换等。本篇文章将详细介绍如何使用 Qt 实现…...

【Mac电脑本地部署Deepseek-r1:详细教程与Openwebui配置指南】

文章目录 前言电脑配置&#xff1a;安装的Deepseek版本&#xff1a;使用的UI框架&#xff1a;体验效果展示&#xff1a;本地部署体验总结 部署过程Ollama部署拉取模型运行模型Openwebui部署运行Ollama服务在Openwebui中配置ollama的服务 后话 前言 deepseek最近火的一塌糊涂&a…...

DeepSeek开源技术全景解析:从硬件榨取到AI民主化革命

DeepSeek开源技术全景解析&#xff1a;从硬件榨取到AI民主化革命 一、开源周核心成果概览 2025年2月24日启动的"开源周"计划&#xff0c;DeepSeek团队连续发布三项底层技术突破&#xff1a; FlashMLA&#xff08;2.24&#xff09;&#xff1a;动态资源调度算法&am…...

WPF12-MVVM

目录 1. 什么是MVVM2. 实现简单MVVM2.1. Part 12.2. Part 21. 什么是MVVM MVVM 是 Model-View-ViewModel 的缩写,是一种用于构建用户界面的设计模式,是一种简化用户界面的事件驱动编程方式。 MVVM 的目标是实现用户界面和业务逻辑之间的彻底分离,以便更好地管理和维护应用…...

一个原教旨的多路径 TCP

前面提到过 ECMP 和 TCP 之间的互不友好&#xff0c;pacing 收益和中断开销的互斥&#xff0c;在事实上阻碍了 packet-based LB 的部署&#xff0c;也限制了交换机&#xff0c;服务器的并发性能&#xff0c;同时潜在增加了 bufferbloat 的概率&#xff0c;而适用 packet-based …...

跟着AI学vue第十三章

第十三章&#xff1a;技术传承与行业影响力塑造 到了这个阶段&#xff0c;你已经在Vue技术领域积累了深厚的经验&#xff0c;拥有了较强的技术实力。此时&#xff0c;你的重点将是把自己的知识和经验传递给更多人&#xff0c;在行业内树立起影响力&#xff0c;推动整个Vue技术…...

3 分钟搞定答辩 PPT!PaperXie AI:本科生的学术汇报「开挂」神器

paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/AIPPThttps://www.paperxie.cn/ppt/createhttps://www.paperxie.cn/ppt/create 一、 答辩 PPT 的「血泪史」&#xff1a;你是不是也卡在这一步&#xff1f; 毕业论文写到定稿&#xff0c;以为能松口气&…...

STM32 HAL库下Modbus通讯卡死?别急着清标志位,先查查这个隐藏的AD采样循环

STM32 HAL库下Modbus通讯卡死&#xff1f;别急着清标志位&#xff0c;先查查这个隐藏的AD采样循环 当你的Modbus通讯突然卡死&#xff0c;而所有常规排查手段都指向"标志位未清除"时&#xff0c;先别急着在串口中断里打转。我最近在工业传感器项目中踩过一个坑&#…...

轻量高效的动态指针数组CPtrArray实现

在C开发中&#xff0c;动态管理指针集合是常见需求&#xff0c;今天分享一款轻量、高效的动态指针数组类CPtrArray&#xff0c;其核心作用是统一管理任意类型指针的存储、删除、访问&#xff0c;适配单线程下的各类指针管理场景&#xff0c;代码简洁且实用性强。CPtrArray采用动…...

Zephyr SMF轻量状态机实战与嵌入式开发优化

1. 项目概述"Zephyr SMF实战&#xff1a;几百行代码实现轻量状态机&#xff01;"这个标题立刻让我想起了在嵌入式开发中经常遇到的状态管理难题。作为一名在RTOS领域摸爬滚打多年的开发者&#xff0c;我深知状态机在嵌入式系统中的重要性——它就像交通信号灯控制系统…...

Pixel Mind Decoder 创意应用展示:AI 驱动的情感化故事生成器

Pixel Mind Decoder 创意应用展示&#xff1a;AI 驱动的情感化故事生成器 1. 当AI学会感知情绪 你有没有想过&#xff0c;一个故事生成器不仅能理解文字&#xff0c;还能感知情绪&#xff1f;这就是我们最新开发的"情感化故事生成器"的核心能力。通过结合Pixel Min…...

专业付费墙突破技术:5个高效解决方案完整指南

专业付费墙突破技术&#xff1a;5个高效解决方案完整指南 你是否在为付费墙而烦恼&#xff1f;想要获取优质内容却被各种限制困扰&#xff1f;今天我将为你详细介绍5种专业的付费墙突破技术&#xff0c;帮助你在合法范围内更好地获取所需信息。本文仅用于技术研究和学习目的&am…...

Retinaface+CurricularFace人脸识别镜像实测:5分钟快速部署,小白也能轻松上手

RetinafaceCurricularFace人脸识别镜像实测&#xff1a;5分钟快速部署&#xff0c;小白也能轻松上手 1. 为什么选择这个镜像&#xff1f; 想快速搭建一个高精度的人脸识别系统&#xff1f;市面上方案虽多&#xff0c;但要么部署复杂&#xff0c;要么效果不佳。今天给大家介绍…...

OpenClaw技能扩展实战:用Qwen3.5-9B实现公众号图文自动化

OpenClaw技能扩展实战&#xff1a;用Qwen3.5-9B实现公众号图文自动化 1. 为什么选择OpenClaw做公众号自动化 去年我开始运营技术公众号时&#xff0c;最头疼的就是内容发布的繁琐流程&#xff1a;写完Markdown要手动转格式、找配图、调整排版&#xff0c;最后才能上传到公众号…...

空项目文档无法生成技术内容

项目标题“mecanum2017_2”未提供有效摘要、关键词及README内容&#xff0c;所有输入字段均为空或无效&#xff08;摘要仅为十六个日文平假名“おぼぼぼぼぼぼぼぼぼぼぼぼぼぼぼ”&#xff0c;无技术含义&#xff1b;关键词为空&#xff1b;README内容为空&#xff09;。 根据…...

Java全核心-阿里大厂面试-Gemini版

完善更新中......一、Java 核心基础1、Java 四大引用与 ThreadLocal 深度拷问【核心连环炮】面试官&#xff1a;说一下 Java 的四大引用及其实际业务场景&#xff1f;面试官&#xff1a;ThreadLocal 为什么要用弱引用&#xff1f;不用行不行&#xff1f;面试官&#xff1a;既然…...