设计一个验证系统
难度:
标签:
题目描述
你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 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 <= 1081 <= currentTime <= 1081 <= tokenId.length <= 5tokenId只包含小写英文字母。- 所有
generate函数的调用都会包含独一无二的tokenId值。 - 所有函数调用中，
currentTime的值 严格递增 。 - 所有函数的调用次数总共不超过
2000次。
代码结果
运行时间: 80 ms, 内存: 18.6 MB
/*
* 思路：
* 1. 使用一个HashMap存储tokenId和它的过期时间。
* 2. generate方法：将tokenId和它的过期时间（currentTime + timeToLive）存入HashMap。
* 3. renew方法：检查tokenId是否存在且未过期，如果是，则更新它的过期时间。
* 4. countUnexpiredTokens方法：使用Java Stream API统计所有未过期的token数。
*/
import java.util.HashMap;
import java.util.Map;
public class AuthenticationManagerStream {
private int timeToLive;
private Map<String, Integer> tokens;
public AuthenticationManagerStream(int timeToLive) {
this.timeToLive = timeToLive;
this.tokens = new HashMap<>();
}
public void generate(String tokenId, int currentTime) {
tokens.put(tokenId, currentTime + timeToLive);
}
public void renew(String tokenId, int currentTime) {
if (tokens.containsKey(tokenId) && tokens.get(tokenId) > currentTime) {
tokens.put(tokenId, currentTime + timeToLive);
}
}
public int countUnexpiredTokens(int currentTime) {
tokens.entrySet().removeIf(entry -> entry.getValue() <= currentTime);
return (int) tokens.values().stream().filter(expiryTime -> expiryTime > currentTime).count();
}
}
解释
方法:
本题解采用了双向链表与哈希表结合的数据结构，以便高效地管理和更新验证码的过期时间。双向链表用于记录过期时间的顺序，而哈希表则用于快速访问任意的 tokenId。初始化时，建立一个头尾哨兵节点以方便操作。生成验证码时，将新节点插入到双向链表的尾部，并在哈希表中记录。更新验证码时，如果未过期，则从链表中移除该节点，并重新插入到尾部。计数时，从头节点开始移除所有过期的节点，并返回哈希表的大小，即未过期的验证码数。
时间复杂度:
O(1)
空间复杂度:
O(n)
代码细节讲解
🦆
在设计中选用双向链表和哈希表结合的数据结构有哪些特定的优势？
▷🦆
为什么在`generate`方法中要将新节点插入到链表的尾部，而不是头部或中间？
▷🦆
在进行`renew`操作时，你是如何确保节点在移除后再正确插入到链表尾部的？
▷🦆
在`countUnexpiredTokens`方法中，为何选择从头节点开始遍历移除过期节点，这样做的效率如何？
▷