【队列】2024E-篮球游戏

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P2698

题目描述

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

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

# 题目：【队列】2024E-篮球游戏
# 分值：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;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 初始化一个队列结构
typedef struct {
    int *data;
    int front;
    int rear;
    int size;
} Queue;

// 队列初始化
Queue* createQueue(int size) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * size);
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    return q;
}

// 队列是否为空
int isEmpty(Queue *q) {
    return q->size == 0;
}

// 从右边入队
void enqueue(Queue *q, int value) {
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
}

// 从左边出队
int dequeueLeft(Queue *q) {
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

// 从右边出队
int dequeueRight(Queue *q) {
    int value = q->data[q->rear];
    q->rear--;
    q->size--;
    return value;
}

// 获取队列的队头元素
int peekLeft(Queue *q) {
    return q->data[q->front];
}

// 获取队列的队尾元素
int peekRight(Queue *q) {
    return q->data[q->rear];
}

// 主函数
int main() {
    // 入队顺序
    char push_list_str[1000];
    fgets(push_list_str, 1000, stdin);
    char *token;
    
    // 出队顺序
    char pop_list_str[1000];
    fgets(pop_list_str, 1000, stdin);

    int push_list[1000], pop_list[1000];
    int n = 0, i = 0;

    // 解析入队顺序
    token = strtok(push_list_str, ",");
    while (token != NULL) {
        push_list[n++] = atoi(token);
        token = strtok(NULL, ",");
    }

    // 解析出队顺序
    i = 0;
    token = strtok(pop_list_str, ",");
    while (token != NULL) {
        pop_list[i++] = atoi(token);
        token = strtok(NULL, ",");
    }

    // 初始化队列
    Queue *q = createQueue(n);

    // 初始化答案字符串
    char ans[1000] = "";
    
    // 表示出队序列的索引，初始化为0
    int pop_idx = 0;

    // 从头到尾遍历入队序列的元素push_num
    for (i = 0; i < n; i++) {
        // 将push_num加入队列中，注意只能从队列右端加入
        enqueue(q, push_list[i]);

        // 进行循环
        while (!isEmpty(q)) {
            // 判断队头、队尾元素情况
            // 注意：此处一定要先判断队头
            // 因为当队列中仅剩一个元素时，从左边出队
            // 若【队头元素】等于下一个出队元素
            if (peekLeft(q) == pop_list[pop_idx]) {
                // 该元素从左边出队
                dequeueLeft(q);
                // 出队序列移动到下一个位置
                pop_idx++;
                // 更新答案
                strcat(ans, "L");
            }
            // 若【队尾元素】等于下一个出队元素
            else if (peekRight(q) == pop_list[pop_idx]) {
                // 该元素从右边出队
                dequeueRight(q);
                // 出队序列移动到下一个位置
                pop_idx++;
                // 更新答案
                strcat(ans, "R");
            }
            // 如果队头、队尾元素均不等于下一个出队元素
            // 退出循环
            else {
                break;
            }
        }
    }

    // 退出上述循环后，如果ans长度为n
    // 说明所有小球都可以正常出队、入队，输出ans序列的结果
    // 否则输出"NO"
    if (strlen(ans) == n) {
        printf("%s\n", ans);
    } else {
        printf("NO\n");
    }

    // 释放队列内存
    free(q->data);
    free(q);

    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建接口以读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 获取输入
rl.question('', (pushInput) => {
    rl.question('', (popInput) => {
        // 入队顺序
        const pushList = pushInput.split(',').map(Number);
        // 出队顺序
        const popList = popInput.split(',').map(Number);
        // 序列的个数
        const n = pushList.length;

        // 初始化一个队列
        let q = [];

        // 初始化答案字符串
        let ans = '';

        // 表示出队序列的索引，初始化为0
        let popIdx = 0;

        // 从头到尾遍历入队序列的元素push_num
        for (let pushNum of pushList) {
            // 将pushNum加入队列中，注意只能从队列右端加入
            q.push(pushNum);

            // 进行循环
            while (q.length > 0) {
                // 判断队头、队尾元素情况
                // 注意：此处一定要先判断队头
                // 因为当队列中仅剩一个元素时，从左边出队
                // 若【队头元素】等于下一个出队元素
                if (q[0] === popList[popIdx]) {
                    // 该元素从左边出队
                    q.shift();
                    // 出队序列移动到下一个位置
                    popIdx += 1;
                    // 更新答案
                    ans += 'L';
                } 
                // 若【队尾元素】等于下一个出队元素
                else if (q[q.length - 1] === popList[popIdx]) {
                    // 该元素从右边出队
                    q.pop();
                    // 出队序列移动到下一个位置
                    popIdx += 1;
                    // 更新答案
                    ans += 'R';
                } 
                // 如果队头、队尾元素均不等于下一个出队元素
                // 退出循环
                else {
                    break;
                }
            }
        }

        // 退出上述循环后，如果ans长度为n
        // 说明所有小球都可以正常出队、入队，输出ans序列的结果
        // 否则输出"NO"
        if (ans.length === n) {
            console.log(ans);
        } else {
            console.log('NO');
        }

        // 关闭接口
        rl.close();
    });
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        // 使用缓冲读取输入
        reader := bufio.NewReader(os.Stdin)

        // 读取入队顺序
        pushInput, _ := reader.ReadString('\n')
        pushInput = strings.TrimSpace(pushInput)
        pushList := parseInput(pushInput)

        // 读取出队顺序
        popInput, _ := reader.ReadString('\n')
        popInput = strings.TrimSpace(popInput)
        popList := parseInput(popInput)

        // 序列的个数
        n := len(pushList)

        // 初始化一个队列，使用切片实现
        q := []int{}

        // 初始化答案字符串
        ans := ""

        // 表示出队序列的索引，初始化为0
        popIdx := 0

        // 从头到尾遍历入队序列的元素 pushNum
        for _, pushNum := range pushList {
                // 将 pushNum 加入队列中，注意只能从队列右端加入
                q = append(q, pushNum)

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

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

// 辅助函数：将输入的字符串解析为整数数组
func parseInput(input string) []int {
        strNums := strings.Split(input, ",")
        nums := make([]int, len(strNums))
        for i, str := range strNums {
                num, _ := strconv.Atoi(str)
                nums[i] = num
        }
        return nums
}

时空复杂度

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

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