描述

输入描述：

输入说明： 1 输入歌曲数量 2 输入命令 U或者D

本题含有多组输入数据！

输出描述：

输出说明 1 输出当前列表 2 输出当前选中歌曲

示例

输入：
10
UUUU
输出：
7 8 9 10
7

知识点：数组，模拟

难度：⭐⭐⭐

题解

方法一：模拟

图解：

解题思路：

模拟整个过程处理。情况分为歌曲数小于等于4和大于4两种情况，每种情况都要考虑特殊翻页、一般翻页、其他。用n表示歌曲总数，first表示当前页面的第一首歌，num表示当前选中的歌。

算法流程：

当歌曲数小于等于4时：特殊向上翻页，移动光标到最后一首歌；特殊向上翻页，移动光标到第一首歌；一般向上翻页，光标向上移动一格；一般向下翻页，光标向下移动一格；
当歌曲数大于4时：特殊向上翻页，光标移动到最后一首歌，最后一页第一首歌为n-3；特殊向下翻页，光标移动到第一首歌，第一页第一首歌为1；一般向上翻页，光标向上移一格，当前页第一首歌和光标位置相同；一般向下翻页，光标向下移一格，当前页第一首歌位置也向下移一格；

Java 版本代码如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            String cmd = sc.next();
            parseCmd(cmd, n);
        }
    }

    public static void parseCmd(String str, int n) {
        // 页面数据大小，默认4
        int pageSize = 4;
        // 页面的歌曲大小，最大为4
        if (n < pageSize) {
            pageSize = n;
        }
        // 根据指令移动current光标，可以当作歌曲编号
        int current = 1;
        // 记录光标在页面中的位置pageIndex，即歌曲编号
        int pageIndex = 1;
        for (int i=0; i < str.length(); i++) {
            // 上移
            if (str.charAt(i) == 'U') {
                // 特殊情况，当前光标在歌曲中第一首
                if (current == 1) {
                    // 从第一行上移，移动到最后的歌曲
                    current = n;
                    // 光标在页面的位置，
                    pageIndex = pageSize;
                    // 一般情况，即光标不在第一行
                } else {
                    // 光标上移
                    current--;
                    if (pageIndex != 1) {
                        pageIndex--;
                    }
                }
            } else {
                // 下移
                // 已经到最后一首歌曲，光标到第一首歌曲
                if (current == n) {
                    current = 1;
                    pageIndex = 1;
                } else {
                    // 非最后一行，则光标下移即可
                    current++;
                    if (pageIndex != pageSize) {
                        pageIndex++;
                    }
                }
            }
        }
        // 计算光标前后数字个数
        int next =  pageSize - pageIndex;
        int pre = pageSize - 1 - next;
        // 打印页面
        String page = "";
        // 从当前光标前一个元素开始向前打印
        for (int i = pre; i>0; i--) {
            page += (current-i) + " ";
        }
        page += current + " ";
        for (int i=1; i<=next; i++) {
            page += (current + i) + " ";
        }
        // 去除尾部空格
        page = page.substring(0, page.length()-1);
        System.out.println(page);
        // 打印当前光标
        System.out.println(current);
    }
}

复杂度分析：

时间复杂度： $O (n)$ , 其中n为命令字符串的长度，需要遍历n个命令。

空间复杂度： $O (1)$ , 直接判断，无额外空间。

方法二：滑动窗口

解题思路：

滑动窗口，在本体中长度固定为4，可以看作是一个有限制长度的屏幕，只是这里需要把无法显示的所有内容都放到长度无限的页面上，通过对向上和向下操作进行优化。通过模拟可知，1、2、3、4这四个数中循环，假设当前位置为i，对于 U 操作指令，光标向上移动一格后的位置为 (i-1-1+n) % n+1，这个步骤可以自己在纸上模拟得出规律；光标向后移动一格后的位置为 i%n+1。

对于特殊情况，如果移动后的光标不在窗口内，则需要滑动窗口。如果光标在窗口起始位置前，则把窗口的起始位置和光标对齐；如果光标在窗口后，则把窗口的末位置和光标对齐。

图解：