一、编程题
1、1.合法出栈序列
给定一个由不同小写字母构成的长度不超过8的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。
要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。
再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。
时间限制：1000
内存限制：65536
输入
第一行是原始字符串x 后面有若干行，每行一个字符串
输出
对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO"
样例输入
abc
abc
bca
cab
样例输出
YES
YES
NO
参考答案：
略
解析：【喵呜刷题小喵解析】：本题是一道判断字符串是否合法的出栈序列的编程题。首先，我们需要理解题目中的要求。题目中给定了一个原始字符串x，然后有一系列的字符串，我们需要判断这些字符串是否是x的合法出栈序列。所谓的合法出栈序列，是指我们可以按照题目中给出的字符串的字符顺序，将字符依次压入栈中，然后再全部弹出，使得弹出的字符顺序与题目中给出的字符串一致。在解决这个问题时，我们可以使用一个栈来模拟这个过程。我们遍历题目中给出的字符串的每一个字符，然后将该字符与栈顶字符进行比较。如果栈为空或者栈顶字符大于或等于当前字符，我们将当前字符压入栈中；否则，我们将栈顶字符弹出，直到栈为空或者栈顶字符大于或等于当前字符，然后将当前字符压入栈中。最后，如果栈为空，那么题目中给出的字符串就是一个合法出栈序列，否则，就不是。在这个思路的基础上，我们可以写出相应的代码。在代码中，我们首先读取题目中给出的原始字符串x的长度，然后将x读入到内存中。接着，我们读取一系列的字符串，对于每一个字符串，我们都按照上述的思路进行判断，如果是合法出栈序列，就输出"YES"，否则，就输出"NO"。需要注意的是，由于题目中给出的字符串可能有很多个，我们需要使用一个循环来读取所有的字符串，并对每一个字符串进行判断。在判断时，我们需要使用一个栈来模拟压栈和弹栈的过程，如果栈为空或者栈顶字符大于或等于当前字符，就将当前字符压入栈中，否则，就将栈顶字符弹出，直到栈为空或者栈顶字符大于或等于当前字符。最后，如果栈为空，就输出"YES"，否则，就输出"NO"。
2、2.奇怪的括号
某天小A和同学在课堂上讨论到：“栈这种数据结构真是太优美了，既简单用途又广泛。”小B仰慕
小A许久，于是他拿出了自己在网上抄写的一道题问小A，如何判断括号是否匹配呢
时间限制：1000
内存限制：65536
输入
多组数据，每组数据占一行，且都是由(、)、[、]、*、/这六种字符组成。
输出
每组数据输出一行，如果括号能匹配成功，输出True，否则输出False。括号匹配规则是： ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败，例如 /***/ 是匹配失败的因为中间多了一个*。
样例输入
()/*[()]*/
*/**/
样例输出
True
False
参考答案：
略
解析：【喵呜刷题小喵解析】：本题要求判断括号是否匹配，可以使用栈来解决。遍历输入的字符串，对于每个字符，如果是左括号或者特殊字符（*或/），则将其压入栈中；如果是右括号，则判断栈顶元素是否与其匹配，如果不匹配则返回False，否则将栈顶元素弹出。最后判断栈是否为空，如果为空则表示括号匹配成功，否则表示括号匹配失败。在Python中，可以使用列表来模拟栈，使用append()方法将元素压入栈中，使用pop()方法将栈顶元素弹出。对于特殊字符的处理，如果是右括号，则只需要判断栈顶元素是否与其匹配；如果是特殊字符（*或/），则需要判断栈中是否存在与其匹配的字符，如果不存在则返回False。在判断特殊字符时，需要特别注意*和/的匹配规则，即*和/必须成对出现，且中间不能有其他字符。可以使用栈来辅助判断，当遇到/时，判断栈顶元素是否为*，如果不是则返回False，否则将栈顶元素弹出，继续判断下一个字符。本题要求处理多组数据，因此可以使用循环来读入数据，直到读入空行为止。
3、3.区间合并
给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。
时间限制：1000
内存限制：65536
输入
第一行为一个整数n，3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行，在第i行上（1 ≤ i ≤ n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。
输出
输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。
样例输入
5
5 6
1 5
10 10
6 9
8 10
样例输出
1 10
参考答案：
略
解析：【喵呜刷题小喵解析】：本题是一道区间合并的题目，可以使用贪心算法来解决。首先，我们读入区间的数量n和每个区间的左右边界。然后，我们按照区间的左边界进行排序，这样可以保证我们在合并区间时，总是选择左边界最小的区间进行合并。接下来，我们遍历每个区间，如果当前区间和上一个合并的区间有交集，那么我们就将当前区间合并到上一个合并的区间中，更新上一个合并的区间的右边界为两个区间右边界的较大值。否则，我们就将当前区间作为一个新的合并的区间。最后，我们检查合并的区间的数量，如果只有一个区间，说明所有的区间都可以合并为一个区间，我们输出这个区间的左右边界。否则，说明所有的区间不能合并为一个区间，我们输出"no"。时间复杂度为O(nlogn)，其中n为区间的数量，我们需要对区间按照左边界进行排序。空间复杂度为O(n)，我们需要存储每个区间的左右边界和合并的区间。
4、4.双端队列
定义一个双端队列，进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。编程实现这个数据结构。
时间限制：1000
内存限制：65535
输入
第一行输入一个整数t，代表测试数据的组数。 每组数据的第一行输入一个整数n，表示操作的次数。 接着输入n行，每行对应一个操作，首先输入一个整数type。 当type=1，进队操作，接着输入一个整数x，表示进入队列的元素。 当type=2，出队操作，接着输入一个整数c，c=0代表从队头出队，c=1代表从队尾出队。 n <= 1000
输出
对于每组测试数据，输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开，按队头到队尾的顺序输出，占一行。如果队列中已经没有任何的元素，输出NULL。
样例输入
2
5
1 2
1 3
1 4
2 0
2 1
6
1 1
1 2
1 3
2 0
2 1
2 0
样例输出
3
NULL
参考答案：
略
解析：【喵呜刷题小喵解析】本题要求实现一个双端队列，其进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。首先，我们定义一个双端队列类Deque，包含两个方法：push和pop。push方法用于将元素添加到队尾，pop方法用于从队头或队尾弹出元素。在solve函数中，我们首先读取测试数据的组数t，然后对于每组数据，读取操作次数n，并创建一个空的双端队列dq。对于每个操作，我们读取操作类型和元素x。如果操作类型为1，表示进队操作，我们调用dq.push(x)将元素x添加到队尾。如果操作类型为2，表示出队操作，我们调用dq.pop(x)从队头或队尾弹出元素，并将结果打印出来。如果弹出的元素为空，我们打印'NULL'。如果操作类型不是1或2，我们打印'Invalid operation'。最后，如果当前操作是从队尾出队操作，我们打印一个换行符，以区分每组测试数据。这样，我们就实现了双端队列的编程实现，满足题目的要求。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
