LC 1797. 设计一个验证系统

题目描述

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

你需要设计一个包含验证码的验证系统。

每一次验证中,用户会收到一个新的验证码,这个验证码在 ct 时刻之后 timeToLive 秒过期。

如果验证码被更新了,那么它会在 ct (可能与之前的 ct 不同)时刻延长 timeToLive 秒。

请你实现 AuthenticationManager 类:

  • AuthenticationManager(int timeToLive) 构造 AuthenticationManager 并设置 timeToLive 参数。

  • generate(string id, int ct) 给定 id,在当前时间 ct 生成一个新的验证码。

  • renew(string id, int ct) 将给定 id 且未过期的验证码在 ct 时刻更新。

    如果给定 id 对应的验证码不存在或已过期,请你忽略该操作,不会有任何更新操作发生。

  • countUnexpiredTokens(int ct) 请返回在给定 ct 时刻,未过期的验证码数目。

如果一个验证码在时刻 t 过期,且另一个操作恰好在时刻 t 发生(renew 或者 countUnexpiredTokens 操作),过期事件优先于其他操作。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入:
["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$
  • id 只包含小写英文字母。
  • 所有 generate 函数的调用都会包含独一无二的 id 值。
  • 所有函数调用中,ct 的值严格递增。
  • 所有函数的调用次数总共不超过 2000 次。

哈希表

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

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class AuthenticationManager {
int d;
unordered_map<string, int> map;
public:
AuthenticationManager(int timeToLive) : d(timeToLive){}
void generate(string id, int ct) {
map[id] = ct + d;
}
void renew(string id, int ct) {
if (!map.count(id) || map[id] <= ct) return;
map[id] = ct + d;
}
int countUnexpiredTokens(int ct) {
int ans = 0;
for (auto it = map.begin(); it != map.end(); ++it) {
if (it->second > ct) ans++;
}
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class AuthenticationManager:
def __init__(self, timeToLive):
self.d = timeToLive
self.map = {}

def generate(self, id: str, ct: int) -> None:
self.map[id] = ct + self.d

def renew(self, id: str, ct: int) -> None:
if id not in self.map or self.map[id] <= ct:
return
self.map[id] = ct + self.d

def countUnexpiredTokens(self, ct: int) -> int:
ans = 0
for id in self.map:
if self.map[id] > ct:
ans += 1
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class AuthenticationManager {
d: number;
map: { [id: string]: number } = {};

constructor(timeToLive: number) {
this.d = timeToLive;
}

generate(id: string, ct: number): void {
this.map[id] = ct + this.d;
}

renew(id: string, ct: number): void {
if (!this.map.hasOwnProperty(id) || this.map[id] <= ct) {
return;
}
this.map[id] = ct + this.d;
}

countUnexpiredTokens(ct: number): number {
let ans = 0;
for (const id in this.map) {
if (this.map[id] > ct) {
ans++;
}
}
return ans;
}
}

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

双向链表

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

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

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

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

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

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

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

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class AuthenticationManager {
struct Node {
string id;
int t;
Node *prev, *next;
Node (string _id, int _t) : id(_id), t(_t), prev(nullptr), next(nullptr) {}
};
int d;
Node *he, *ta;
unordered_map<string, Node*> map;
public:
AuthenticationManager(int timeToLive) : d(timeToLive) {
he = new Node("", -1);
ta = new Node("", (int)1e9);
he->next = ta;
ta->prev = he;
}
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[id] = node;
}
void renew(string id, int ct) {
if (!map.count(id) || map[id]->t <= ct) return;
Node* node = map[id];
node->prev->next = node->next;
node->next->prev = node->prev;
generate(id, ct);
}
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;
}
};

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Node {
id: string;
t: number;
prev: Node | null;
next: Node | null;
constructor(_id: string, _t: number) {
this.id = _id;
this.t = _t;
this.prev = null
this.next = null
}
}
class AuthenticationManager {
d: number;
he: Node;
ta: Node;
map: {[id: string]: Node};
constructor(timeToLive: number) {
this.d = timeToLive;
this.he = new Node("", -1)
this.ta = new Node("", 1e9)
this.he.next = this.ta
this.ta.prev = this.he
this.map = {};
}

generate(id: string, ct: number) {
let node : Node = new Node(id, ct + this.d) ;
node.prev = this.ta.prev;
node.next = this.ta;
this.ta.prev!.next = node;
this.ta.prev = node;
this.map[id] = node;
}

renew(id: string, ct: number) {
if (!this.map.hasOwnProperty(id) || this.map[id].t <= ct) {
return;
}
var node : Node = this.map[id];
node.prev!.next = node.next;
node.next!.prev = node.prev;
this.generate(id, ct);
}

countUnexpiredTokens(ct: number) {
let ans = 0;
let cur : Node = this.ta.prev!;
while (cur.t > ct && ++ans >= 0)
cur = cur.prev!;
this.he.next = cur.next;
cur.next!.prev = this.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 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!