LC 1797. 设计一个验证系统

题目描述

这是 LeetCode 上的 1797. 设计一个验证系统 ，难度为 中等。

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

---

哈希表

数据范围只有 20，我们使用哈希表记录每个 id 的过期时间 ct，在每次查询时遍历整个哈希表来统计未过期的验证码数量。

代码：

class AuthenticationManager {
    int d;
    Map<String, Integer> map = new HashMap<>();
    public AuthenticationManager(int timeToLive) {
        d = timeToLive;
    }
    public void generate(String id, int ct) {
        map.put(id, ct + d);
    }
    public void renew(String id, int ct) {
        if (!map.containsKey(id) || map.get(id) <= ct) return ;
        map.put(id, ct + d);
    }
    public int countUnexpiredTokens(int ct) {
        int ans = 0;
        for (String id : map.keySet()) {
            if (map.get(id) > ct) ans++;
        }
        return ans;
    }
}

• 时间复杂度：generate 操作和 renew 操作的复杂度为 $O(1)$；countUnexpiredTokens 操作的复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

双向链表

在所有函数的调用过程中，timeToLive 都在单调递增。

在哈希表的做法里，我们没有清理旧验证码的操作，同时每次执行 countUnexpiredTokens 时，需要对整个哈希表进行遍历。

实际上，如果我们引入 双向链表，并将哈希表的键值对定义从 {验证码:过期时间值} 调整为 {验证码:链表节点} 时（链表节点属性仅包含验证码字符串 id 及其过期时间 t），我们便能实现如下优化：

• 减少统计未过期验证码时的无效遍历：由于构建的双向链表严格按照 timeToLive 递增，因此可以从尾部出发，从后往前利用链表节点的 prev 指针进行遍历统计。

  如此一来，有多少未过期的验证码，我们就会遍历多少个链表节点，其余已过期的节点对象并不会被访问；

• 引入清理时机：由于上述的统计过程，我们会找到最靠前的一个未过期节点。可以将其作为新的双向链表新头结点，从而将整段的过期节点从双向链表中删除

最后，我们像对其他链表题目一样，为了方便，引入 he 和 ta 的头尾链表哨兵节点以减少边界处理。

代码：

class AuthenticationManager {
    class Node {
        String id;
        int t;
        Node prev, next;
        Node (String _id, int _t) {
            id = _id; t = _t;
        }
    }
    int d;
    Node he, ta;
    Map<String, Node> map = new HashMap<>();
    public AuthenticationManager(int timeToLive) {
        he = new Node("", -1); ta = new Node("", (int)1e9);
        he.next = ta; ta.prev = he;
        d = timeToLive;
    }
    public void generate(String id, int ct) {
        Node node = new Node(id, ct + d);
        node.prev = ta.prev;
        node.next = ta;
        ta.prev.next = node;
        ta.prev = node;
        map.put(id, node);
    }
    public void renew(String id, int ct) {
        if (!map.containsKey(id) || map.get(id).t <= ct) return ;
        Node node = map.get(id);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        generate(id, ct);
    }
    public int countUnexpiredTokens(int ct) {
        int ans = 0;
        Node cur = ta.prev;
        while (cur.t > ct && ++ans >= 0) cur = cur.prev;
        he.next = cur.next;
        cur.next.prev = he;
        return ans;
    }
}

• 时间复杂度：generate 操作和 renew 操作的复杂度为 $O(1)$；countUnexpiredTokens 操作的复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1797 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。