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 <= 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: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.设计浏览器历史记录:一个数组完成模拟,单次操作均O(1) 力扣题目链接:https://leetcode.cn/problems/design-browser-history/ 你有一个只支持单个标签页的 浏览器 ,最开始你浏览的网页是 homepage ,…...
AI+游戏,正在进行时!
2月,DeepSeek引领的AI浪潮对游戏行业造成了巨大冲击。 2月17日马斯克在社交平台宣布,xAI将成立一家AI游戏工作室,高调宣布两大核心理念,打破大公司的垄断,利用AI重构游戏体验。随后的新闻中还表示,团队计划…...
贪心算法精品题
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 复制从备份初始化数据
参考 : 从备份初始化订阅(事务) - SQL Server | Microsoft Learn sql server 复制默认是用快照初始化数据的,也支持从备份初始化数据,参考如上...
【蓝桥杯】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的关系(个人理解)三、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后端数据库多表关系一对多,外键,一对一
多表关系 一对多 多的表里,要有一表里的主键 外键 多的表上,添加外键 一对一 多对多 案例...
鸿蒙 ArkUI 实现敲木鱼小游戏
敲木鱼是一款具有禅意的趣味小游戏,本文将通过鸿蒙 ArkUI 框架的实现代码,逐步解析其核心技术点,包括动画驱动、状态管理、音效震动反馈等。 一、架构设计与工程搭建 1.1 项目结构解析 完整项目包含以下核心模块: ├── entry…...
cv2.solvePnP 报错 求相机位姿
目录 报错信息及解决: cv2.solvePnP 使用例子: 设置初始值效果也不好 cv2.projectPoints 函数效果不好 报错信息及解决: File "/shared_disk/users/lbg/project/human_4d/nlf_pose/render_demo_pkl2_cal.py", line 236, in <…...
Linux实操——在服务器上直接从百度网盘下载(/上传)文件
Linux Linux实操——在服务器上直接从百度网盘下载(/上传)文件 文章目录 Linux前言一、下载并安装bypy工具二、认证并授权网盘账号三、将所需文件转移至目的文件夹下四、下载文件五、上传文件六、更换绑定的百度云盘账户 前言 最近收到一批很大的数据&…...
2004-2024年光刻机系统及性能研究领域国内外发展历史、差距、研究难点热点、进展突破及下一个十年研究热点方向2025.2.27
一.光刻机概述 1.1 定义与原理 光刻机是 集成电路芯片制造的核心设备 ,其工作原理基于 光学成像和化学反应 。它通过 曝光系统 将掩模版上的图形精确地转移到涂覆于硅片表面的光刻胶上。这个过程涉及复杂的物理和化学反应,主要包括以下几个步骤: 涂胶 :在硅片表面均匀涂抹…...
请求Geoserver的WTMS服务返回200不返回图片问题-跨域导致
今天碰到个奇怪问题,改了个页面标题再打包布署GeoServer发现调用WTMS服务失败,请求返回状态码200,返回包大小0,使用postman模拟请求是可以正常返回图片的。 跟之前版本对比如下: 正常Response请求: HTTP/1.1 200X-Fr…...
ubuntu配置jmeter
1.前提准备 系统 ubuntu server 22.04 前提条件:服务器更新apt与安装lrzsz:更新apt: sudo apt update安装lrzsz: 命令行下的上传下载文件工具 sudo apt install lrzszsudo apt install zip2.安装jemeter 2.1.下载jdk17 输入命令…...
《Qt动画编程实战:轻松实现头像旋转效果》
《Qt动画编程实战:轻松实现头像旋转效果》 Qt 提供了丰富的动画框架,可以轻松实现各种平滑的动画效果。其中,旋转动画是一种常见的 UI 交互方式,广泛应用于加载指示器、按钮动画、场景变换等。本篇文章将详细介绍如何使用 Qt 实现…...
【Mac电脑本地部署Deepseek-r1:详细教程与Openwebui配置指南】
文章目录 前言电脑配置:安装的Deepseek版本:使用的UI框架:体验效果展示:本地部署体验总结 部署过程Ollama部署拉取模型运行模型Openwebui部署运行Ollama服务在Openwebui中配置ollama的服务 后话 前言 deepseek最近火的一塌糊涂&a…...
DeepSeek开源技术全景解析:从硬件榨取到AI民主化革命
DeepSeek开源技术全景解析:从硬件榨取到AI民主化革命 一、开源周核心成果概览 2025年2月24日启动的"开源周"计划,DeepSeek团队连续发布三项底层技术突破: FlashMLA(2.24):动态资源调度算法&am…...
WPF12-MVVM
目录 1. 什么是MVVM2. 实现简单MVVM2.1. Part 12.2. Part 21. 什么是MVVM MVVM 是 Model-View-ViewModel 的缩写,是一种用于构建用户界面的设计模式,是一种简化用户界面的事件驱动编程方式。 MVVM 的目标是实现用户界面和业务逻辑之间的彻底分离,以便更好地管理和维护应用…...
一个原教旨的多路径 TCP
前面提到过 ECMP 和 TCP 之间的互不友好,pacing 收益和中断开销的互斥,在事实上阻碍了 packet-based LB 的部署,也限制了交换机,服务器的并发性能,同时潜在增加了 bufferbloat 的概率,而适用 packet-based …...
跟着AI学vue第十三章
第十三章:技术传承与行业影响力塑造 到了这个阶段,你已经在Vue技术领域积累了深厚的经验,拥有了较强的技术实力。此时,你的重点将是把自己的知识和经验传递给更多人,在行业内树立起影响力,推动整个Vue技术…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
