小易有一个长度为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道。。。
平时自己刷题时都习惯先暴力求解，再去思考最优解，但是在真实的考试中，时间是不允许的，出题人还会刻意的去卡你的时间复杂度，吸取这次惨痛教训吧。
网友评论