【每日一题Day113】LC1797设计一个验证系统 | 哈希表

设计一个验证系统【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<String,Integer> 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 )，countUnexpiredTokens的时间复杂度为O ( n )

空间复杂度：O ( n )