题目描述:
幼儿园里有一个放倒的圆桶,它是一个线性结构,只能在桶的右边将放入篮球,但是可以在桶的左边或者右边将取出篮球。每个篮球有单独的编号,老师可以一次性放入一个或者多个篮球,小朋友可以在桶左边或者右边取出篮球,当桶里只有一个篮球的情况下,只能从桶的左边取出。
例如,老师按顺序放入 1、2、3、4、5 共 5 个编号的篮球,那么小朋友可以依次取出的编号为“1,2,3,4,5”或者“3,1,2,4,5”顺序编号的篮球,但是无法取出“5,1,3,2,4” 顺序编号的篮球。其中,顺序编号“3,1,2,4,5”的取出场景为:连续放入 1,2,3 号 -> 从右边取出 3 号 ->从左边取出 1 号 -> 从左边取出 2 号 -> 放入 4 号 -> 从左边取出 4 号 -> 放入 5 号 -> 从左边取出 5 号,简单起见,我们以 L 表示左边取出篮球,R 表示右边取出篮球,此时的篮球的依次取出序列为“ RLLLL ”;
输入描述:
第一行的数字作为老师依次放入的篮球编号;
第二行的数字作为要检查是否能够按照放入顺序取出的篮球编号;
其中,篮球编号用逗号进行分隔。
输出描述:
对于每个篮球的取出序列,如果确实可以获取,请打印出其按照左右方向的操作的取出顺序;否则,打印"NO" ;
特别注意事项:
1、1<=篮球的编号,篮球个数<=200;
2、篮球上的数字不重复;
3、输出的结果中 LR 的必须为大写;
示例1:
输入
4,5,6,7,0,1,2
6,4,0,1,2,5,7
输出
RLRRRLL
说明:篮球的取出顺序依次为 “右,左,右,右,右,左,左”
示例2:
输入
4,5,6,7,0,1,2
6,0,5,1,2,4,7
输出:
NO
说明:无法取出对应序列的篮球
示例3:
输入
1,2,3,4
1,2,3,5
输出
NO
说明:不存在编号为 5 的篮球,所以无法取出对应的编号数据
C++源码:
#include <iostream>
#include <sstream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
queue<int> ball, get;
deque<int> list;
string input;
getline(cin, input); // 获取第一行数据,篮球的放入顺序
stringstream ss(input);
string temp;
while (getline(ss, temp, ',')) {
ball.push(stoi(temp));
}
getline(cin, input); // 获取第二行数据,篮球的取出顺序
ss.clear();
ss.str(input);
while (getline(ss, temp, ',')) {
get.push(stoi(temp));
}
int ballNum = 0; // 统计输入的字符串中篮球编号的个数
for (int i = 0; i < input.size(); i++)
{
if (input[i] != ',') {
ballNum++;
}
}
string direction; // 对篮球的取出顺序进行记录
while (!get.empty()) {
if (list.empty() && !ball.empty()) {
list.push_back(ball.front());
ball.pop();
}
if (list.empty()) {
break;
}
int tempL = list.front(), tempR = list.back();
int temp = get.front();
if (temp == tempL) {
get.pop();
list.pop_front();
direction = direction + 'L';
}
else if (temp == tempR) {
get.pop();
list.pop_back();
direction = direction + 'R';
}
else {
if (ball.empty()) {
break;
}
list.push_back(ball.front());
ball.pop();
}
}
// 输出取出顺序
if (ballNum == direction.size()) {
cout << direction << endl;
}
else {
cout << "NO" << endl;
}
system("pause");
return 0;
}