杭州网站建设,做维修家具广告在哪个网站好,wordpress html 标签页,阐述商业网站开发岗位需求分析文章目录1797. 设计一个验证系统方法1#xff1a;哈希表代码总体1797. 设计一个验证系统
LeetCode: 1797. 设计一个验证系统 中等\color{#FFB800}{中等}中等 你需要设计一个包含验证码的验证系统。每一次验证中#xff0c;用户会收到一个新的验证码#xff0c;这个验证码在…
文章目录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_castint(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);elseit;}
}代码总体
#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_castint(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);elseit;}}private:const int ttl;unordered_mapstring, 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)
