360

admin管理员组

文章数量:1516870

360

题目：
给定一个1到N的排列P1到PN（N为偶数），初始时Pi=i（1≤i≤N），现在要对排列进行M次操作，每次操作为以下两种中一种：
①将排列的第1个数移到末尾；
②交换排列的第1个数与第2个数、第3个数与第4个数、…、第N-1个数与第N个数。
求经过这M次操作后得到的排列。

输入描述
第一行包含两个整数N和M，2≤N，M≤10^5。
第二行包含M个空格隔开的整数t1到tM，1≤ti≤2。若ti=1，则表示第i次操作为操作①；若ti=2，则表示第i次操作为操作②。
输出描述
输出N个空格隔开的整数，即经过M次操作后得到的排列。
示例
输入：
6 3
1 2 1
输出：
2 5 4 1 6 3
描述：
一开始是 1 2 3 4 5 6，经过操作1后为：2 3 4 5 6 1，经过操作2后为：3 2 5 4 1 6，经过操作1后为：2 5 4 1 6 3

思路 基于java

首先这道题，即使你啥都不会，你也可以通过暴力法解决，我们可以使用一个LinkedList，当操作1时，pollfirst然后将其add到尾部；操作2时，就交换。
但是当数据量变大或者操作变得频繁，问题就来了，很明显最耗时间的是操作2，这个时间复杂度的O(n/2*(操作2的次数))。

那我们能不能想办法把操作2聚合起来？
当然是可以，但是有一个问题，中间有若干次操作1怎么办？
那好，我遇到操作1我就把目前操作2的聚合执行一次。
那如果我是2，1，2，1，2，1....怎么办？

让我们再来分析下示例，操作1 2 1变化过程为：
1 2 3 4 5 6
2 3 4 5 6 1 ···· 操作1
3 2 5 4 1 6 ···· 操作2
2 5 4 1 6 3 ···· 操作1

操作1的步骤，实际上就是一次更换链表头”的操作，链表头变成了下一个元素；
操作2的步骤，实际上也是一次更换链表头”的操作（对于表头而言），链表头变成了下一个元素；

两者对于链表表头来说，其实都包含了一次更换链表头为原链表头下一元素的操作。

再来说操作2，操作2是交换排列的第1个数与第2个数、第3个数与第4个数、…、第N-1个数与第N个数。发现了吗，这个操作很单一呀，都只是前一个跟后一个交换位置。

我们为什么用链表来做呢？因为操作1的关系，注定我们用数组来做是不友好的。那由这里引申，我们是不是有必要维持整个数据在同一条链表里面？

仔细看看操作1，因为题目说链表的长度是偶数（我们这里的坐标当作是1开始好了，比较容易理解），其实也就是把表头（奇数位置）放到一个偶数位置后面而已；
操作2，不过就是把奇偶数的位置互换而已。

来个图吧！

发现了吗，操作1、2好像每次都会更换红蓝色数据的位置。我们可以维持两个链表，一个奇数一个偶数。而正确结果，是先打印上面的一个数据，然后再下面的一个数据，上下上下…所以我们需要一个变量来标识，当前应该先从奇数链表开始，还是先从偶数链表开始。

上上代码，或许你该差不多懂了。

    public static void main(String[] args){Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){int n = scanner.nextInt();int m = scanner.nextInt();int[] arr = new int[m];for (int i = 0; i < m ; i++) {arr[i] = scanner.nextInt();}getOut(n,arr);}}private static void getOut(int n, int[] arr) {LinkedList<Integer> list1 = new LinkedList<>();LinkedList<Integer> list2 = new LinkedList<>();boolean flag = true; // true的时候把list1当成首 false时list2为首for (int i = 1; i <= n ; i++) {if (i%2!=0){list1.add(i);}else {list2.add(i);}}for (int i = 0; i < arr.length ; i++) {if (arr[i]==1){if (flag){Integer val = list1.pollFirst();list1.addLast(val);}else {Integer val = list2.pollFirst();list2.addLast(val);}flag = !flag;}else if (arr[i]==2){flag = !flag;}}if (flag){while (!list1.isEmpty()&&!list2.isEmpty()){System.out.print(list1.pollFirst()+" ");System.out.print(list2.pollFirst()+" ");}}else {while (!list1.isEmpty()&&!list2.isEmpty()){System.out.print(list2.pollFirst()+" ");System.out.print(list1.pollFirst()+" ");}}}

进一步发现，操作1我们还能再优化~

public class Main {public static void main(String[] args){Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){int n = scanner.nextInt();int m = scanner.nextInt();int[] arr = new int[m];for (int i = 0; i < m ; i++) {arr[i] = scanner.nextInt();}getOut(n,arr);}}private static void getOut(int n, int[] arr) {LinkedList<Integer> list1 = new LinkedList<>();LinkedList<Integer> list2 = new LinkedList<>();// true的时候把list1当成首 false时list2为首boolean flag = true;int actionFirstOfList1 = 0;int actionFirstOfList2 = 0;for (int i = 1; i <= n ; i++) {if (i%2!=0){list1.add(i);}else {list2.add(i);}}for (int i = 0; i < arr.length ; i++) {if (arr[i]==1){if (flag){actionFirstOfList1++;}else {actionFirstOfList2++;}}flag = !flag;}actionFirstOfList1 = actionFirstOfList1%(n/2);actionFirstOfList2 = actionFirstOfList2%(n/2);while (actionFirstOfList1>0){Integer val = list1.pollFirst();list1.addLast(val);actionFirstOfList1--;}while (actionFirstOfList2>0){Integer val = list2.pollFirst();list2.addLast(val);actionFirstOfList2--;}if (flag){while (!list1.isEmpty()&&!list2.isEmpty()){System.out.print(list1.pollFirst()+" ");System.out.print(list2.pollFirst()+" ");}}else {while (!list1.isEmpty()&&!list2.isEmpty()){System.out.print(list2.pollFirst()+" ");System.out.print(list1.pollFirst()+" ");}}}
}

码字来之不易，有帮助的伙伴点个赞鸭~

本文标签： 360