Markdown File

栈和队列的各自一道练习题

栈和队列的各自一道练习题.md

下载原文件打开 Vercel 原文件

1一、933 最近的请求次数：队列题

3题目要求每次 ping(t) 返回 [t-3000, t] 范围内的请求次数。因为请求时间 t 是递增的，所以可以用队列维护最近 3000ms 内的请求。

51. 核心概念

7每次来了一个新时间 t：

91. 把 t 入队

102. 把小于 t - 3000 的旧请求出队

113. 队列长度就是答案

13队列里始终保存：

14最近 3000ms 内的请求时间

162. 为什么用队列？

18因为时间是递增的。

20旧请求一定在队头，新请求一定从队尾进。

22所以：

24队尾入队新请求

25队头删除过期请求

27正好是 FIFO 队列。

293. C代码模板

30#include <stdlib.h>

32struct RecentCounter {

33 int data[10010];

34 int front;

35 int rear;

36};

38struct RecentCounter* recentCounterCreate() {

39 struct RecentCounter* obj = malloc(sizeof(struct RecentCounter));

40 obj->front = 0;

41 obj->rear = 0;

42 return obj;

43}

45int recentCounterPing(struct RecentCounter* obj, int t) {

46 //让最新的t入队，然后移动rear

47 obj->data[obj->rear] = t;

48 obj->rear++;

50 while (obj->front < obj->rear && obj->data[obj->front] < t - 3000) {

51 //当front对应的data小于t-3000时，就出队

52 obj->front++;

53 }

55 return obj->rear - obj->front;

56}

58void recentCounterFree(struct RecentCounter* obj) {

59 free(obj);

60}

624. 例子

63ping(1)

64队列：[1]

65范围：[-2999, 1]

66答案：1

68ping(100)

69队列：[1, 100]

70范围：[-2900, 100]

71答案：2

73ping(3001)

74队列：[1, 100, 3001]

75范围：[1, 3001]

76答案：3

78ping(3002)

79先入队：[1, 100, 3001, 3002]

80范围：[2, 3002]

811 过期，出队

82队列：[100, 3001, 3002]

83答案：3

855. 易错点

86过期条件是：

87data[front] < t - 3000

89不是 <=

91因为 [t-3000, t] 是闭区间，

92等于 t-3000 的请求还有效。

94二、844 比较含退格的字符串：栈题

96题目给两个字符串 s 和 t，# 表示退格，要求判断两个字符串经过退格处理后是否相等。

981. 核心概念

100遇到普通字符：入栈

101

102遇到 #：如果栈非空，就弹出栈顶

103

104最后栈里剩下的字符就是处理后的字符串。

105

1062. 为什么用栈？

107

108退格删除的是：前一个字符

109

110也就是最近加入的字符。

111

112这正好符合栈：

113

114后进先出 LIFO

115

1163. 固定模板

117遍历字符串：

118

119如果是普通字符：

120 push

121

122如果是 #：

123 如果栈不空：

124 pop

125

126最后比较两个栈中的内容

1274. C代码

128#include <stdlib.h>

129#include <string.h>

130#include <stdbool.h>

131

132char* build(char* s) {

133 int n = strlen(s);

134 char* stack = malloc((n + 1) * sizeof(char));

135 int top = 0;

136

137 for (int i = 0; i < n; i++) {

138 if (s[i] != '#') {

139 stack[top] = s[i];

140 top++;

141 } else {

142 if (top > 0) {

143 top--;

144 }

145 }

146 }

147

148 stack[top] = '\0';

149

150 return stack;

151}

152

153bool backspaceCompare(char* s, char* t) {

154 char* a = build(s);

155 char* b = build(t);

156

157 bool ans = strcmp(a, b) == 0;

158

159 free(a);

160 free(b);

161

162 return ans;

163}

164

1655. 例子

166s = "ab#c"

167

168处理过程：

169

170a 入栈：[a]

171b 入栈：[a, b]

172# 删除 b：[a]

173c 入栈：[a, c]

174

175最终：

176

177"ac"

178t = "ad#c"

179

180处理过程：

181

182a 入栈：[a]

183d 入栈：[a, d]

184# 删除 d：[a]

185c 入栈：[a, c]

186

187最终：

188"ac"

189

190所以：

191true

192

1936. 易错点

1941. 遇到 # 时，如果栈为空，不能继续 pop。

1952. C字符串最后必须补 '\0'。

1963. top 表示下一个可插入位置，不是栈顶元素下标。

197

198三、两题总结

199

200933 最近请求次数：

201结构：

202 队列

203原因：

204 旧请求先过期，先出队

205操作：

206 队尾入队

207 队头删除过期元素

208

209--------------------------------

210

211844 退格字符串比较：

212结构：

213 栈

214原因：

215 退格删除最近输入的字符

216操作：

217 普通字符入栈

218 # 弹出栈顶

219

220队列解决“先进先出”的时间窗口问题；栈解决“后进先出”的撤销/退格问题。

Rendered Preview

一、933 最近的请求次数：队列题

题目要求每次 ping(t) 返回 [t-3000, t] 范围内的请求次数。因为请求时间 t 是递增的，所以可以用队列维护最近 3000ms 内的请求。

核心概念

每次来了一个新时间 t：

把 t 入队
把小于 t - 3000 的旧请求出队
队列长度就是答案

队列里始终保存：
最近 3000ms 内的请求时间

为什么用队列？

因为时间是递增的。

旧请求一定在队头，新请求一定从队尾进。

所以：

队尾入队新请求
队头删除过期请求

正好是 FIFO 队列。

C代码模板
#include <stdlib.h>

struct RecentCounter {
int data[10010];
int front;
int rear;
};

struct RecentCounter* recentCounterCreate() {
struct RecentCounter* obj = malloc(sizeof(struct RecentCounter));
obj->front = 0;
obj->rear = 0;
return obj;
}

int recentCounterPing(struct RecentCounter* obj, int t) {
//让最新的t入队，然后移动rear
obj->data[obj->rear] = t;
obj->rear++;

while (obj->front < obj->rear && obj->data[obj->front] < t - 3000) {
//当front对应的data小于t-3000时，就出队    
    obj->front++;
}

return obj->rear - obj->front;

}

void recentCounterFree(struct RecentCounter* obj) {
free(obj);
}

例子
ping(1)
队列：[1]
范围：[-2999, 1]
答案：1

ping(100)
队列：[1, 100]
范围：[-2900, 100]
答案：2

ping(3001)
队列：[1, 100, 3001]
范围：[1, 3001]
答案：3

ping(3002)
先入队：[1, 100, 3001, 3002]
范围：[2, 3002]
1 过期，出队
队列：[100, 3001, 3002]
答案：3

易错点
过期条件是：
data[front] < t - 3000

不是 <=

因为 [t-3000, t] 是闭区间，
等于 t-3000 的请求还有效。

二、844 比较含退格的字符串：栈题

题目给两个字符串 s 和 t，# 表示退格，要求判断两个字符串经过退格处理后是否相等。

核心概念

遇到普通字符：入栈

遇到 #：如果栈非空，就弹出栈顶

最后栈里剩下的字符就是处理后的字符串。

为什么用栈？

退格删除的是：前一个字符

也就是最近加入的字符。

这正好符合栈：

后进先出 LIFO

固定模板
遍历字符串：

如果是普通字符：
push

如果是 #：
如果栈不空：
pop

最后比较两个栈中的内容
4. C代码
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* build(char* s) {
int n = strlen(s);
char* stack = malloc((n + 1) * sizeof(char));
int top = 0;

for (int i = 0; i < n; i++) {
    if (s[i] != '#') {
        stack[top] = s[i];
        top++;
    } else {
        if (top > 0) {
            top--;
        }
    }
}

stack[top] = '\0';

return stack;

}

bool backspaceCompare(char* s, char* t) {
char* a = build(s);
char* b = build(t);

bool ans = strcmp(a, b) == 0;

free(a);
free(b);

return ans;

}

例子
s = "ab#c"

处理过程：

a 入栈：[a]
b 入栈：[a, b]

删除 b：[a]

c 入栈：[a, c]

最终：

"ac"
t = "ad#c"

处理过程：

a 入栈：[a]
d 入栈：[a, d]

删除 d：[a]

c 入栈：[a, c]

最终：
"ac"

所以：
true

易错点
遇到 # 时，如果栈为空，不能继续 pop。
C字符串最后必须补 '\0'。
top 表示下一个可插入位置，不是栈顶元素下标。

三、两题总结

933 最近请求次数：
结构：
队列
原因：
旧请求先过期，先出队
操作：
队尾入队
队头删除过期元素

844 退格字符串比较：
结构：
栈
原因：
退格删除最近输入的字符
操作：
普通字符入栈
# 弹出栈顶

队列解决“先进先出”的时间窗口问题；栈解决“后进先出”的撤销/退格问题。