【LeetCode每日一题】【2023/2/9】1797. 设计一个验证系统
创始人
2024-05-23 16:29:13
0

文章目录

  • 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^8
  • 1 <= currentTime <= 10^8
  • 1 <= tokenId.length <= 5
  • tokenId 只包含小写英文字母。
  • 所有 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(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 
#include 
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(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 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) 

相关内容

热门资讯

功夫熊猫中的经典台词 功夫熊猫中的经典台词  1、一切都不是偶然。  2、何必躲呢,躲不过的。  3、着急的时候脑子也乱了...
《十全九美》的台词 《十全九美》的台词  1、艺人啊 要是不红那就是死 要是红了… 那是生不如死 !  2、南宫小姐被太...
中秋节晚会上的主持词 关于中秋节晚会上的主持词(精选5篇)  主持词需要富有情感,充满热情,才能有效地吸引到观众。在当下的...
民主生活会主持词 民主生活会主持词  一、主持词简介  由主持人于节目进行过程中串联节目的串联词。如今的各种演出活动和...
2022年央视春节联欢晚会主... 2022年央视春节联欢晚会主持词  借鉴诗词和散文诗是主持词的一种写作手法。在现今人们越来越重视活动...
少先队建队日主持词 少先队建队日主持词  什么是主持词  由主持人于节目进行过程中串联节目的串联词。如今的各种演出活动和...
晚会节目串词主持稿 晚会节目串词主持稿  在现在社会,很多地方都会使用到主持稿,通过主持稿的写作将主题贯穿于所有的节目之...
幼儿园开园揭牌剪彩仪式主持词 幼儿园开园揭牌剪彩仪式主持词  主持词要把握好吸引观众、导入主题、创设情境等环节以吸引观众。在一步步...
公司辞旧迎新晚会主持词串词   男:尊敬的各位领导、各位来宾,  女:亲爱的同事们  合:大家下午好!  男:光阴似箭,岁月如梭...
纯中式婚礼主持词 纯中式婚礼主持词(通用5篇)  主持词是主持人在台上表演的灵魂之所在。在现在的社会生活中,越来越多的...
悟空传的经典台词 悟空传的经典台词  1、我曾深爱过,我不在乎结局。  2、我知道天会愤怒,那,你知不知道,天也会颤抖...
最有创意的广告词(经典 最有创意的广告词(经典  01 钱不是问题,问题是没钱。  02 钻石恆久远,一颗就破產。  03 ...
毕业感谢致辞 关于毕业感谢致辞(精选15篇)  无论是在学校还是在社会中,大家都写过致辞吧,致辞的措词造句要考虑与...
年会嘉宾简短致辞 年会嘉宾简短致辞  在日复一日的学习、工作或生活中,大家总少不了要接触或使用致辞吧,致辞具有很强的实...
成长礼主持稿 成长礼主持稿(通用8篇)  在日常生活和工作中,需要使用主持稿的情况越来越多,主持稿是在晚会、联欢会...
电视剧《放羊的星星》经典台词 电视剧《放羊的星星》经典台词  在现实社会中,用到台词的地方越来越多,台词是一种特殊的,也是很难掌握...
抓周仪式主持词 抓周仪式主持词范文  主持词是主持人在台上表演的灵魂之所在。在如今这个中国,主持词是活动、集会等的必...
年终总结大会主持词结束语 年终总结大会主持词结束语  主持词是各种演出活动和集会中主持人串联节目的串联词。时代不断在进步,主持...
纯中式婚礼主持词(2) 让我们共同举起手中的酒杯,共同祝福我们这一对知心爱人,祝福他们在爱的旅途上风雨相承,相濡以沫,真爱一...
幼儿园园庆主持词 幼儿园园庆主持词  利用在中国拥有几千年文化的诗词能够有效提高主持词的感染力。在人们积极参与各种活动...