绍兴优秀做网站的,百度站长论坛,做网站经常加班还是app,屏蔽wordpress头像一、题目
你需要设计一个包含验证码的验证系统。每一次验证中#xff0c;用户会收到一个新的验证码#xff0c;这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了#xff0c;那么它会在 currentTime #xff08;可能与之前的 currentTime 不同用户会收到一个新的验证码这个验证码在 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 操作过期事件 优先于 其他操作。
示例 来源力扣LeetCode 链接
二、C解法
我的思路及代码
此代码在力扣超时但是我觉得力扣评判的不标准 用两个哈希表第一个存储token到期时间第二个存储当前时间有几个未过期的token。 新建操作更新token的到期时间并且更新这个持续时间中的token数量。 更新操作判断当前token是否到期若还有效则更新token的到期时间并且从原来的到期时间开始直到新的到期时间结束的时间内继续增加token数量。
class AuthenticationManager {
public:int timeToLive;unordered_mapstring,int tokenAndTimePast;unordered_mapint,int countTokens;AuthenticationManager(int timeToLive) {this-timeToLive timeToLive;}void generate(string tokenId, int currentTime) {tokenAndTimePast[tokenId] currentTimetimeToLive;for(int icurrentTime;icurrentTimetimeToLive;i){countTokens[i];}}void renew(string tokenId, int currentTime) {//当tokenId不存在的时候他对应的值为0所以可以用这个条件来判断if(tokenAndTimePast[tokenId]currentTime){for(int itokenAndTimePast[tokenId];icurrentTimetimeToLive;i){countTokens[i];}tokenAndTimePast[tokenId] currentTimetimeToLive;}}int countUnexpiredTokens(int currentTime) {return countTokens[currentTime];}
};/*** Your AuthenticationManager object will be instantiated and called as such:* AuthenticationManager* obj new AuthenticationManager(timeToLive);* obj-generate(tokenId,currentTime);* obj-renew(tokenId,currentTime);* int param_3 obj-countUnexpiredTokens(currentTime);*/时间复杂度构造函数O(1)generateO(n)其中 n 为 currentTime 的秒数renewO(n)其中 n 为 currentTime 的秒数官方写的countUnexpiredTokensO(n)其中 n 为 generate 的调用次数。空间复杂度O(n)两个 map 中 n 都为 generate 的调用次数。
官方参考代码
class AuthenticationManager {
private:int timeToLive;unordered_mapstring, int mp;
public:AuthenticationManager(int timeToLive) {this-timeToLive timeToLive;}void generate(string tokenId, int currentTime) {mp[tokenId] currentTime timeToLive;}void renew(string tokenId, int currentTime) {if (mp.count(tokenId) mp[tokenId] currentTime) {mp[tokenId] currentTime timeToLive;}}int countUnexpiredTokens(int currentTime) {int res 0;for (auto [_, time] : mp) {if (time currentTime) {res;}}return res;}
};
时间复杂度构造函数O(1)generateO(1)renewO(1)官方写的countUnexpiredTokensO(n)其中 n 为 generate 的调用次数。我认为的countUnexpiredTokens里面带有 for 循环循环次数和 mp 的个数相关而 mp 的个数和 tokenId 的数量相关所以我认为是 countUnexpiredTokens O(nt)其中 n 为 generate 的调用次数t 为 tokenId 的数量。空间复杂度O(n)其中 n 为 generate 的调用次数map 中有 n 个元素。
