题解 | #MP3光标位置#

MP3光标位置

http://www.nowcoder.com/practice/eaf5b886bd6645dd9cfb5406f3753e15

题目的主要信息：

MP3每页只能显示4首歌曲，光标初始的位置为第1首歌，通过上下键控制光标移动来浏览歌曲列表。有以下几种情况：

特殊翻页：屏幕显示的是第一页且光标在第一首歌曲上，用户按Up键后，屏幕要显示最后一页，同时光标放到最后一首歌上；
一般翻页：屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。光标当前屏幕的最后一首歌时的Down键处理也类似。
其他情况无需翻页，只需移动光标。

需要注意的是，当歌曲数小于等于4时，无需翻页。

方法一：

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

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

具体做法：

#include <iostream>
#include <string>
using namespace std;

int main(){
    int n;
    string commands;
    while(cin >> n >> commands){
        int num = 1;
        // first：当前屏幕显示页的第一首歌曲的编号
        int first = 1;
        // 歌曲总数不超过4时，不需翻页
        if(n <= 4) {
            for(int i = 0; i < commands.size(); i++){
                // 特殊向上翻页
                if(num == 1 && commands[i] == 'U'){
                    num = n; 
                // 特殊向下翻页
                }else if(num == n && commands[i] == 'D'){
                    num = 1;
                }else if(commands[i] == 'U'){
                    num--;
                }else{
                    num++; 
                }
            }
            for(int i = 1; i <= n - 1; i++){//输出当前页
                cout << i << ' ';
            }
            cout << n << endl << num << endl;
        }else{// 歌曲总数大于4时，需要翻页
            for(int i = 0; i < commands.size(); i++){
                // 特殊向上翻页
                if(num == 1 && commands[i] == 'U') {
                    first = n-3;
                    num = n;
                }else if(num == n && commands[i] == 'D') {// 特殊向下翻页
                    first = 1;
                    num = 1;
                }else if(num == first && commands[i] == 'U')//一般向上翻页
                {
                    first--;
                    num--;
                }else if(num == first + 3 && commands[i] == 'D')//一般向下翻页
                {
                    first++;
                    num++;
                }else if(commands[i] == 'U'){//其他情况，不翻页，只移动光标
                    num--;
                }else{
                    num++;
                }
            }
            for(int i = first; i < first + 3; i++){//输出当前页面
                cout << i << ' ';
            }
            cout << first + 3 << endl << num << endl;
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，其中n为命令字符串的长度，需要遍历n个命令。
空间复杂度： $O (1)$ ，直接判断，无额外空间。

方法二：

滑动窗口。显示的页面就是一个窗口，同时对向上和向下操作进行优化。首先我们知道如果在0、1、2、3这四个数中循环，假设当前位置为i，光标向前移动一格后的位置为(i-1+n)%n；光标向后移动一格后的位置为(i+1)%n。这个理论可以推广到1、2、3、4这四个数中循环，假设当前位置为i，光标向前移动一格后的位置为(i-1-1+n)%n+1；光标向后移动一格后的位置为i%n+1。因此我们可以简化判断，直接用取余计算。

如果移动后的光标不在窗口内，则需要滑动窗口。如果光标在窗口起始位置前，则把窗口的起始位置和光标对齐；如果光标在窗口后，则把窗口的末位置和光标对齐。 alt 具体做法：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int n;
    string commands;
    while(cin >> n >> commands){
        int num = 1;//选中的歌曲
        int win_b = 1;//页面的起始
        int win_e = min(4,n);//页面的末位置
        for(int i = 0; i < commands.size(); i++){
            if(commands[i] == 'U') {//向上移动一格
                num = (num-1-1+n)%n + 1;
            }else if(commands[i] == 'D') {//向下移动一格
                num = num % n + 1;
            }
            if(num < win_b){//如果当前歌曲在窗口前，则将窗口往前移动
                win_b = num;
                win_e = win_b + 3;
            }else if(num > win_e){//如果当前歌曲在窗口后，则将窗口往后移动
                win_e = num;
                win_b = win_e - 3;
            }
        }
        for(int i = win_b; i <= win_e; i++){//输出当前页面
            cout << i << ' ';
        }
        cout << endl;
        cout << num << endl;//输出选中的歌曲
    }
    return 0;
}

复杂度分析：