返回目录

题目描述

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

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

如老师按顺序放入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. 第二行的数字作为要检查是否能够按照放入的顺序取出给定的篮球的编号，其中篮球的编号用逗号进行分隔。

其中篮球编号用逗号进行分隔。

备注

• 1 ≤ 篮球编号，篮球个数 ≤ 200
• 篮球上的数字不重复
• 输出的结果中 LR 必须为大写

输出描述

对于每个篮球的取出序列，如果确实可以获取，请打印出其按照左右方向的操作取出顺序，如果无法获取则打印“NO”。

示例：

解题思路

1. 使用队列来模拟篮球的放入和取出过程。
2. 遍历放入顺序，将每个篮球编号放入队列的末尾。
3. 每放入一个篮球后，检查队列的两端是否有与取出顺序当前编号相同的篮球。
   如果队列首部的篮球可以取出，则记录操作并从首部取出，继续下一次检查。
   如果队列尾部的篮球可以取出，则记录操作并从尾部取出，继续下一次检查。
   如果两端都不可取出，则继续放入下一个篮球。
4. 如果所有篮球都能按取出顺序被取出，则输出记录的操作序列。如果无法按取出顺序取出所有篮球，则输出"NO"。

Python算法源码

# 将字符串按照分隔符切分，返回整数列表
def split_string_to_int(string, delim):
    tokens = string.split(delim)
    return list(map(int, tokens))

if __name__ == "__main__":
    # 读取第一行输入，分割字符串得到放入篮球的编号列表
    input_line_1 = input()
    input_numbers = split_string_to_int(input_line_1, ',')

    # 读取第二行输入，分割字符串得到要检查的取出篮球的顺序列表
    input_line_2 = input()
    output_sequence = split_string_to_int(input_line_2, ',')

    # 创建双端队列用于模拟篮球的放入和取出
    deque = []

    # 用于构建输出的取球顺序
    result = ""
    # 初始化输出序列的索引
    output_index = 0

    # 遍历放入篮球的编号
    for number in input_numbers:
        # 将篮球编号放入双端队列的末尾（右边放入）
        deque.append(number)

        # 当双端队列不为空且输出序列索引小于输出序列长度时
        while deque and output_index < len(output_sequence):
            # 获取输出序列中当前要取出的篮球编号
            output_number = output_sequence[output_index]

            # 如果双端队列的首部（左边）的篮球编号与当前要取出的编号相同
            if deque[0] == output_number:
                # 从双端队列首部取出篮球
                deque.pop(0)
                # 添加取球操作"L"
                result += 'L'
                # 输出序列索引递增
                output_index += 1
            elif deque[-1] == output_number:
                # 如果双端队列的尾部（右边）的篮球编号与当前要取出的编号相同
                # 从双端队列尾部取出篮球
                deque.pop()
                # 添加取球操作"R"
                result += 'R'
                # 输出序列索引递增
                output_index += 1
            else:
                # 如果两边的篮球编号都不匹配，则停止当前循环
                break

    # 如果输出序列索引没有达到输出序列的长度，说明无法按照要求取出所有篮球
    if output_index != len(output_sequence):
        print("NO")
    else:
        # 如果可以取出所有篮球，打印取球操作序列
        print(result)

C算法源码

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

// 将字符串按照分隔符切分，返回整数数组
int* split_string_to_int(const char* str, char delim, int* size) {
    int capacity = 10;
    int* tokens = (int*)malloc(capacity * sizeof(int));
    char* token = strtok((char*)str, &delim);
    *size = 0;

    while (token != NULL) {
        tokens[*size] = atoi(token);
        (*size)++;
      
        if (*size >= capacity) {
            capacity *= 2;
            tokens = (int*)realloc(tokens, capacity * sizeof(int));
        }

        token = strtok(NULL, &delim);
    }

    return tokens;
}

int main() {
    char inputLine[100];
    int* inputNumbers;
    int* outputSequence;
    int inputSize, outputSize;

    // 读取第一行输入，分割字符串得到放入篮球的编号数组
    fgets(inputLine, sizeof(inputLine), stdin);
    inputNumbers = split_string_to_int(inputLine, ',', &inputSize);

    // 读取第二行输入，分割字符串得到要检查的取出篮球的顺序数组
    fgets(inputLine, sizeof(inputLine), stdin);
    outputSequence = split_string_to_int(inputLine, ',', &outputSize);

    // 创建双端队列用于模拟篮球的放入和取出
    int* deque = (int*)malloc(inputSize * sizeof(int));
    int dequeSize = 0;

    // 用于构建输出的取球顺序
    char result[100];
    int resultIndex = 0;
    // 初始化输出序列的索引
    int outputIndex = 0;

    // 遍历放入篮球的编号
    for (int i = 0; i < inputSize; i++) {
        // 将篮球编号放入双端队列的末尾（右边放入）
        deque[dequeSize++] = inputNumbers[i];

        // 当双端队列不为空且输出序列索引小于输出序列长度时
        while (dequeSize > 0 && outputIndex < outputSize) {
            // 获取输出序列中当前要取出的篮球编号
            int outputNumber = outputSequence[outputIndex];

            // 如果双端队列的首部（左边）的篮球编号与当前要取出的编号相同
            if (deque[0] == outputNumber) {
                // 从双端队列首部取出篮球
                for (int j = 0; j < dequeSize - 1; j++) {
                    deque[j] = deque[j + 1];
                }
                dequeSize--;
                // 添加取球操作"L"
                result[resultIndex++] = 'L';
                // 输出序列索引递增
                outputIndex++;
            } else if (deque[dequeSize - 1] == outputNumber) {
                // 如果双端队列的尾部（右边）的篮球编号与当前要取出的编号相同
                // 从双端队列尾部取出篮球
                dequeSize--;
                // 添加取球操作"R"
                result[resultIndex++] = 'R';
                // 输出序列索引递增
                outputIndex++;
            } else {
                // 如果两边的篮球编号都不匹配，则停止当前循环
                break;
            }
        }
    }
    result[resultIndex] = '\0'; // Null-terminate the string

    // 如果输出序列索引没有达到输出序列的长度，说明无法按照要求取出所有篮球
    if (outputIndex != outputSize) {
        printf("NO\n");
    } else {
        // 如果可以取出所有篮球，打印取球操作序列
        printf("%s\n", result);
    }

    free(inputNumbers);
    free(outputSequence);
    free(deque);

    return 0;
}

java算法源码

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


class SomeClass {
    private int x;
    private int y;

    public SomeClass(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int sum() {
        return x + y;
    }
}

public class Main {
    //参数类型和个数
    /**
     * 根据输入的字符串构建整数数组
     *
     * @param str 输入的字符串
     * @return 构建的整数数组
     */
    public static int[] buildIntArray(String str) {
        String[] parts = str.split(",");
        int[] arr = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            arr[i] = Integer.parseInt(parts[i]);
        }
        return arr;
    }

    // 函数语句的参数名和变量
    /**
     * 根据输入的篮球编号和取球顺序判断是否可以按照要求取出所有篮球
     *
     * @param inputNumbers   输入的篮球编号数组
     * @param outputSequence 要检查的取出篮球的顺序数组
     * @return 是否可以按照要求取出所有篮球
     */
    public static boolean canRetrieveBalls(int[] inputNumbers, int[] outputSequence) {
        Deque<Integer> deque = new ArrayDeque<>();
        int outputIndex = 0;

        for (int number : inputNumbers) {
            deque.offerLast(number);

            while (!deque.isEmpty() && outputIndex < outputSequence.length) {
                int outputNumber = outputSequence[outputIndex];
                if (deque.peekFirst() == outputNumber) {
                    deque.pollFirst();
                    outputIndex++;
                } else if (deque.peekLast() == outputNumber) {
                    deque.pollLast();
                    outputIndex++;
                } else {
                    break;
                }
            }
        }

        return outputIndex == outputSequence.length;
    }

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

        // 更改输入方法
        String input1 = sc.nextLine();
        String input2 = sc.nextLine();

        // 调用函数
        int[] inputNumbers = buildIntArray(input1);
        int[] outputSequence = buildIntArray(input2);

        //函数调用
        boolean canRetrieve = canRetrieveBalls(inputNumbers, outputSequence);

        if (!canRetrieve) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }

        // 类的使用
        SomeClass obj = new SomeClass(3, 5);
        System.out.println("Sum of x and y: " + obj.sum());
    }
}