【牛客华为机试】MP3光标位置算法题解答

2023-01-06 12:29:01

一、题目描述

MP3 Player因为屏幕较小，显示歌曲列表的时候每屏只能显示几首歌曲，用户要通过上下键才能浏览所有的歌曲。为了简化处理，假设每屏只能显示4首歌曲，光标初始的位置为第1首歌。

现在要实现通过上下键控制光标移动来浏览歌曲列表，控制逻辑如下：

1.歌曲总数<=4的时候，不需要翻页，只是挪动光标位置。

光标在第一首歌曲上时，按Up键光标挪到最后一首歌曲；光标在最后一首歌曲时，按Down键光标挪到第一首歌曲。

其他情况下用户按Up键，光标挪到上一首歌曲；用户按Down键，光标挪到下一首歌曲。

2. 歌曲总数大于4的时候（以一共有10首歌为例）：

特殊翻页：屏幕显示的是第一页（即显示第1 – 4首）时，光标在第一首歌曲上，用户按Up键后，屏幕要显示最后一页（即显示第7-10首歌），同时光标放到最后一首歌上。同样的，屏幕显示最后一页时，光标在最后一首歌曲上，用户按Down键，屏幕要显示第一页，光标挪到第一首歌上。

一般翻页：屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。光标当前屏幕的最后一首歌时的Down键处理也类似。

其他情况，不用翻页，只是挪动光标就行。

3.输入输出描述

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

输出说明：（1）输出当前歌曲列表（用编号表示）；（2）输出光标选中的歌曲（用编号表示）

二、题目解答

1.问题分析

只需要注意以下几点：

（1）当歌曲数目小于等于4时，不需要翻页；当歌曲数目大于4时需要翻页。所以我们需要一个常量firstSongIndex记住每一页的第一首歌，还需要另外一个常量currTarget记录当前光标所在位置。

（2）需考虑currTarget=1（光标在第一首歌），命令为U时，若n>4，则翻页和光标均要移动至最底部一页，此时firstSongIndex将变为n-3（n<=4时仍在当前页不需要改变），currTarget变为n（最后一首歌）；

（3）需考虑currTarget=n（光标在最后一首歌），命令为D时，若n>4，则翻页和光标均要移动至第一页，此时firstSongIndex将变为1（n<=4时仍在当前页不需要改变），currTarget也会变为1；

（4）其余情况下currTarget随命令U自减（向上移动减小编号），随命令D自增；但firstSongIndex只有在翻页时才会改变，排除上述（2）（3）情况，只有遇命令U且光标就在当前页第一首歌时，即firstSongIndex==currTarget时自减；

或者遇命令D且光标就在当前页最后一首歌时，即firstSongIndex+3==currTarget时自增；

2.代码

    /**
    * @param n   歌曲数量
    * @param cmd 命令  
    */
    private static void findSongsList(int n, String cmd){
        int l = cmd.length();
        int firstSongIndex = 1;// 每一页的第一首歌为歌单的第几首
        int curTarget = 1;// 指针当前位置，第几首歌
        int i = 0;
        while (i<l) {
            char curr = cmd.charAt(i);
            if (curr=='U'){// 当前命令为向上
                // 如果当前curTarget指向第一首歌
                if(curTarget==1){
                    // 歌曲大于4时第一首歌的位置需要改变为最后一页的第一首n-3
                    if(n>4) firstSongIndex = n-3;
                    // 将curTarget变为指向最后一首
                    curTarget = n;
                } else {
                    // 此时是向上移动光标，又不是第一首，只有当光标和第一首相等时才
                    // 改变当前页第一首的位置
                    if (curTarget==firstSongIndex) firstSongIndex--;
                    //如果当前指针curTarget没有指向最后一首歌，则减一
                    curTarget--;
                }
            } else {// 当前命令为向下
                //如果当前curTarget指向最后一首歌
                if (curTarget==n){
                    // 将firstSongIndex变为指向第一首
                    firstSongIndex=1;
                    // 将curTarget变为指向第一首
                    curTarget=1;
                } else {
                    // 此时为向下移动光标，又不是最后一首，只有光标为当前页的最后一首歌时
                    // 才该表当前页第一首的位置
                    if (curTarget==firstSongIndex+3) firstSongIndex++;
                    //如果当前指针curTarget没有指向最后一首歌，则加一
                    curTarget++;
                }
            }
            i++;
        }
        // 每一页需要展示的歌曲数量
        int disCount = Math.min(4,n);
        // 打印当前页的歌曲
        for (int j = 1; j <=disCount; j++, firstSongIndex++) {
            System.out.print(firstSongIndex);
            System.out.print((j==disCount) ? "\n" : " ");
        }
        // 打印光标
        System.out.println(curTarget);
    }

码农公寓