华为OD机试真题---幼儿园篮球游戏

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

备注：1≤篮球编号，篮球个数≤200，篮球上的数字不重复。

输出描述

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

示例

• 示例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的篮球，所以无法取出对应编号的数据。

解题思路

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

1. 读取输入的老师放入篮球的顺序和小朋友取出篮球的顺序。
2. 使用双端队列模拟圆桶，队列中存放篮球的编号。
3. 循环进行操作，根据情况进行放入或取出操作，并记录操作序列。
4. 如果最后队列为空，说明所有篮球都能够按照要求取出，输出操作序列；否则输出“NO”。

复杂度分析

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

通过上述分析，可以清晰地理解题目要求及解题思路，并有效地解答该题目。

代码实现

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class BasketballGame {

    
    
    /**
     * 判断是否能够按照指定的顺序取出篮球
     *
     * @param inputPut       表示放入篮球的顺序的字符串
     * @param inputRetrieve  表示尝试取出篮球的顺序的字符串
     * @return               如果能够按照指定顺序取出所有篮球，则返回操作序列，否则返回"NO"
     */
    public static String canRetrieveBalls(String inputPut, String inputRetrieve) {
        // 验证输入字符串
        if (inputPut == null || inputRetrieve == null || inputPut.isEmpty() || inputRetrieve.isEmpty()) {
            return "NO";
        }

        // 将输入的字符串转换为整数列表
        List<Integer> putList = convertToIntegerList(inputPut);
        List<Integer> retrieveList = convertToIntegerList(inputRetrieve);

        // 使用双端队列模拟圆桶
        Deque<Integer> deque = new LinkedList<>();

        // 记录操作序列
        StringBuilder operationSequence = new StringBuilder();

        // 遍历要取出的篮球列表
        for (int retrieve : retrieveList) {
            // 尝试取出篮球，如果失败则返回"NO"
            if (!tryRetrieve(deque, retrieve, operationSequence)) {
                return "NO";
            }

            // 如果还有篮球要放入且队列不为空（不是最后一个篮球），则继续放入
            if (!putList.isEmpty() && (deque.isEmpty() || !deque.peekLast().equals(putList.get(putList.size() - 1)))) {
                deque.offerLast(putList.remove(putList.size() - 1));
            }
        }

        // 检查是否所有篮球都已正确取出且没有剩余未放入的篮球
        if (deque.isEmpty() && putList.isEmpty()) {
            return operationSequence.toString();
        } else {
            return "NO";
        }
    }

    
    
    
    
    /**
     * 将逗号分隔的字符串转换为整数列表
     * 此方法选择逗号作为分隔符，因为它假设输入字符串中的数字以逗号分隔
     * 该方法不处理输入字符串中的空格或其他潜在的格式问题
     *
     * @param input 一个包含由逗号分隔的数字的字符串
     * @return 一个包含解析后的整数的列表
     * @throws NumberFormatException 如果字符串中的数字无法解析为整数，则抛出此异常
     */
    private static List<Integer> convertToIntegerList(String input) {
        // 分割输入字符串为数组
        String[] array = input.split(",");
        // 初始化整数列表
        List<Integer> list = new ArrayList<>();
        // 遍历数组，将每个字符串转换为整数并添加到列表中
        for (String s : array) {
            list.add(Integer.parseInt(s));
        }
        // 返回转换后的整数列表
        return list;
    }

    
    
    
    
    /**
     * 尝试从双端队列中取出特定的元素，并记录操作序列
     *
     * @param deque 双端队列，包含要取出的元素
     * @param retrieve 要取出的目标元素
     * @param operationSequence 记录操作序列的字符串构建器
     * @return 如果成功取出目标元素，则返回true；否则返回false
     */
    private static boolean tryRetrieve(Deque<Integer> deque, int retrieve, StringBuilder operationSequence) {
        boolean retrieved = false;

        // 尝试从右边取出
        if (!deque.isEmpty() && deque.peekLast() == retrieve) {
            deque.pollLast();
            operationSequence.append('R');
            retrieved = true;
        }

        // 尝试从左边取出（但注意当桶里只有一个篮球时必须从左边取出）
        if (!retrieved && (!deque.isEmpty() && deque.peekFirst() == retrieve || deque.size() == 1)) {
            deque.pollFirst();
            operationSequence.append('L');
            retrieved = true;
        }

        return retrieved;
    }

    public static void main(String[] args) {
        // 示例测试
        String inputPut1 = "4,5,6,7,0,1,2";
        String inputRetrieve1 = "6,4,0,1,2,5,7";
        System.out.println(canRetrieveBalls(inputPut1, inputRetrieve1)); // 输出: NO 或相应的正确序列，但注意此实现可能因策略不同而略有差异

        String inputPut2 = "4,5,6,7,0,1,2";
        String inputRetrieve2 = "6,0,5,1,2,4,7";
        System.out.println(canRetrieveBalls(inputPut2, inputRetrieve2)); // 输出: NO

        String inputPut3 = "1,2,3,4";
        String inputRetrieve3 = "1,2,3,5";
        System.out.println(canRetrieveBalls(inputPut3, inputRetrieve3)); // 输出: NO
    }
}

以上实现有问题，望大佬们指正。