猿创征文|【算法刷题日记之本手篇】洗牌与MP3光标位置

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【洗牌】和【MP3光标位置】，展示语言java。

小贴士：本专栏所有题目来自牛客->面试刷题必用工具

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年9月3日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬推荐在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：

注册地址：牛客网

有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。

---

⭐️洗牌⭐️

🔐题目详情

洗牌在生活中十分常见，现在需要写一个程序模拟洗牌的过程。 现在需要洗2n张牌，从上到下依次是第1张，第2张，第3张一直到第2n张。首先，我们把这2n张牌分成两堆，左手拿着第1张到第n张（上半堆），右手拿着第n+1张到第2n张（下半堆）。接着就开始洗牌的过程，先放下右手的最后一张牌，再放下左手的最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。接着把牌合并起来就可以了。 例如有6张牌，最开始牌的序列是1,2,3,4,5,6。首先分成两组，左手拿着1,2,3；右手拿着4,5,6。在洗牌过程中按顺序放下了6,3,5,2,4,1。把这六张牌再次合成一组牌之后，我们按照从上往下的顺序看这组牌，就变成了序列1,4,2,5,3,6。 现在给出一个原始牌组，请输出这副牌洗牌k次之后从上往下的序列。

输入描述：

第一行一个数T(T ≤ 100)，表示数据组数。对于每组数据，第一行两个数n,k(1 ≤ n,k ≤ 100)，接下来有2n行个数a1,a2,…,a2n(1 ≤ ai ≤ 1000000000)。表示原始牌组从上到下的序列。

输出描述：

对于每组数据，输出一行，最终的序列。数字之间用空格隔开，不要在行末输出多余的空格。

示例1

输入：

3
3 1
1
2
3
4
5
6
3 2
1
2
3
4
5
6
2 2
1
1
1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出：

1 4 2 5 3 6
1 5 4 3 2 6
1 1 1 1
1
2
3

题目来源：牛客网
题目链接：洗牌

💡解题思路

基本思路： 模拟
解题思路：
本题的题目比较长，本质上按照题意进行模拟就行，首先我们看看看洗牌的规则：
一共有2n张牌，根据题意，前n张牌放到左手，后n张牌放到右手。

洗牌的过程，先放下右手的最后一张牌，再放下左手的最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。

其实也就是从右手的最后一张牌开始，放一张牌，然后放左手的最后一张牌，以此类推往复，直到将两手的牌都放完为止，题目中的牌其实就是数组，我们只需要操作数组模拟洗牌的过程即可。

当然题目要求洗k次牌，我们将洗牌的逻辑封装起来专门写到一个方法中，然后k次调用该方法即可。

🔑源代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] data = new int[2 * n];
            for (int i = 0; i < 2 * n; i++) {
                data[i] = sc.nextInt();
            }
            while (k-- > 0) {
                //洗牌
                data = shuffle(data);
            }
            for (int i = 0; i < data.length; i++) {
                System.out.print(data[i] + " ");
            }
            System.out.println();
        }
    }
    private static int[] shuffle(int[] arr) {
        int[] clone = arr.clone();
        //模拟洗牌
        int m = arr.length / 2;
        int index = clone.length - 1;
        for (int i = m - 1; i >= 0; i--) {
            //第二组牌最后一张
            clone[index--] = arr[i + m];
            //再放第一组牌最后一张
            clone[index--] = arr[i];
        }
        return clone;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

🌱总结

本题为数组模拟题，读懂题，然后按照题目的意思进行洗牌模拟就可以了。

⭐️MP3光标位置⭐️

🔐题目详情

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

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

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

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

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

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

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

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

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

数据范围：命令长度1≤s≤100 ，歌曲数量1≤n≤150

进阶：时间复杂度：O(n)，空间复杂度：O(n)

输入描述：

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

输出描述：

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

示例1

输入：

10
UUUU
1
2

输出：

7 8 9 10
7
1
2

题目来源：牛客网
题目链接：MP3光标位置

💡解题思路

基本思路： 模拟

解题思路：
本题题目很长，并且看起来很复杂，其实仔细读题之后，其实是一道模拟题，就是模拟以前的老人机或者是MP3列表切换的一个逻辑。

其中U命令表示向上切换歌曲，D命令表示向下切换歌曲，题目会给我们歌曲的数量和一系列操作指令，我们需要得到列表上出现的序号已经光标所在的序号。

我们使用rel变量来维护光标所在列表中的相对位置(1-4)，cur变量表示当前光标所在的位置。

向上翻：

情况1：命令为U，cur=1，此时需要将cur=n，如果n>=4，光标所在列表的相对位置为4，否则为n，如n=10。

情况2：相对位置rel=1但cur!=1，命令为U，列表往上翻一格rel仍然为1，光标位置cur--即可。

情况3：相对位置rel>1，命令U，此时cur-- ,rel--。

向下翻：

情况1：cur=n，命令为D，向下翻，cur=1， rel=1。

情况2：rel=4 ，cur!=n，命令为D，向下翻之后，cur++，rel仍然为4。

情况3：rel<4，命令为D，向下翻之后，cur++， rel++。

计算列表起始序号：
根据最终模拟得到的光标位置cur与列表相对位置rel，计算起始序号start=cur-rel+1。

根据起始序号筛选出合法的序号（1-n）输出列表的序号结果集，最后再换行输出当前光标的位置即可。

🔑源代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        sc.nextLine();
        String op = sc.nextLine();
        char[] cs = op.toCharArray();
        int cur = 1;
        int rel = 1;
        for (int i = 0; i < cs.length; i++) {
            if (cur == 1 && cs[i] == 'U') {
                cur = n;
                rel = n >= 4 ? 4 : n;
            } else if (rel == 1 && cs[i] == 'U') {
                cur--;
            } else if (rel > 1 && cs[i] == 'U') {
                rel--;
                cur--;
            } else if (cur == n && cs[i] == 'D') {
                cur = 1;
                rel = 1;
            } else if (rel == 4 && cs[i] == 'D') {
                cur++;
            } else if (rel < 4 && cs[i] == 'D') {
                cur++;
                rel++;
            }
        }
        int start = cur - rel + 1;
        for (int i = 0; i < 4; i++) {
            if (start >= 1 && start <= n) {
                System.out.print(start + " ");
            }
            start++;
        }
        System.out.println();
        System.out.print(cur);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

🌱总结

本题为模拟题，最关键的是读懂题，然后找到一个合适的方式模拟光标位置编号即可。

---

到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！