网易有道2018校招编程题 —— 操作序列

小易有一个长度为n的整数序列,a_1,...,a_n。然后考虑在一个空序列b上进行n次以下操作:
1、将a_i放入b序列的末尾
2、逆置b序列
小易需要你计算输出操作n次之后的b序列。

输入描述:
输入包括两行,第一行包括一个整数n(2 ≤ n ≤ 2*10^5),即序列的长度。
第二行包括n个整数a_i(1 ≤ a_i ≤ 10^9),即序列a中的每个整数,以空格分割。

输出描述:
在一行中输出操作n次之后的b序列,以空格分割,行末无空格。

输入例子1:
4
1 2 3 4

输出例子1:
4 2 1 3

网易的笔试时间真是不够，两个小时，20道选择，3道编程题，选择题考的范围极广，我那套卷涉及到了C++，Java，数据结构，操作系统，计算机网络，数据库，Linux命令，Android，后端服务器，正则表达式等知识，我大概花了30多分钟做选择题，导致后面做编程题的时间连一个半小时都不到。

这道题是三道编程题中的第二道，解题时我犯了一个比较致命的错误：『读懂题意后，就顺着题目描述的过程开始敲代码，而没有仔细思考有没有时间复杂度更低的解法』

按照题目的描述，整个数组的操作过程无非就是：每读入一个整数，将其放到整数序列末尾，然后逆置整数序列。于是我按照这个过程写出如下代码：

public class OperateSequence {


    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 逆置数组
     *
     * @param arr
     * @param n
     */
    public static void reverseArr(int[] arr, int n) {
        int c = n / 2;
        int d = 1;
        if (n % 2 == 0) {
            while (c - d >= 0 && c + d - 1 < n) {
                swap(arr, c - d, c + d - 1);
                d++;
            }
        } else {
            while (c - d >= 0 && c + d < n) {
                swap(arr, c - d, c + d);
                d++;
            }
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
                reverseArr(nums, i + 1);
            }
            for (int i = 0; i < n; i++) {
                System.out.print(nums[i]);
                if (i != n - 1) {
                    System.out.print(" ");
                }
            }
        }
    }
}

然后提交运行，结果如下图

很明显，上面这个O(n^2)的算法被卡了，感觉自己被套路了。。。
然后又重新在纸上列出n取不同值对应的结果，整数序列按升序输入，便于分析，于是规律出来了：

1
2 1
3 1 2
4 2 1 3
5 3 1 2 4
6 4 2 1 3 5

换个姿势看看，秒懂了吧

    1
    2 | 1
  3 1 | 2
  4 2 | 1 3
5 3 1 | 2 4
6 4 2 | 1 3 5

其最后输出的序列分两部分，前一半从最后一个数开始以2为步长递减；后一半根据整数个数的奇偶，分别从第二个或第一个数开始以2为步长递增。找到了这个规律，O(n)的算法就很容易写出来了：

public class OperateSequence {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            for (int i = n - 1; i >= 0; i -= 2) {     // 前一半从最后一个数开始以2为步长递减
                System.out.print(nums[i] + " ");
            }
            for (int i = n % 2; i < n - 2; i += 2) {  // 后一半根据整数个数的奇偶，分别从第二个或第一个数开始以2为步长递增
                System.out.print(nums[i] + " ");
            }
            System.out.print(nums[n - 2]);  // 最后一个数
        }
    }
}

提交运行上述代码，完美AC，本题OJ传送门在此

但遗憾的是，在考试时间内，我虽然找到了规律，但代码没写完。至于第三题，我连看的时间都没有。最后，三道编程题只AC1.5道。。。

平时自己刷题时都习惯先暴力求解，再去思考最优解，但是在真实的考试中，时间是不允许的，出题人还会刻意的去卡你的时间复杂度，吸取这次惨痛教训吧。