设计一个验证系统【LC1797】

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 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 操作），过期事件 优先于 其他操作。

• 思路：

  使用哈希表存储每个验证码的过期时间，哈希表的key为本次请求的tokenId，value为该验证码的过期时间，为请求的currentTime+timeToLive

  • generate(string tokenId, int currentTime)：在哈希表中添加新的验证码及其过期时间
  • renew(string tokenId, int currentTime) ：如果该tokenId不存在或者存在并且未过期时，更新过期时间
  • countUnexpiredTokens(int currentTime) ：遍历哈希表，统计过期时间大于 currentTime 的验证码数目

• 实现

  class AuthenticationManager {Map idToEnd;int timeToLive;public AuthenticationManager(int timeToLive) {this.timeToLive = timeToLive;idToEnd = new HashMap<>();}public void generate(String tokenId, int currentTime) {idToEnd.put(tokenId, currentTime + timeToLive);}public void renew(String tokenId, int currentTime) {if (idToEnd.containsKey(tokenId) && idToEnd.get(tokenId) > currentTime){idToEnd.put(tokenId, currentTime + timeToLive); }}public int countUnexpiredTokens(int currentTime) {int size = 0;for (var node : idToEnd.entrySet()){if (node.getValue() > currentTime){size++;}}return size;}
  }/*** 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);*/
  

  • 复杂度
    • 时间复杂度：generate、renew的时间复杂度为O(1)O(1)O(1)，countUnexpiredTokens的时间复杂度为O(n)O(n)O(n)
    • 空间复杂度：O(n)O(n)O(n)