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
| class Logger {
private Deque<Pair<Integer, String>> q;
private Set<String> occurred;
private String emptyString;
public Logger() {
q = new ArrayDeque<>();
occurred = new HashSet<>();
emptyString = "";
}
public boolean shouldPrintMessage(int timestamp, String message) {
int expirationTime = timestamp - 10;
while (!q.isEmpty() && q.peek().getKey() <= expirationTime) {
occurred.remove(q.poll().getValue());
}
if (occurred.contains(message)) {
return false;
} else {
q.offer(new Pair<>(timestamp, message));
occurred.add(message);
return true;
}
}
}
|
这个是用queue记录目前print过但还没超时的message, 然后Set可以让我们快速知道没超时的message中是否有我们想要print的. 这道题需要注意的是, 比如1时刻来个foo, 那么5时刻来的foo不会被print, 当11时刻来的时候, 我们不会因为上一次foo出现的时刻是5时刻而不print而是看上一次print的时候是什么时候, 那是1时刻, 因此我们此时可以print. 因此当我们print完之后, 我们才在set和queue中记录.
时间复杂度: O(n)
空间复杂度: O(n)
