题目来源:https://leetcode.com/problems/number-of-recent-calls/description/

标记难度:Easy

提交次数:1/1

代码效率:148ms

题意

给定一系列严格递增的ping时间戳,问每个时间戳3000毫秒前共有几次ping。

分析

今天比赛的时候发生了一点incident。实验室没开门,于是我坐在外面的桌子上又冷又没电地打比赛,然后第三题的Dijstra居然还写错了调不出来,最后紧张地在没电和比赛结束之前换成了用priority_queue的做法……(事实证明不加堆优化还是会超时的)然后当然没时间做第四题了。我一眼望去以为第四题要用后缀树之类的做法,结果好像比我想象的要简单。

最后排名是466 / 2948。今天北京下雨了。


直接用队列维护一个时间窗口就可以了。(不知道为什么我比赛的时候用的是deque)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class RecentCounter {
private:
deque<int> pings;

public:
RecentCounter() {

}

int ping(int t) {
while (!pings.empty() && pings.front() < t - 3000)
pings.pop_front();
pings.push_back(t);
return pings.size();
}
};

题目来源:https://leetcode.com/problems/implement-queue-using-stacks/description/

标记难度:Easy

提交次数:3/3

代码效率:

  • 我的做法(两个栈):100.00%
  • 稍微好一点的双栈版本:100.00%
  • 平摊O(1)的双栈版本:100.00%

题意

用栈实现队列。

分析

这道题和Leetcode 225正好对应。不过,栈和队列相比,只有一个出口,所以解法也少一种。

法1:我的做法

我的做法特别简单直接明了,用一个栈(s1)模拟队列(栈顶表示队尾,栈底表示队头),另一个栈(s2)作为临时存储空间。

  • push(x):直接把x放入s1栈顶,时间复杂度为O(1)
  • pop():把s1中的元素逐个弹出并插入到s2中,直到得到位于s1栈底的队头元素;然后把s2中的元素再逐个弹出,放回s1中,时间复杂度是O(n)(因为这里的数据结构是栈,所以临时存储会改变元素的顺序,按照这种思路,只能把元素再重新放回去了)。
  • peek():和pop()的过程基本相同,但不删除队头元素,时间复杂度为O(n)
  • empty():返回s1.empty(),时间复杂度为O(1)

这种做法虽然不算很错,但显然不是一种很聪明的办法:因为栈只有一端是开口的,我还把队头放在不开的那一头,所以pop()peek()都要花费O(n)的时间,相当离谱。

法2:较少的时间复杂度

这种做法的思路和上一种做法很相似,也是用一个栈(s1)模拟队列,另一个栈(s2)作为临时存储空间;主要的区别是,此时用栈顶表示队头,栈底表示队尾。[1]

  • push(x):把s1中的元素逐个弹出并插入到s2中,把x插入s1中,最后再把s2中的元素再逐个弹出,放回s1中。时间复杂度是O(n)

push操作

  • pop():直接从s1栈顶弹出元素,时间复杂度是O(1)

pop操作

  • peek():返回s1栈顶元素,时间复杂度是O(1)
  • empty():返回s1.empty(),时间复杂度是O(1)

法3:平摊O(1)复杂度

这种做法大约是法1的改进版。可以发现,在法1里,进行pop()的过程中,元素在s2中排成了正确的顺序,队头在栈顶。那我们不妨就把这些元素留在s1里面。并且用front变量维护s1栈顶元素。

  • push(x):直接把x放入s1栈顶,维护front,时间复杂度是O(1)

push操作

  • pop():如果s2为空,则把s1中的元素逐个弹出并插入到s2中;从s2中弹出栈顶元素。显然,单次时间复杂度最坏可能是O(n),但并不是每次都需要花这么多时间;事实上,每个元素只会进入s1一次,然后再进入s2一次,所以整体的时间复杂度只有O(1);平摊到每次操作上,就是O(1)

pop操作

  • peek():如果s2不为空,则返回s2栈顶元素;否则返回front。时间复杂度为O(1)
  • empty():返回s1.empty() && s2.empty()。时间复杂度是O(1)

以及,我感觉用栈模拟链表再模拟队列的做法应该也是可行的,不过既然以及有了平摊O(1)的方法,似乎没有这个必要了。

代码

法1

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
class MyQueue {
private:
stack<int> s1, s2;

public:
MyQueue() {

}

void push(int x) {
s1.push(x);
}

int pop() {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
int x = s2.top();
s2.pop();
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
return x;
}

int peek() {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
int x = s2.top();
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
return x;
}

bool empty() {
return s1.empty();
}
};

法2

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
class MyQueue {
private:
stack<int> s1, s2;

public:
MyQueue() {
}

void push(int x) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s1.push(x);
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}

int pop() {
int x = s1.top();
s1.pop();
return x;
}

int peek() {
return s1.top();
}

bool empty() {
return s1.empty();
}
};

法3

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
class MyQueue {
private:
stack<int> s1, s2;

public:
MyQueue() {
}

void push(int x) {
s1.push(x);
}

int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int x = s2.top();
s2.pop();
return x;
}

// 我觉得不维护front变量,而把peek写成和pop类似的形式并不会改变整体的平摊时间复杂度
// 但是可能会增加peek的访问时间
int peek() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}

bool empty() {
return s1.empty() && s2.empty();
}
};

  1. 232. Implement Queue using Stacks(本文中的图片都来自这里)

题目来源:https://leetcode.com/problems/binary-search-tree-iterator/description/

标记难度:Easy

提交次数:4/4

代码效率:

  • 方法1:2个队列:100.00%
  • 方法2:2个队列:100.00%
  • 方法3:1个队列:100.00%
  • 方法4:用队列模拟链表:100.00%

题意

只通过队列实现栈。

分析

方法1:使用两个队列

我的第一反应就是弄两个队列,push(x)的时候, 把x放到第一个队列的队尾;pop()的时候,把第一个队列里的元素依次弹出再插入到第二个队列里,直到把最末一个元素弹出来,然后交换这两个队列。在这种实现下,push(x)的复杂度是O(1)pop()的复杂度是O(n)

方法1的push操作

方法1的pop操作

方法2:仍然是两个队列

另一种类似的思路也是使用两个队列,push(x)的时候,把x放入第二个队列的队尾(此时第二个队列为空),然后把第一个队列里的元素依次弹出,插入到第二个队列中,最后交换两个队列;pop()的时候直接弹出第一个队列的队头。在这种实现下,push(x)的复杂度是O(n)pop()的复杂度是O(1),元素在队列中的顺序正好和上一种做法相反。

方法2的push操作

方法2的pop操作

另一个问题是,还有top()pop()两种操作需要实现,第一种做法的top()操作也是O(n)的(因为栈顶元素在队尾,所以不得不全都重新移动一遍),所以可能第二种做法比较好。

方法3:只使用一个队列

一种更简单的方法是只用一个队列,push(x)的时候,先把x放到队尾,然后把x前面的元素全都弹出,依次插入到x后面;pop()的时候,直接弹出队头。这种方法的复杂度和方法2是相同的。[1]

方法3的push操作

方法4:用队列模拟链表

这是StephanPochmann提出的一种很有创意的方法。简单来说,就是用一个队列表示链表中的一项,队列中一共两个元素,第一个元素是数值,第二个元素是链表指针。然后就可以用链表来表示栈了。在这种做法中,插入和删除都是O(1)的。[2]

代码

方法1(2个队列)

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
class MyStack {
private:
queue<int> q[2];
int cur;

public:
MyStack() {
cur = 0;
}

void push(int x) {
q[cur].push(x);
}

int pop() {
int x;
while (!q[cur].empty()) {
x = q[cur].front();
q[cur].pop();
if (q[cur].empty())
break;
q[(cur + 1) % 2].push(x);
}
cur = (cur + 1) % 2;
return x;
}

int top() {
int x = pop();
push(x);
return x;
}

bool empty() {
return q[cur].empty();
}
};

方法2(2个队列)

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
class MyStack {
private:
queue<int> q[2];
int cur;

public:
MyStack() {
cur = 0;
}

void push(int x) {
q[(cur + 1) % 2].push(x);
while (!q[cur].empty()) {
q[(cur + 1) % 2].push(q[cur].front());
q[cur].pop();
}
cur = (cur + 1) % 2;
}

int pop() {
int x = q[cur].front();
q[cur].pop();
return x;
}

int top() {
return q[cur].front();
}

bool empty() {
return q[cur].empty();
}
};

方法3:1个队列

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
class MyStack {
private:
queue<int> q;

public:
MyStack() {

}

void push(int x) {
q.push(x);
for (int i = 0; i < q.size() - 1; i++) {
q.push(q.front());
q.pop();
}
}

int pop() {
int x = q.front();
q.pop();
return x;
}

int top() {
return q.front();
}

bool empty() {
return q.empty();
}
};

方法4:用队列模拟链表

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 MyStack {
private:
queue<void*>* head;

public:
MyStack() {
head = NULL;
}

/** Push element x onto stack. */
void push(int x) {
queue<void*>* newNode = new queue<void*>();
int* val = new int(x);
newNode->push((void*) val);
newNode->push((void*) head);
head = newNode;
}

int pop() {
int* val = (int*) head->front();
head->pop();
queue<void*>* newHead = (queue<void*>*) head->front();
head->pop();

int x = *val;
delete val;
delete head;
head = newHead;
return x;
}

int top() {
int* val = (int*) head->front();
int x = *val;
return x;
}

bool empty() {
return head == NULL;
}
};

  1. Leetcode 255 Solution

  2. O(1) purely with queues