篮球游戏 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

幼儿园里有一个放倒的圆桶，它是一个线性结构，允许在桶的右边将篮球放入，可以在桶的左边和右边将篮球取出。

每个篮球有单独的编号，老师可以连续放入一个或多个篮球，小朋友可以在桶左边或右边将篮球取出，当桶里只有一个篮球的情况下，必须从左边取出。

如老师按顺序放入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<=篮球的编号，篮球个数<=200；
篮球上的数字不重复；
输出的结果中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的篮球，所以无法取出对应的编号数据

题解

这道题目属于模拟题，需要按照老师放入篮球的顺序和小朋友取出篮球的顺序来模拟篮球的放入和取出操作。主要思路是使用双端队列来模拟圆桶，并根据题目要求进行操作。

解题思路：

首先读取输入的老师放入篮球的顺序和小朋友取出篮球的顺序。

使用双端队列模拟圆桶，队列中存放篮球的编号。

循环进行操作，根据情况进行放入或取出操作，并记录操作序列。

如果最后队列为空，说明所有篮球都能够按照要求取出，输出操作序列；否则输出"NO"。

时间复杂度：设篮球个数为n，则时间复杂度为O(n)。

空间复杂度：空间复杂度为O(n)，主要由双端队列和输入篮球编号数组所占用的空间决定。

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int[] source = Arrays.stream(in.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int[] target = Arrays.stream(in.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int n = source.length;

        // 双端队列用例模拟圆桶， first() - 左侧， last() - 右侧
        Deque<Integer> dq = new ArrayDeque<>();
        StringBuilder ans = new StringBuilder();
        int si = 0, ti = 0;
        while (true) {
            if (!dq.isEmpty() && dq.peekFirst() == target[ti]) {   // 可以在桶的左边将篮球取出
                dq.pollFirst();
                ans.append("L");
                ti++;
            } else if (!dq.isEmpty() && dq.peekLast() == target[ti]) {   // 可以在桶的右边将篮球取出
                dq.pollLast();
                ans.append("R");
                ti++;
            } else if (si < n) {   // 在桶的右边将篮球放入
                dq.addLast(source[si++]);
            } else {
                break;
            }
        }

        // 当桶里还有球说明无法取出
        System.out.println(dq.isEmpty() ? ans.toString() : "NO");
    }
}

Python

from collections import deque

def main():
    # 放入篮球编号顺序
    source = list(map(int, input().split(',')))

    # 取出篮球编号顺序
    target = list(map(int, input().split(',')))

    n = len(source)

    # 双端队列用例模拟圆桶
    dq = deque()
    ans = ""
    si, ti = 0, 0

    while True:
        if dq and dq[0] == target[ti]:   # 可以在桶的左边将篮球取出
            dq.popleft()
            ans += "L"
            ti += 1
        elif dq and dq[-1] == target[ti]:   # 可以在桶的右边将篮球取出
            dq.pop()
            ans += "R"
            ti += 1
        elif si < n:   # 在桶的右边将篮球放入
            dq.append(source[si])
            si += 1
        else:
            break

    # 当桶里还有球说明无法取出
    print(ans if not dq else "NO")


if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

// 放入篮球编号顺序
vector<int> source;

// 取出篮球编号顺序
vector<int> target;

// 读入一行数字存入 collect 中,  delimiter 数字之间的分隔符
void read_line(vector<int>& collect, char delimiter = ' ')
{
    string line;
    getline(cin, line);
    istringstream iss(line);
    int           num;
    while (iss >> num) {
        collect.push_back(num);
        if (iss.peek() == delimiter)
            iss.ignore();
        else
            break;
    }
}


int main()
{
    read_line(source, ',');
    read_line(target, ',');
    int n = source.size();

    // 双端队列用例模拟圆桶， front() - 左侧， back() - 右侧
    deque<int> dq;
    string     ans;
    int        si = 0, ti = 0;

    while (true) {
        if (!dq.empty() && dq.front() == target[ti]) {   // 可以在桶的左边将篮球取出
            dq.pop_front();
            ans += "L";
            ti++;
        } else if (!dq.empty() && dq.back() == target[ti]) {   // 可以在桶的右边将篮球取出
            dq.pop_back();
            ans += "R";
            ti++;
        } else if (si < n) {   // 在桶的右边将篮球放入
            dq.push_back(source[si++]);
        } else {
            break;
        }
    }

    // 当桶里还有球说明无法取出
    cout << (dq.empty() ? ans : "NO") << endl;

    return 0;
}