东莞网站建设-拥有多年专业,网站建设案例哪家好,网站百度秒收,雁塔区住房和城乡建设局网站蓝桥杯-左移右移1、问题描述2、解题思路与代码实现2.1 方法一#xff1a;使用LinkedList双向链表实现(50%)2.2 方法二#xff1a;使用HashMap左右临界值实现(100%)1、问题描述 小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。 之后小蓝对这个数组进行了 M 次操…
蓝桥杯-左移右移1、问题描述2、解题思路与代码实现2.1 方法一使用LinkedList双向链表实现(50%)2.2 方法二使用HashMap左右临界值实现(100%)1、问题描述 小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。 之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:
左移 x, 即把 x 移动到最左边。右移 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][1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[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();LinkedListInteger list new LinkedList();for (int i 0; i n; i) {list.addLast(i1);}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相等都存的是数值。 定义两个边界左边界l0有边界rn1 然后从第一个元素开始遍历当接收到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 l0;//最左临界值int rn1;//最优临界HashMapInteger, 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
