下载掌阅APP，畅读海量书库
立即打开
【问题描述】 学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。所有学生站在一个队列中，每个学生要么喜欢圆形的三明治要么喜欢方形的三明治。餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈中，每一轮：
（1）如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
（2）否则这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列中的所有学生都不喜欢栈顶的三明治为止。
给定两个整数数组students和sandwiches，其中sandwiches[ i ]是栈中第 i 个三明治的类型（ i =0是栈的顶部），students[ j ]是初始队列中第 j 名学生对三明治的喜好（ j =0是队列的最开始位置）。请返回无法吃午餐的学生的数量。
例如，students=[1，1，1，0，0，1]，sandwiches=[1，0，0，0，1，1]，答案为3，即有3个学生无法吃午餐。
【限制】 1≤students.length，sandwiches.length≤100，students.length=sandwiches.length，sandwiches[ i ]和students[ i ]要么是0要么是1。
【解题思路】 用队列模拟学生选择三明治的循环过程 。先将students依次存入一个队列qu中，用 i 从0开始遍历sandwiches，然后开始一轮一轮操作，每一轮对应一个学生找到喜欢的三明治，其中用cnt累计比较的次数。当队头的学生stud（从队头出队）喜欢当前的三明治sandwiches[ i ]时，执行 i ++，表示移到下一个三明治，同时cnt清零，表示进入下一轮，否则将stud插入队尾，同时cnt增1。队列qu中剩余的学生都尚未吃午餐，若cnt等于qu中元素的个数，说明剩余学生中每个学生都比较过一次，此时结束，返回cnt或者qu.size（）即可。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 设计一个RecentCounter类来计算特定时间范围内最近的请求。
（1）RecentCounter（）：初始化计数器，请求数为0。
（2）int ping（int t）：在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求），确切地说，返回在[ t -3000， t ]范围内发生的请求数。
保证每次对ping的调用都使用比之前更大的 t 值。
示例：
【限制】 1≤ t ≤10 9 ，保证每次对ping的调用所使用的 t 值都严格递增，最多调用ping方法10 4 次。
【解题思路】 用队列模拟请求操作 。由于多次调用ping（t）时的 t 总是递增的，用一个队列qu存放请求的时间（每个时间对应一次请求）。执行ping（t）的操作是先将 t 进队，将所有小于 t -3000的请求出队，返回队列qu中元素的个数，即[ t -3000， t ]范围内的请求数。
对应的RecentCounter类如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 请使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的4种操作（push、top、pop和empty），实现MyStack类。
（1）void push（int x）：将元素 x 压入栈顶。
（2）int pop（）：移除并返回栈顶元素。
（3）int top（）：返回栈顶元素。
（4）bool empty（）：如果栈为空，返回true，否则返回false。
注意：只能使用队列的基本操作实现这些操作。
示例：
【限制】 1≤ x ≤9，最多调用100次push、pop、top和empty，每次调用pop和top都保证栈不为空。
【解题思路】 用两个 queue 模拟一个栈 。设置两个队列，qu为主队列，模拟栈操作，将队头作为栈顶，如图4.8所示；tmpqu为辅助队列。
图4.8 主队列qu
（1）push（int x）：假设队列qu中从队头到队尾为[ a 0 ， a 1 ，…， a n -1 ]，执行该运算后qu变为[ x ， a 0 ， a 1 ，…， a n -1 ]。为此先将qu中的所有元素出队并进入tmpqu中，这样qu=[]，tmpqu=[ a 0 ， a 1 ，…， a n -1 ]，将 x 进qu队，qu=[ x ]，再将tmpqu中的所有元素出队并进入qu中，这样qu=[ x ， a 0 ， a 1 ，…， a n -1 ]，tmpqu=[]。
（2）pop（）：若qu=[ x ， a 0 ， a 1 ，…， a n -1 ]，该运算返回 x ，并且qu变为[ a 0 ， a 1 ，…， a n -1 ]，从队列qu的角度看就是出队队头元素 x 。
（3）top（）：若qu=[ x ， a 0 ， a 1 ，…， a n -1 ]，该运算返回 x ，并且qu不变，从队列qu的角度看就是取队头元素 x 。
（4）empty（）：栈中的所有元素均存放在qu中，所以返回qu是否为空。
在上述4个算法中只有push（x）算法的时间复杂度为 O （ n ），其他算法的时间复杂度均为 O （1）。对应的MyStack类如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定两个一维的向量，请实现一个迭代器类ZigzagIterator，用于交替返回它们中间的元素。
例如，v1=[1，2]，v2=[3，4，5，6]，答案是[1，3，2，4，5，6]，需要通过连续调用next（）函数直到hasNext（）函数返回false，next（）函数的返回值应该为[1，3，2，4，5，6]。
【解题思路】 用队列作为数据容器 + 二路归并 。next（）函数不带参数，可以连续调用，对于题目中的示例，第一次调用next（）返回1，第2次调用next（）返回3，第3次调用next（）返回2，以此类推。为此设计一个队列qu存放两个向量交替的元素序列，执行一次next（）相当于从队列中出队一次。对应的ZigzagIterator类如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定由小写字母组成的字符串s，在s上反复执行重复项删除操作（重复项删除操作指选择两个相邻且相同的字母，并删除它们），直到无法继续删除，在完成所有重复项删除操作后返回最终的字符串。答案要保证唯一。
例如，＂abbaca＂，可以删除＂bb＂（由于两个字母相邻且相同，这是此时唯一可以执行删除操作的重复项），得到字符串＂aaca＂，其中又有＂aa＂可以执行重复项删除操作，所以最后的字符串为＂ca＂，答案为＂ca＂。
【限制】 1≤s.length≤2×10 4 ，s仅由小写英文字母组成。
【解题思路】 用双端队列后端判定相邻字符是否重复 。设置一个双端队列dq，用 i 从0开始遍历s。
（1）若dq不为空且队尾元素等于s[ i ]，说明当前判定s[ i ]是重复字符，则从后端（队尾）出队元素。
（2）若dq为空或者dq不为空且队尾元素不等于s[ i ]，说明当前判定s[ i ]是非重复字符，则将s[ i ]从后端进队。
遍历完毕dq中都是非相邻重复字符，则从队头到队尾将所有字符连接起来得到答案ans，返回ans即可。
例如，s=＂abbaca＂，dq=[]。
（1）s[0]='a'，dq为空，将s[0]从后端进队，dq=['a']。
（2）s[1]='b'，dq队尾≠'b'，将s[1]从后端进队，dq=['a'，'b']（按从前端到后端的顺序排列）。
（3）s[2]='b'，dq队尾='b'，从后端出队，dq=['a']。
（4）s[3]='a'，dq队尾='a'，从后端出队，dq=[]。
（5）s[4]='c'，dq为空，将s[4]从后端进队，dq=['c']。
（6）s[5]='a'，dq队尾≠'a'，将s[5]从后端进队，dq=['c'，'a']。
求出ans=＂ca＂。