【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【队列】2023C-篮球游戏【欧弟算法】全网注释最详细分类最全的华为OD真题题解

题目描述与示例

题目描述

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

如老师按顺序放入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++

#include <iostream>
#include <deque>
#include <sstream>
#include <string>

using namespace std;

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

    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;
}

时空复杂度

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

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

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多