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

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

输出描述

对于每个篮球的取出序列，如果确实可以获取，请打印出其按照左右方向的操作取出顺序，如果无法获取则打印“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”，
• 若没有，则打印前面的取出顺序

import Foundation

func ODTest_2_2() {
    print("第一行的数字作为老师依次放入的篮球编号")
    var teachers = (readLine() ?? "").split(separator: ",").map { Int($0) ?? 0 }
    print("第二行的数字作为要检查是否能够按照放入的顺序取出给定的篮球的编号，其中篮球的编号用逗号进行分隔。")
    var students = (readLine() ?? "").split(separator: ",").map { Int($0) ?? 0 }

    var queue: [Int] = []
    // 记录题解
    var res: [String] = []
    var i = 0
    queue.append(teachers[i])
    while !queue.isEmpty {
        let student = students[0]
        if queue.first == student {
            res.append("L")
            students.removeFirst()
            queue.removeFirst()
        } else if queue.last == student {
            res.append("R")
            students.removeFirst()
            queue.removeLast()
        } else {
            i += 1
            if i >= teachers.count {
                break
            }
            queue.append(teachers[i])
        }
    }
    if res.count != teachers.count {
        print("NO")
        return
    }
    print(res.joined())
}