【LeetCode每日一题】【2023/2/9】1797. 设计一个验证系统
文章目录
- 1797. 设计一个验证系统
- 方法1:哈希表
- 代码总体
1797. 设计一个验证系统
LeetCode: 1797. 设计一个验证系统
中等\color{#FFB800}{中等}中等
你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在
currentTime时刻之后timeToLive秒过期。如果验证码被更新了,那么它会在currentTime(可能与之前的currentTime不同)时刻延长timeToLive秒。请你实现
AuthenticationManager类:
AuthenticationManager(int timeToLive)构造AuthenticationManager并设置timeToLive参数。generate(string tokenId, int currentTime)给定tokenId,在当前时间currentTime生成一个新的验证码。renew(string tokenId, int currentTime)将给定tokenId且 未过期 的验证码在currentTime时刻更新。如果给定tokenId对应的验证码不存在或已过期,请你忽略该操作,不会有任何更新操作发生。countUnexpiredTokens(int currentTime)请返回在给定currentTime时刻,未过期 的验证码数目。如果一个验证码在时刻
t过期,且另一个操作恰好在时刻t发生(renew或者countUnexpiredTokens操作),过期事件 优先于 其他操作。
示例 1:

输入:
["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"]
[[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
输出:
[null, null, null, 1, null, null, null, 0]解释:
AuthenticationManager authenticationManager = new AuthenticationManager(5); // 构造 AuthenticationManager ,设置 timeToLive = 5 秒。
authenticationManager.renew("aaa", 1); // 时刻 1 时,没有验证码的 tokenId 为 "aaa" ,没有验证码被更新。
authenticationManager.generate("aaa", 2); // 时刻 2 时,生成一个 tokenId 为 "aaa" 的新验证码。
authenticationManager.countUnexpiredTokens(6); // 时刻 6 时,只有 tokenId 为 "aaa" 的验证码未过期,所以返回 1 。
authenticationManager.generate("bbb", 7); // 时刻 7 时,生成一个 tokenId 为 "bbb" 的新验证码。
authenticationManager.renew("aaa", 8); // tokenId 为 "aaa" 的验证码在时刻 7 过期,且 8 >= 7 ,所以时刻 8 的renew 操作被忽略,没有验证码被更新。
authenticationManager.renew("bbb", 10); // tokenId 为 "bbb" 的验证码在时刻 10 没有过期,所以 renew 操作会执行,该 token 将在时刻 15 过期。
authenticationManager.countUnexpiredTokens(15); // tokenId 为 "bbb" 的验证码在时刻 15 过期,tokenId 为 "aaa" 的验证码在时刻 7 过期,所有验证码均已过期,所以返回 0 。
提示:
1 <= timeToLive <= 10^81 <= currentTime <= 10^81 <= tokenId.length <= 5tokenId只包含小写英文字母。- 所有
generate函数的调用都会包含独一无二的tokenId值。 - 所有函数调用中,
currentTime的值 严格递增 。 - 所有函数的调用次数总共不超过
2000次。
方法1:哈希表
使用哈希表来存放验证码及其过期时间。哈希表的键为验证码字符串,值为对应的过期时间。
构造函数将 timeToLive 记录下来:
class AuthenticationManager
{
public:explicit AuthenticationManager(const int timeToLive): ttl{timeToLive} { }private:const int ttl;
};
函数 generate() 将传入的 tokenId 记录下来,并将 currentTime 加上 ttl 作为该验证码的 过期时间 记录下来:
void generate(string tokenId, const int currentTime)
{hashtable.emplace(std::move(tokenId), currentTime + ttl);
}
函数 renew() 实现验证码的更新。按题意,若哈希表中没有找到该验证码,则不做任何操作;若该验证码的过期时间 小于等于 当前时间 currentTime ,则删除,否则更新为 currentTime + ttl ,即在当前时间下 延后 ttl 个时间。
void renew(const string& tokenId, const int currentTime)
{if (const auto it = hashtable.find(tokenId);it != hashtable.end()){if (it->second > currentTime)it->second = currentTime + ttl;elsehashtable.erase(it);}
}
函数 countUnexpiredTokens 在调用函数 clearExpiredTokens 清除 过期 验证码后,返回哈希表中的元素个数,即为所求的当前 未过期 的验证码。
int countUnexpiredTokens(const int currentTime)
{clearExpiredTokens(currentTime);return static_cast<int>(hashtable.size());
}
函数 clearExpiredTokens 遍历哈希表,并逐个删除 过期的 验证码:
void clearExpiredTokens(const int currentTime)
{for (auto it = hashtable.begin(); it != hashtable.end();){if (const auto& [_, expireTime] = *it;expireTime <= currentTime)it = hashtable.erase(it);else++it;}
}
代码总体
#include <string>
#include <unordered_map>
using namespace std;class AuthenticationManager
{
public:explicit AuthenticationManager(const int timeToLive): ttl{timeToLive} { }void generate(string tokenId, const int currentTime){hashtable.emplace(std::move(tokenId), currentTime + ttl);}void renew(const string& tokenId, const int currentTime){if (const auto it = hashtable.find(tokenId);it != hashtable.end()){if (it->second > currentTime)it->second = currentTime + ttl;elsehashtable.erase(it);}}int countUnexpiredTokens(const int currentTime){clearExpiredTokens(currentTime);return static_cast<int>(hashtable.size());}private:void clearExpiredTokens(const int currentTime){for (auto it = hashtable.begin(); it != hashtable.end();){if (const auto& [_, expireTime] = *it;expireTime <= currentTime)it = hashtable.erase(it);else++it;}}private:const int ttl;unordered_map<string, int> hashtable;
};
复杂度分析:
-
时间复杂度:
- 构造函数:O(1)O(1)O(1)
- generate():O(1)O(1)O(1),哈希表的插入操作即为 O(1)O(1)O(1) 的时间复杂度。
- renew():O(1)O(1)O(1),哈希表的查找、删除操作均为 O(1)O(1)O(1) 的时间复杂度。
- countUnexpiredTokens():O(n)O(n)O(n),其中 nnn 为哈希表中的验证码元素个数,或者说就是函数
generate()的调用次数。
-
空间复杂度:O(n)O(n)O(n)。其中 nnn 为函数
generate()的调用次数,主要为哈希表的开销。
参考结果
Accepted
90/90 cases passed (76 ms)
Your runtime beats 65.89 % of cpp submissions
Your memory usage beats 89.25 % of cpp submissions (29.3 MB)
若每次调用
generate()和renew()时都打算清理 过期的 验证码,那么由于函数clearExpiredTokens()的时间复杂度为 O(n)O(n)O(n) ,函数generate()和renew()的时间复杂度也会继而变为 O(n)O(n)O(n) 。参考结果如下:
Accepted 90/90 cases passed (92 ms) Your runtime beats 34.58 % of cpp submissions Your memory usage beats 93.46 % of cpp submissions (29.3 MB)
相关文章:
【LeetCode每日一题】【2023/2/9】1797. 设计一个验证系统
文章目录1797. 设计一个验证系统方法1:哈希表代码总体1797. 设计一个验证系统 LeetCode: 1797. 设计一个验证系统 中等\color{#FFB800}{中等}中等 你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在…...
计算机图形学:改进的中点BH算法
作者:非妃是公主 专栏:《计算机图形学》 博客地址:https://blog.csdn.net/myf_666 个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩 文章目录专栏推荐专栏系列文章序一、改进缘由二、…...
【SQL开发实战技巧】系列(六):从执行计划看NOT IN、NOT EXISTS 和 LEFT JOIN效率,记住内外关联条件不要乱放
系列文章目录 【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧…...
十分钟利用环信WebIM-vue3-Demo,打包上线一个即时通讯项目【含音视频通话】
这篇文章无废话,只教你如果接到即时通讯功能需求,十分钟利用环信WebIM-vue3-Demo,打包上线一个即时通讯项目【包含音视频通话功能】。 写这篇文章是因为,结合自身情况,以及所遇到的有同样情况的开发者在接到即时通讯&a…...
pandas——DataFrame基本操作(二)【建议收藏】
pandas——DataFrame基本操作(二) 文章目录pandas——DataFrame基本操作(二)一、实验目的二、实验原理三、实验环境四、实验内容五、实验步骤1.修改数据2.缺失值3.合并1.concat合并2.使用append方法合并3.使用merge进行合并4.使用…...
PostgreSQL查询引擎——General Expressions Grammar之restricted expression
General expressions语法规则定义在src/backend/parser/gram.y文件中,其是表达式语法的核心。有两种表达式类型:a_expr是不受限制的类型,b_expr是必须在某些地方使用的子集,以避免移位/减少冲突。例如,我们不能将BETWE…...
从某种程度上来看,产业互联网是一次对于互联网的弥补和修正
如果对当下我们正在经历的这样一个时代进行一次定义的话,我更加愿意将其划归到产业互联网的范畴里。可能有人会说,这与产业互联网并无联系,因为从本质上来看,当下我们所经历的这样一个时代,其实是与互联网并没有太多联…...
【C#Unity题】1.委托和事件在使用上的区别是什么?2.C#中 == 和 Equals 的区别是什么?
1.委托和事件在使用上的区别是什么? 委托和事件是C#中的重要概念,通俗来讲,委托是一个可以指向特定方法的指针,可以将委托分配给不同的脚本,使它们能够完成不同的任务。而事件则是一种使用委托实现的通知机制ÿ…...
FFmpeg5.0源码阅读——内存池AVBufferPool
摘要:FFmpeg中大多数数据存储比如AVFrame,AVPacket都是通过AVBufferRef管理的,而承载数据的结构为AVBuffer。本文主要通过FFmpeg源码来分析下FFmpeg中AVBuffer相关的实现。 关键字:AVBuffer、AVBufferPool、AVBufferPool 1. AVBufferRef 1.…...
Python学习------起步7(字符串的连接、删除、修改、查询与统计、类型判断及字符串字母大小写转换)
目录 前言: 1.字符串的连接 join() 函数 2.字符串的删除&取代 replace()函数 3.字符串的修改&切割 (1)strip() 函数 (2)lstrip()函数 和 rstrip()函数 (3)split()函数-->…...
雪花算法snowflake
snowflake中文的意思是 雪花,雪片,所以翻译成雪花算法。它最早是twitter内部使用的分布式环境下的唯一ID生成算法。在2014年开源。雪花算法产生的背景当然是twitter高并发环境下对唯一ID生成的需求,得益于twitter内部高超的技术,雪…...
Part 4 描述性统计分析(占比 10%)——上
文章目录【后续会持续更新CDA Level I&II备考相关内容,敬请期待】【考试大纲】【考试内容】【备考资料】1、统计基本概念1.1、统计学的含义及应用1.1.1、统计学的含义1.2.1、统计学的应用1.2、统计学的基本概念1.2.1、数据及数据的分类1.2.2、总体和样本1.2.3、…...
Linux系统安全:安全技术和防火墙
目录 一、安全技术 1、安全技术 2、防火墙分类 二、防火墙 1、iptables五表五链 2、黑白名单 3、iptables基本语法 4、iptables选项 5、控制类型 6、隐藏扩展模块 7、显示扩展模块 8、iptables规则保存 9、自定义链使用 一、安全技术 1、安全技术 ①入侵检测系统…...
【干货】Python:turtle库的用法
【干货】Python:turtle库的用法1. turtle库概述2. turtle库与基本绘图2.1 导入库的三种方式2.1.12.1.22.1.32.2 窗体函数2.2 画笔状态函数2.2.1 seed(s)2.2.2 random()2.2.3 randint(a, b)2.2.4 getrandbits(k)2.2.5 randrange(start, stop[ , step])2.2.6 uniform(…...
信息安全与网络安全有什么区别?
生活中我们经常会听到要保障自己的或者企业的信息安全。那到底什么是信息安全呢?信息安全包含哪些内容?与网络安全又有什么区别呢?今天我们就一起来详细了解一下。什么叫做信息安全?信息安全定义如下:为数据处理系统建…...
花了5年时间,用过市面上95%的工具,终于找到这款万能报表工具
经常有粉丝问我有“哪个报表工具好用易上手?”或者是“有哪些适合绝大多数普通职场人的万能报表工具?” 从这里我大概总结出了大家选择报表工具最期望满足的3点: (1)简单易上手:也就是所谓的学习门槛要低…...
ESP32S3系列--SPI主机驱动详解(一)
一、目的SPI是一种串行同步接口,可用于与外围设备进行通信。ESP32S3自带4个SPI控制器外设,其中SPI0/SPI1内部专用,共用一组信号线,通过一个仲裁器访问外部Flash和PSRAM;SPI2/3各自使用一组信号线;开发者可以使用SPI2/3控制外部SPI…...
2023开工开学火热!远行的人们,把淘特箱包送上顶流
春暖花开,被疫情偷走的三年在今年开学季找补回来了。多个数据反馈,居民消费意愿大幅提升。在淘特上,开工开学节点就很是明显:1月30日以来,淘特箱包品类甚至远超2022年双11,成为开年“第一爆品”。与此同时&…...
Intel x86_64 PMU简介
文章目录前言一、性能监控概述二、CPUID information三、架构性能监控3.1 架构性能监控 Version 13.1.1 架构性能监控 Version 1 Facilities3.1.2 预定义的体系结构性能事件3.1.3 cmask demo测试参考资料前言 Intel 64 和 IA-32 架构提供了 PMU(Performance Monito…...
Vue (2)
文章目录1. 模板语法1.1 插值语法1.2 指令语法2. 数据绑定3. 穿插 el 和 data 的两种写法4. MVVM 模型1. 模板语法 root 容器中的代码称为 vue 模板 1.1 插值语法 1.2 指令语法 图一 : 简写 : v-bind: 是可以简写成 : 的 总结 : …...
SDXL-Turbo在虚拟现实中的应用:实时环境生成技术
SDXL-Turbo在虚拟现实中的应用:实时环境生成技术 想象一下,在虚拟世界中每走一步,周围的景色就随之变化——茂密的森林在你眼前生长,古老的城堡在远处拔地而起,这一切都发生在眨眼之间。这不是魔法,而是SDX…...
裂隙注浆模拟:当岩层遇上高粘度浆液
在COMSOL中运用水平集法和蠕动流模块模拟裂隙注浆过程,考虑浆液—岩体的耦合作用。 一般而言,裂隙开度越大,浆液所需注入压力越小。 本算例从结果来看可以验证此定律。 裂隙变形的本构取之于已发表的文献。 本算例中,初始时刻裂隙…...
TI DSP BootLoader实战:从Flash分区到安全跳转的工程化指南
1. 为什么需要BootLoader? 想象一下你家的空调遥控器突然需要升级功能,但厂家要求必须拆开外壳用专用设备烧录——这显然不现实。BootLoader就是嵌入式设备的"遥控器升级按钮",让设备在出厂后仍能通过常规接口(如串口、…...
次元画室+AI绘图工作流:从文字描述到精准提示词的无缝衔接
次元画室AI绘图工作流:从文字描述到精准提示词的无缝衔接 1. 为什么需要AI绘图工作流? 在动漫角色设计领域,创作者们长期面临一个核心矛盾:脑海中有丰富的创意,却难以准确转化为视觉形象。传统工作流程中,…...
Llama-3.2V-11B-cot部署案例:中小企业低成本构建AI图文分析工作台
Llama-3.2V-11B-cot部署案例:中小企业低成本构建AI图文分析工作台 1. 项目概述 Llama-3.2V-11B-cot是基于Meta最新多模态大模型开发的专业级视觉推理工具,专为中小企业打造的低成本AI图文分析解决方案。该工具针对双卡RTX 4090环境进行了深度优化&…...
ccmusic-database新手教程:Gradio输出组件定制——增强Top5结果可读性技巧
ccmusic-database新手教程:Gradio输出组件定制——增强Top5结果可读性技巧 1. 项目简介与背景 ccmusic-database是一个基于深度学习的音乐流派分类系统,它能够自动识别音频文件所属的音乐流派。这个系统在计算机视觉预训练模型VGG19_BN的基础上进行微调…...
5分钟搞定黑苹果音频驱动:AppleALC新手配置指南
5分钟搞定黑苹果音频驱动:AppleALC新手配置指南 【免费下载链接】AppleALC Native macOS HD audio for not officially supported codecs 项目地址: https://gitcode.com/gh_mirrors/ap/AppleALC AppleALC是一款强大的开源内核扩展工具,能让非官方…...
基于ZLMediaKit API的Java流媒体服务实战:从配置到核心功能封装
1. ZLMediaKit快速入门与环境搭建 第一次接触ZLMediaKit时,我被它的轻量级和高性能所吸引。作为一款开源的流媒体服务器,它支持RTSP、RTMP、HLS等多种协议,特别适合中小型视频项目的快速部署。记得当时为了测试性能,我在一台2核4G…...
AI 大模型落地系列|Eino 组件核心篇:ChatTemplate 为什么不是字符串拼接
声明:本文数据源于官方文档与官方实现,重点参考 ChatTemplate 使用说明。 为什么很多人学 Eino 后,写 Prompt 时还是把 ChatTemplate 用成了字符串拼接?1. ChatTemplate 是什么,不是什么2. 接口虽短,但起的…...
6大终极方案!WarcraftHelper全方位解决魔兽争霸III在Win10/11兼容性难题
6大终极方案!WarcraftHelper全方位解决魔兽争霸III在Win10/11兼容性难题 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 经典游戏魔兽争霸…...
