华为机考真题 -- 篮球游戏

题目描述：

幼儿园里有一个放倒的圆桶，它是一个线性结构，只能在桶的右边将放入篮球，但是可以在桶的左边或者右边将取出篮球。每个篮球有单独的编号，老师可以一次性放入一个或者多个篮球，小朋友可以在桶左边或者右边取出篮球，当桶里只有一个篮球的情况下，只能从桶的左边取出。

例如，老师按顺序放入 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;
}