OD机试 2024 考试题【幼儿园篮球游戏】

■ 题目描述

【幼儿园篮球游戏】

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

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

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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String push = in.nextLine();
            String pop = in.nextLine();
            LinkedList link = new LinkedList();
            String[] pushList = push.split(",");
            String[] popList = pop.split(",");
            String[] re = new String[pushList.length];
            int match = 0;
            ArrayList list = new ArrayList();
            ArrayList listre = new ArrayList();
            for (String s : pushList) {
                if (link.size() == 0) {
                    link.addFirst(s);
                } else {
                    link.addFirst(s);
                    link.addLast(s);
                }
            }
            try {

                for (String p : popList) {
                    int x = link.indexOf(p);
                    for (int i = 0; i < x; i++) {
                        link.removeFirst();
                    }
                    if (x >= 0) {
                        list.add(p);
                        if (link.indexOf(pushList[0]) > 0) {
                            listre.add("R");
                        } else {
                            listre.add("L");
                        }
                        link.removeFirst();
                    } else {
                        match = 1;
                    }
                }
            } catch (Exception e) {

            }
            if (match == 0) {
                for (int i = 0; i < list.size(); i++) {
                    if (!list.get(i).equals(popList[list.indexOf(list.get(i))])) {
                        match = 1;
                    }
                };
            }

            if (match == 0) {
                listre.forEach(it-> {
                    System.out.print(it);
                });

            } else {
                System.out.println("NO");
            }

        }
    }
}

■ 解析

老师只能从右边放入篮球，学生拿球可左可右；利用逆向思维，老师可左放，也可右放，学生只能从左边取出；

1.用链表linkedList模拟老师放入篮球序列，得到[5, 4, 3, 2, 1, 2, 3, 4, 5]，只要取出顺序包含在该序列内，即能满足该取出顺序；

2.依次遍历取出顺序，每从左边取出一个编号的球，就把它之前的序号球移出；比如第一个取的球是【3】，则去除【5】【4】，

链表变为[3, 2, 1, 2, 3, 4, 5],依次遍历，在此过程，如果出现拿不到取出编号球下标，则说明该序列不满足篮球取出顺序；

3.用最开始放入的【1】号球作为坐标，如果【1】号球存在链表中，则说明是从右边取出，否则未从左边取出；

#机考##华为#