(C卷,200分)- 篮球游戏（Java & JS & Python & C）

题目描述

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

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

如老师按顺序放入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 必须为大写

用例

题目解析

本题可以使用双端队列dque来模拟圆桶。

假设

第一行给定放入顺序是inputs

第二行给定取出顺序是outputs

由于需要按照outputs顺序取出，因此我们定义一个index指向当前outputs要被取出的元素，

初始时index = 0

按照inputs顺序依次放入（篮球编号）到dque（圆桶）右边（addLast操作），每当放入一个后，则需要进行多次取出检查，即一次放入后，可以进行多次取出行为：

假设

圆桶左边篮球编号是left，则 left = dque.getFirst

圆桶右边篮球编号是right，则 right = dque.getLast

当前要取出的篮球编号是outputs[index]

• 优先检查 outputs[index] 编号的篮球是不是left，若是，则取出左边，然后index++，继续循环判断下一个要取出的篮球
• 否则继续检查 outputs[index] 编号的篮球是不是right，若是则取出右边，然后index++，继续循环判断下一个要取出的篮球
• 否则，本轮无法取出篮球，结束本轮取出操作

优先检查 outputs[index] 编号的篮球是不是left 的原因是：题目说当桶只有一个篮球的情况下，必须从左边取出

最后，完成上面逻辑，检查圆桶中是否有剩余篮球

• 若有，则说明无法按照当前放入顺序和取出顺序，取完所有篮球，打印“NO”，
• 若没有，则打印前面的取出顺序

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const inputs = (await readline()).split(",").map(Number);
  const outputs = (await readline()).split(",").map(Number);

  // 利用队列结构模拟圆桶
  const queue = [];
  // outputs[index]是要被取出的篮球的编号
  let index = 0;

  // 记录题解
  const res = [];

  for (let input of inputs) {
    // 按照放入顺序，从圆桶右边放入
    queue.push(input);

    // 然后开始尝试取出
    while (queue.length > 0) {
      // 圆桶左边的篮球的编号
      const left = queue[0];
      // 圆桶右边的篮球的编号
      const right = queue.at(-1);

      if (left == outputs[index]) {
        // 优先比较圆桶左边的篮球是不是当前要取出的篮球，优先左边的原因是：当桶只有一个篮球的情况下，必须从左边取出
        res.push("L");
        queue.shift();
        index++;
      } else if (right == outputs[index]) {
        // 比较圆桶右边的篮球是不是当前要取出的篮球
        res.push("R");
        queue.pop();
        index++;
      } else {
        // 如果圆桶左右两边都不是要取出的球，则本轮取出流程结束
        break;
      }
    }
  }

  // 最终如果圆桶空了，则说明所有球都取出了，否则按照给定要求无法取出所有球
  if (queue.length != 0) {
    console.log("NO");
  } else {
    console.log(res.join(""));
  }
})();

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

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

    int[] inputs = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    int[] outputs = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();

    // 利用队列结构模拟圆桶
    LinkedList<Integer> queue = new LinkedList<>();

    // outputs[index]是要被取出的篮球的编号
    int index = 0;

    // 记录题解
    StringBuilder sb = new StringBuilder();

    for (int input : inputs) {
      // 按照放入顺序，从圆桶右边放入
      queue.addLast(input);

      // 然后开始尝试取出
      while (queue.size() > 0) {
        // 圆桶左边的篮球的编号
        int left = queue.getFirst();
        // 圆桶右边的篮球的编号
        int right = queue.getLast();

        if (left == outputs[index]) {
          // 优先比较圆桶左边的篮球是不是当前要取出的篮球，优先左边的原因是：当桶只有一个篮球的情况下，必须从左边取出
          sb.append("L");
          queue.removeFirst();
          index++;
        } else if (right == outputs[index]) {
          // 比较圆桶右边的篮球是不是当前要取出的篮球
          sb.append("R");
          queue.removeLast();
          index++;
        } else {
          // 如果圆桶左右两边都不是要取出的球，则本轮取出流程结束
          break;
        }
      }
    }

    // 最终如果圆桶空了，则说明所有球都取出了，否则按照给定要求无法取出所有球
    if (queue.size() != 0) {
      System.out.println("NO");
    } else {
      System.out.println(sb);
    }
  }
}

Python算法源码

# 输入获取
ipts = list(map(int, input().split(",")))
opts = list(map(int, input().split(",")))


# 算法入口
def getResult():
    # 利用队列结构模拟圆桶
    queue = []
    # outputs[index]是要被取出的篮球的编号
    index = 0

    # 记录题解
    res = []

    for ipt in ipts:
        # 按照放入顺序，从圆桶右边放入
        queue.append(ipt)

        # 然后开始尝试取出
        while len(queue) > 0:
            # 圆桶左边的篮球的编号
            left = queue[0]
            # 圆桶右边的篮球的编号
            right = queue[-1]

            if left == opts[index]:
                # 优先比较圆桶左边的篮球是不是当前要取出的篮球，优先左边的原因是：当桶只有一个篮球的情况下，必须从左边取出
                res.append("L")
                queue.pop(0)
                index += 1
            elif right == opts[index]:
                # 比较圆桶右边的篮球是不是当前要取出的篮球
                res.append("R")
                queue.pop()
                index += 1
            else:
                # 如果圆桶左右两边都不是要取出的球，则本轮取出流程结束
                break

    # 最终如果圆桶空了，则说明所有球都取出了，否则按照给定要求无法取出所有球
    if len(queue) != 0:
        return "NO"
    else:
        return "".join(map(str, res))


# 算法调用
print(getResult())

C算法源码

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

#define MAX_SIZE 200

typedef struct ListNode {
    int ele;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}

int removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

int removeLast_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->tail;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->tail = link->tail->prev;
        link->tail->next = NULL;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

int main() {
    int inputs[MAX_SIZE];
    int inputs_size = 0;

    while (scanf("%d", &inputs[inputs_size++])) {
        if (getchar() != ',') break;
    }

    int outputs[MAX_SIZE];
    int outputs_size = 0;

    while (scanf("%d", &outputs[outputs_size++])) {
        if (getchar() != ',') break;
    }

    // 利用队列结构模拟圆桶
    LinkedList *queue = new_LinkedList();
    // outputs[index]是要被取出的篮球的编号
    int index = 0;

    // 记录题解
    char res[MAX_SIZE] = {''};
    int res_size = 0;

    for (int i = 0; i < inputs_size; i++) {
        // 按照放入顺序，从圆桶右边放入
        addLast_LinkedList(queue, inputs[i]);

        // 然后开始尝试取出
        while (queue->size > 0) {
            // 圆桶左边的篮球的编号
            int left = queue->head->ele;
            // 圆桶右边的篮球的编号
            int right = queue->tail->ele;

            if (left == outputs[index]) {
                // 优先比较圆桶左边的篮球是不是当前要取出的篮球，优先左边的原因是：当桶只有一个篮球的情况下，必须从左边取出
                res[res_size++] = 'L';
                removeFirst_LinkedList(queue);
                index++;
            } else if (right == outputs[index]) {
                // 比较圆桶右边的篮球是不是当前要取出的篮球
                res[res_size++] = 'R';
                removeLast_LinkedList(queue);
                index++;
            } else {
                // 如果圆桶左右两边都不是要取出的球，则本轮取出流程结束
                break;
            }
        }
    }

    // 最终如果圆桶空了，则说明所有球都取出了，否则按照给定要求无法取出所有球
    if (queue->size != 0) {
        puts("NO");
    } else {
        puts(res);
    }

    return 0;
}