题目描述与示例
题目描述
幼儿园里有一个放倒的圆桶，它是一个线性结构，允许在桶的右边将篮球放入，可以在桶的左边和右边将篮球取出。每个篮球有单独的编号，老师可以连续放入一个或多个篮球，小朋友可以在桶左边或右边将篮球取出，当桶里只有一个篮球的情况下，必须从左边取出。
如老师按顺序放入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"
输入描述
每次输入包含一个测试用例:
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++）⽬录汇总（每⽇更新）
