蓝桥杯-左移右移(2022国赛)

1、问题描述

  小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。

  之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:

1. 左移 x, 即把 x 移动到最左边。
2. 右移 x, 即把 x 移动到最右边。

  请你回答经过 M 次操作之后, 数组从左到右每个数是多少?

输入格式

  第一行包含 2 个整数, N 和 M 。

  以下 M 行每行一个操作, 其中 “L x "表示左移x,"Rx "表示右移x 。

输出格式

  输出 N 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明

  样例中的数组变化如下:

$[1,2,3,4,5]\to [3,1,2,4,5]\to [2,3,1,4,5]\to [2,3,4,5,1]$

  评测用例规模与约定

  对于 50% 的评测用例, 1≤N,M≤10000.

  对于 100% 的评测用例, 1≤N,M≤200000,1≤x≤N.

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

2、解题思路与代码实现

2.1 方法一：使用LinkedList双向链表实现(50%)

  我们使用双向链表结构来存储这N个元素，若输入的是L x，我们就找到这个x,将该节点移动到链表的头部，可以直接将该节点删除，然后使用addFirst(E e)方法直接插入到链表头部。

  若输入的是R x,我们也找到这个x，然后使用addLast(E e)将该节点移动到链表的尾部即可。

  双向链表插入和删除元素比较快，但是我们的时间主要花费在了查找x这个值上面，这个方法只能通过50%的测试用例

import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();LinkedList<Integer> list = new LinkedList<>();for (int i = 0; i <n; i++) {list.addLast(i+1);}for (int i = 0; i <m ; i++) {String s = scan.next();int num = scan.nextInt();if(s.equals("L")){//左移//删除此列表中指定元素的第一个出现（从头到尾遍历列表时//由于此集合中没有重复元素，所以结果正确list.removeFirstOccurrence(num);list.addFirst(num);}else{//右移list.removeFirstOccurrence(num);list.addLast(num);}}list.forEach(x->{System.out.print(x+" ");});scan.close();}
}

2.2 方法二：使用HashMap+左右临界值实现(100%)

  我们使用HashMap存储这n个值，初始化的时候key和value相等，都存的是数值。

  定义两个边界，左边界：l=0，有边界：r=n+1

  然后从第一个元素开始遍历，当接收到L x，开始左移的时候，我们的key不动，将value赋值为左边界l，并将左边界自减l--。

  当接收到R x，开始右移动的时候，我们同样将key不动，将value赋值为右边界R，同时将右边界的值自增r++。

  遍历结束之后，我们只需要将map中的值按照value排序，然后输出排序之后的key即可。

  移动的过程如下图所示

import java.util.*;
import java.util.stream.Collectors;public class ACCode {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int l=0;//最左临界值int r=n+1;//最优临界HashMap<Integer, Integer> map = new HashMap<>();//key和value的初始化for (int i = 1; i <=n ; i++) {map.put(i,i);}for (int i = 0; i <m ; i++) {String s = scan.next();int num = scan.nextInt();if(s.equals("L")){//如果是左移，将value赋值为左临界值，再将左临界值自减map.put(num,l--);}else{//如果是右移，则将value赋值为右临界值，并将右边临界值+1map.put(num,r++);}}//查看此时的mapSystem.out.println(map);//将map根据value排序并输出map.entrySet().stream().sorted(Map.Entry.comparingByValue()).map(Map.Entry::getKey).collect(Collectors.toList()).forEach(x->System.out.print(x+" "));}
}

  输入测试用例，顺便打印下移动结束之后的map

方法二思路来源：https://blog.csdn.net/weixin_64061088/article/details/128696642