题目描述与示例

题目描述

幼儿园里有一个放倒的圆桶,它是一个线性结构,允许在桶的右边将篮球放入,可以在桶的左边和右边将篮球取出。每个篮球有单独的编号,老师可以连续放入一个或多个篮球,小朋友可以在桶左边或右边将篮球取出,当桶里只有一个篮球的情况下,必须从左边取出。

如老师按顺序放入1、2、3、4、55个编号的篮球,那么小朋友可以依次取出的编号为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"

输入描述

每次输入包含一个测试用例:

1、第一行的数字作为老师依次放入的篮球编号

2、第二行的数字作为要检查是否能够按照放入顺序取出的篮球编号

其中篮球编号用逗号进行分隔。

输出描述

对于每个篮球的取出序列,如果确实可以获取,请打印出其按照左右方向的操作的取出顺序,如果无法获取则打印"NO"

备注

1、1 <= 篮球的编号,篮球个数 <= 200;

2、篮球上的数字不重复

3、输出的结果中LR的必须为大写:

示例

输入

4,5,6,7,0,1,2
6,4,0,1,2,5,7

输出

RLRRRLL

解题思路

篮球只能从右边放入,但可以同时从左边和右边拿出,这显然是一个具有限制条件的双向队列

输入的第一行为入队顺序,输入的第二行为出队顺序。

题目本质上是要求模拟整个入队、出队过程,有点类似于队列版的LeetCode 946、验证栈序列

代码

Python

# 题目:【队列】2023C-篮球游戏
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:队列
# 代码看不懂的地方,请直接在群上提问


from collections import deque

# 入队顺序
push_list = list(map(int, input().split(",")))
# 出队顺序
pop_list = list(map(int, input().split(",")))
# 序列的个数
n = len(push_list)

# 初始化一个队列
q = deque()

# 初始化答案字符串
ans = str()

# 表示出队序列的索引,初始化为0
pop_idx = 0

# 从头到尾遍历入队序列的元素push_num
for push_num in push_list:
    # 将push_num加入队列中,注意只能从队列右端加入
    q.append(push_num)

    # 进行循环
    while len(q) > 0:
        # 判断队头、队尾元素情况
        # 注意:此处一定要先判断队头
        # 因为当队列中仅剩一个元素时,从左边出队
        # 若【队头元素】等于下一个出队元素
        if q[0] == pop_list[pop_idx]:
            # 该元素从左边出队
            q.popleft()
            # 出队序列移动到下一个位置
            pop_idx += 1
            # 更新答案
            ans += "L"
        # 若【队尾元素】等于下一个出队元素
        elif q[-1] == pop_list[pop_idx]:
            # 该元素从右边出队
            q.pop()
            # 出队序列移动到下一个位置
            pop_idx += 1
            # 更新答案
            ans += "R"
        # 如果队头、队尾元素均不等于下一个出队元素
        # 退出循环
        else:
            break

# 退出上述循环后,如果ans长度为n
# 说明所有小球都可以正常出队、入队,输出ans序列的结果
# 否则输出"NO"
print(ans) if len(ans) == n else print("NO")

Java

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] pushInput = scanner.nextLine().split(",");
        String[] popInput = scanner.nextLine().split(",");
        scanner.close();

        int[] pushList = new int[pushInput.length];
        int[] popList = new int[popInput.length];

        for (int i = 0; i < pushInput.length; i++) {
            pushList[i] = Integer.parseInt(pushInput[i]);
        }

        for (int i = 0; i < popInput.length; i++) {
            popList[i] = Integer.parseInt(popInput[i]);
        }

        ArrayDeque<Integer> q = new ArrayDeque<>();
        StringBuilder ans = new StringBuilder();
        int popIdx = 0;

        for (int pushNum : pushList) {
            q.add(pushNum);

            while (!q.isEmpty()) {
                if (q.peek().equals(popList[popIdx])) {
                    q.poll();
                    popIdx++;
                    ans.append("L");
                } else if (!q.isEmpty() && q.peekLast().equals(popList[popIdx])) {
                    q.pollLast();
                    popIdx++;
                    ans.append("R");
                } else {
                    break;
                }
            }
        }

        if (ans.length() == pushList.length) {
            System.out.println(ans);
        } else {
            System.out.println("NO");
        }
    }
}

C++

“`C++
#include <iostream>
#include <deque>
#include <sstream>
#include <string>

using namespace std;

int main() {
string pushInput, popInput;
getline(cin, pushInput);
getline(cin, popInput);

<pre><code>stringstream pushStream(pushInput);
stringstream popStream(popInput);

deque<int> pushList;
deque<int> popList;

string token;
while (getline(pushStream, token, ',')) {
pushList.push_back(stoi(token));
}

while (getline(popStream, token, ',')) {
popList.push_back(stoi(token));
}

deque<int> q;
string ans;
int popIdx = 0;

for (int pushNum : pushList) {
q.push_back(pushNum);

while (!q.empty()) {
if (q.front() == popList[popIdx]) {
q.pop_front();
popIdx++;
ans += "L";
} else if (!q.empty() && q.back() == popList[popIdx]) {
q.pop_back();
popIdx++;
ans += "R";
} else {
break;
}
}
}

if (ans.length() == pushList.size()) {
cout << ans << endl;
} else {
cout << "NO" << endl;
}

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度:O(N)。一次遍历入队序列,每个元素仅会入队或出队一次。

空间复杂度:O(N)。队列所占空间。

说明

华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。

机试分数越⾼评级越⾼,⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知

关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)