题目分析

1. 题目模拟了一个MP3的列表展示的问题
2. 输入U或D来操作是选择上一首还是下一首
3. 需要输出的内容是经过一些上下选择之后，展示屏幕上的信息（最多能显示4条内容）
4. 并且要输出最后正在选中的一条信息
5. 需要注意的是如果在第一首歌的位置向上选择，则直接跳到末尾并且屏幕展示信息随之改变，在最后一首歌的位置向下同理

方法一：维护窗口+分类讨论

• 实现思路
  • 由于题目中其实隐含了mp3中歌曲数量不足4首的情况，因此屏幕展示信息从来没有变过，所以我们对于n<=4的情况要单独拿出来进行分类讨论
  • 知道这一点之后，对于普遍的选择问题来讲我们要处理两种不同的操作
    • 对于U操作，我们一方面根据当前选择的歌曲选项是否达到窗口的边缘来决定更新屏幕信息的情况，特殊处理的情况就是在第一首的位置用了U操作，此时我们窗口整个设置为列表尾部分的窗口
    • 对于D操作，我们一方面根据当前选择的歌曲选项是否达到窗口的边缘来决定更新屏幕信息的情况，特殊处理的情况就是在最后一首的位置如果用了D操作，此时我们窗口整个设置为列表头部分的窗口

def solution(n, op):
    if n <= 4:                                                # 处理页面歌曲数小于4的部分
        cur = 1
        l = 1
        r = n
        for c in op:                                          # 遍历操作字符串
            if c == 'U':                                      # 对于向上操作
                cur -= 1
                if cur == 0:                                  # 跳到末尾
                    cur += n
            elif c == 'D':                                    # 对于向下操作
                cur += 1
                if cur == n+1:                                # 跳到开头
                    cur -= n
        print(" ".join([str(i) for i in range(1, n+1)]))
        print(cur)
    else:
        l = 1
        r = 4
        cur = 1
        for c in op:
            if c == 'U':                # 对于向上操作
                cur -= 1
                if cur == 0:            # 跳到末尾
                    cur += n
                    r = n               # 列表显示的范围更改
                    l = r - 3
                elif cur < l:           # 更新页面
                    l -= 1
                    r -= 1


            elif c == 'D':              # 对于向下
                cur += 1                
                if cur == n+1:          # 跳到开头
                    cur -= n
                    l = 1               # 列表显示范围修改
                    r = l + 3
                elif cur > r:           # 更新页面
                    l += 1
                    r += 1
        print(l,l+1,l+2,l+3)
        print(cur)
    return 

while True:
    try:
        n = int(input())
        op = input()
        solution(n, op)
    except:
        break

复杂度分析

• 时间复杂度：$O(n)O(n)$，有多少步操作就就有相应代价级别的时间开销
• 空间复杂度：$O(1)O(1)$，常数级别的空间开销，没有引入额外的开销

方法二：取余运算+代码合并整理

• 实现思路
  • 对于方法一来说我们固定地在首尾跳转更新屏幕信息的时候直接设置成对应的信息，但是我们也可以根据n的情况选择使用取余的方式来更新屏幕展示的内容
  • 并且我们不维护这个屏幕展示信息的窗口，而是只跟踪屏幕展示内容的第一条当前信息
  • 我们还可以注意到对于n<=4的情况，即使我们在n>4的情况中一直更新screen显示的内容，但是其实对于n<=4的情况screen显示的内容不会随着上下选择的变化而变化，只需要输出绝对的可显示出来的n条歌曲清单即可
  • 因此我们将n>4和n<=4的代码揉在一起是可以的，只是需要注意输出时候的内容做一次分类判断即可

def solution(n, op):
    cur = 0                                # 当前指向的
    screen = 0                             # 屏幕显示的第一条
    for o in op:
        if o == 'U':                       # 对于U操作
            cur = (cur - 1) % n            # 取余方式更新cur指向的
            if cur == n - 1:               # 特殊情况处理screen
                screen = n - 4
            elif cur < screen:             # screen内容跟随cur变化
                screen = cur
        elif o == 'D':                     # 对于D操作
            cur = (cur + 1) % n            # 取余方式更新cur
            if cur == 0:                   # 特殊情况处理screen
                screen = 0
            elif cur > screen + 3:         # screen内容跟随cur变化
                    screen = cur - 3
    res = list(range(screen+1, screen+5)) if n > 4 else list(range(1, n+1))
    print(*res)
    print(cur + 1)

while True:
    try:
        n = int(input())
        op = input()
        solution(n, op)
    except:
        break

复杂度分析

• 时间复杂度：$O(n)O(n)$，有多少步操作就就有相应代价级别的时间开销
• 空间复杂度：$O(1)O(1)$，常数级别的空间开销，没有引入额外的开销