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

@toc

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]→[3,1,2,4,5]→[2,3,1,4,5]→[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赋值为右临界值，并将右边临界值+1
                map.put(num,r++);
            }
        }
		//查看此时的map
        System.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