网站建设所要花费的资金,建筑咨询公司是做什么的,建设银行人才招聘网站,职业教育网站建设目录1.左移右移1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围6.原题链接2.解题思路3.Ac_code1.左移右移
1.题目描述
小蓝有一个长度为 NNN 的数组, 初始时从左到右依次是 1,2,3,…N1,2,3, \ldots N1,2,3,…N 。
之后小蓝对这个数组进行了 MMM 次操作, 每次…
目录1.左移右移1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围6.原题链接2.解题思路3.Ac_code1.左移右移
1.题目描述
小蓝有一个长度为 NNN 的数组, 初始时从左到右依次是 1,2,3,…N1,2,3, \ldots N1,2,3,…N 。
之后小蓝对这个数组进行了 MMM 次操作, 每次操作可能是以下 2 种之一: 左移 xxx, 即把 xxx 移动到最左边。 右移 xxx, 即把 xxx 移动到最右边。
请你回答经过 MMM 次操作之后, 数组从左到右每个数是多少?
2.输入格式
第一行包含 2 个整数, NNN 和 MMM 。以下 MMM 行每行一个操作, 其中 “LxLxLx 表示左移 xxx ,RxRxRx 表示右移 xxx 。
3.输出格式
输出 NNN 个数, 代表操作后的数组。
4.样例输入
5 3 L 3 L 2 R 1
5.样例输出
2 3 4 5 1
6.数据范围
1≤N,M≤200000,1≤x≤N.1≤N,M≤200000,1≤x≤N.1≤N,M≤200000,1≤x≤N.
6.原题链接
左移右移
2.解题思路 题目的含义非常简单如果按照朴素的方式遍历寻找 xxx然后直接进行插入操作在nnn的级别在2e52e52e5的范围这时间复杂度显然是不可接受的。想要解决此题我们需要思考两个点:
如何高效地进行插入和删除操作如何快速地找到某个点所在的位置 对于第一点我们应该快速地想到链表这个数据结构由于题目需要在左端点和右端点都进行插入操作所以我们应该联想到 双链表 。它可以在O(1)O(1)O(1)的时间范围内对元素进行插入和删除这显然是我们需要的数据结构。 当然双链表并不支持高效地查找所以我们如何快速找到 xxx 的位置呢这时候我们应该联想到 哈希表因为我们需要手动实现双链表所以每个链表结点都对应一个值同时它也是一个对象我们可以使用哈希表以值为keykeykey以这个链表结点对象为valuevaluevalue。这样我们就可以快速获得这个结点然后再进行常规的双链表插入删除操作。
3.Ac_code
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;public class Main {static MapInteger,Node mapnew HashMap();static PrintWriter outnew PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) {Scanner scnew Scanner(System.in);int nsc.nextInt();int msc.nextInt();//双链表的头结点和尾结点Node headnew Node(-1,null,null);Node lastnew Node(-1,null,null);Node prehead;//构建双链表for (int i 1; i n; i) {pre.nextnew Node(i,pre,null);prepre.next;map.put(i,pre);}last.prepre;pre.nextlast;for (int i 0; i m; i) {char csc.next().charAt(0);int xsc.nextInt();//先将x对应的结点在双链表中删除Node nodemap.get(x);node.pre.nextnode.next;node.next.prenode.pre;if (cL){//将其插入到左端点node.nexthead.next;head.next.prenode;head.nextnode;node.prehead;}else{//将其插入到右端点node.prelast.pre;last.pre.nextnode;node.nextlast;last.prenode;}}prehead.next;while (pre!last){out.print(pre.v );prepre.next;}out.flush();}static class Node{int v;Node pre;Node next;public Node(int v, Node pre, Node next) {this.v v;this.pre pre;this.next next;}}
}
