【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) 

相关内容

热门资讯

文艺汇演主持词开场白 文艺汇演主持词开场白9篇  根据活动对象的不同,需要设置不同的主持词。我们眼下的社会,活动集会越来越...
总结大会主持词   导语:春去秋回又一栽,似水流年旺年来。  2017年公司年会主持词  一.主持人开场白  男:一...
农村结婚典礼主持词 农村结婚典礼主持词  一对新人立堂前,两心相印似蜜甜,三生有幸结良缘,下面是小编分享的 农村结婚典礼...
春节联欢晚会主持词开场白   翻开精美的日历,我细数着春节将要来临。那是我们中华民族的传统节日,更是我期盼的佳节,因为只有这几...
真爱至上中英文经典台词 真爱至上中英文经典台词  1、All I want for Christmas is you.  今...
欢聚一堂舞蹈主持词 欢聚一堂舞蹈主持词  串词是在晚会、联欢会等大型联欢活动中,主持人把前后节目,把整台节目恰到好处的联...
主持词结束语 主持词结束语(通用12篇)  利用在中国拥有几千年文化的诗词能够有效提高主持词的感染力。在人们越来越...
秋季小学开学典礼校长的致辞 秋季小学开学典礼校长的致辞(通用13篇)  在学习、工作、生活中,许多人都有过写致辞的经历,对致辞都...
五月的主持词开场白 五月的主持词开场白  主持人在台上表演的灵魂就表现在主持词中。在当下这个社会中,各种场合中活跃现场气...
重阳节优秀致辞 重阳节优秀致辞范文  无论是身处学校还是步入社会,大家都用到过致辞吧,在各种重大的庆典、外交、纪念活...
QQ群晚会开幕词 QQ群晚会开幕词  QQ群晚会开幕词    尊贵的各位嘉宾,群主,各位管理,群友们大家晚上好:   ...
主持谢幕词 主持谢幕词范本  篇一:主持谢幕词  愿一切荣耀、尊贵、颂赞都归给至高上帝!  都说“台上一分钟,台...
圣诞节联欢晚会主持词 圣诞节联欢晚会主持词  主持词的写作需要将主题贯穿于所有节目之中。在一步步向前发展的社会中,主持词与...
元宵节的主持词 元宵节的主持词  一般在节日的时候,都是会举行一些活动的,尤其是在元宵节这个大型的节日。下面是小编为...
初中生晨会主持词 初中生晨会主持词(通用5篇)  主持词要尽量增加文化内涵、寓教于乐,不断提高观众的文化知识和素养。现...
晨会主持词开场白   开晨会是公司职场管理的规章制度,那么公司晨会主持如何开场白好呢?以下是小编为大家搜集整理提供到的...
企业年会主持词 企业年会主持词  主持词是主持人在台上表演的灵魂之所在。在人们越来越多的参与各种活动的今天,主持词是...
企业晚会的主持词 企业晚会的主持词  借鉴诗词和散文诗是主持词的一种写作手法。在人们越来越多的参与各种活动的今天,主持...
年终总结会主持词 2021年终总结会主持词范文(精选13篇)  契合现场环境的主持词能给集会带来双倍的效果。现今社会在...
半台词爆笑 三句半台词大全爆笑  三句半是一种中国民间群众传统曲艺表演形式,下面是为带大家整理的爆笑的'三句半台...