设计一个验证系统

难度: Medium

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 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⁸
1 <= currentTime <= 10⁸
1 <= tokenId.length <= 5
tokenId 只包含小写英文字母。
所有 generate 函数的调用都会包含独一无二的 tokenId 值。
所有函数调用中，currentTime 的值 严格递增 。
所有函数的调用次数总共不超过 2000 次。

Submission

运行时间: 80 ms

内存: 18.6 MB

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.map = {}


    def generate(self, tokenId: str, currentTime: int) -> None:
        node = Node(currentTime+self.ttl, tokenId)
        self.map[tokenId] = node
        last = self.tail.prev
        last.next = node
        node.prev = last
        self.tail.prev = node
        node.next = self.tail


    def renew(self, tokenId: str, currentTime: int) -> None:
        if tokenId in self.map and self.map[tokenId].expire>currentTime:
            node = self.map[tokenId]
            prev = node.prev
            next = node.next
            prev.next = next
            next.prev = prev
            node.expire = currentTime+self.ttl
            last = self.tail.prev
            last.next = node
            node.prev =last
            self.tail.prev = node
            node.next = self.tail
            


    def countUnexpiredTokens(self, currentTime: int) -> int:
        while self.head.next.expire != -1 and self.head.next.expire <= currentTime:
            node = self.head.next
            self.map.pop(node.key)
            self.head.next = node.next
            node.next.prev = self.head
        return len(self.map)

class Node:
    
    def __init__(self, val=0, key=None, prev=None, next=None):
        self.expire = val
        self.key = key
        self.prev = prev
        self.next = next



# Your AuthenticationManager object will be instantiated and called as such:
# obj = AuthenticationManager(timeToLive)
# obj.generate(tokenId,currentTime)
# obj.renew(tokenId,currentTime)
# param_3 = obj.countUnexpiredTokens(currentTime)

Explain

本题解采用了双向链表与哈希表结合的数据结构，以便高效地管理和更新验证码的过期时间。双向链表用于记录过期时间的顺序，而哈希表则用于快速访问任意的 tokenId。初始化时，建立一个头尾哨兵节点以方便操作。生成验证码时，将新节点插入到双向链表的尾部，并在哈希表中记录。更新验证码时，如果未过期，则从链表中移除该节点，并重新插入到尾部。计数时，从头节点开始移除所有过期的节点，并返回哈希表的大小，即未过期的验证码数。

时间复杂度: O(1)

空间复杂度: O(n)

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.ttl = timeToLive  # 设置验证码的存活时间
        self.head = Node(-1)  # 头哨兵节点
        self.tail = Node(-1)  # 尾哨兵节点
        self.head.next = self.tail
        self.tail.prev = self.head
        self.map = {}  # 哈希表存储 tokenId 和其对应的节点


    def generate(self, tokenId: str, currentTime: int) -> None:
        node = Node(currentTime+self.ttl, tokenId)  # 创建新节点，过期时间为当前时间加上生存时间
        self.map[tokenId] = node  # 将节点放入哈希表
        last = self.tail.prev  # 找到最后一个有效节点
        last.next = node  # 将新节点插入到链表尾部
        node.prev = last
        self.tail.prev = node
        node.next = self.tail


    def renew(self, tokenId: str, currentTime: int) -> None:
        if tokenId in self.map and self.map[tokenId].expire > currentTime:  # 如果 tokenId 存在且未过期
            node = self.map[tokenId]
            prev = node.prev
            next = node.next
            prev.next = next  # 从链表中移除节点
            next.prev = prev
            node.expire = currentTime+self.ttl  # 更新过期时间
            last = self.tail.prev
            last.next = node  # 将更新后的节点重新插入到链表尾部
            node.prev = last
            self.tail.prev = node
            node.next = self.tail


    def countUnexpiredTokens(self, currentTime: int) -> int:
        while self.head.next.expire != -1 and self.head.next.expire <= currentTime:  # 移除所有过期节点
            node = self.head.next
            self.map.pop(node.key)  # 从哈希表中移除
            self.head.next = node.next
            node.next.prev = self.head
        return len(self.map)  # 返回未过期的节点数

class Node:
    
    def __init__(self, val=0, key=None, prev=None, next=None):
        self.expire = val  # 节点过期时间
        self.key = key  # tokenId
        self.prev = prev  # 前驱节点
        self.next = next  # 后继节点

Explore

双向链表和哈希表的结合提供了高效的数据管理和访问优势。哈希表允许我们以O(1)的时间复杂度快速地访问任意的tokenId，这使得查找和更新操作非常迅速。而双向链表则用于维护和更新有序的过期时间列表，使得过期的token可以快速地被从链表头部移除，同时新的或被更新的token可以被迅速添加到链表尾部。此外，双向链表中的每个节点既有前驱也有后继链接，这使得节点的插入和删除操作都能直接通过节点连接，避免了复杂的节点搜索过程。

在`generate`方法中将新节点插入到链表的尾部是因为这样可以维持链表按照节点过期时间的有序状态。通常，新生成的token拥有最晚的过期时间，因此将它们插入到尾部使得链表始终按过期时间从早到晚排序。如果将新节点插入到头部或中间，将需要额外的时间去找到正确的插入位置，这会降低操作的效率。

在进行`renew`操作时，首先检查指定的tokenId是否存在并确定其未过期。然后，通过访问哈希表直接获取到对应的节点，使用节点的前驱和后继链接将其从链表中移除。移除后，更新节点的过期时间，并利用链表尾部哨兵节点的前一个节点（即当时的最后一个节点），将当前节点重新链接至链表尾部。这种方法依靠双向链表的连接特性，保证了操作的正确性和高效性。

在`countUnexpiredTokens`方法中，从头节点开始遍历移除过期节点是因为链表是按过期时间有序排列的，最早过期的节点总是在链表的前端。这样可以直接从头部开始检查并移除所有过期的节点，直到遇到一个未过期的节点或到达链表尾部。这种方法是高效的，因为它减少了不必要的遍历，只对过期节点进行操作，并且每个节点只被检查一次。