小易有一個(gè)長(zhǎng)度為n的整數(shù)序列,a_1,...,a_n挑辆。然后考慮在一個(gè)空序列b上進(jìn)行n次以下操作:
1风科、將a_i放入b序列的末尾
2浅萧、逆置b序列
小易需要你計(jì)算輸出操作n次之后的b序列穿剖。輸入描述:
輸入包括兩行,第一行包括一個(gè)整數(shù)n(2 ≤ n ≤ 2*10^5),即序列的長(zhǎng)度。
第二行包括n個(gè)整數(shù)a_i(1 ≤ a_i ≤ 10^9),即序列a中的每個(gè)整數(shù),以空格分割欧穴。輸出描述:
在一行中輸出操作n次之后的b序列,以空格分割,行末無(wú)空格民逼。輸入例子1:
4
1 2 3 4輸出例子1:
4 2 1 3
網(wǎng)易的筆試時(shí)間真是不夠，兩個(gè)小時(shí)涮帘，20道選擇拼苍，3道編程題，選擇題考的范圍極廣调缨，我那套卷涉及到了C++疮鲫，Java，數(shù)據(jù)結(jié)構(gòu)弦叶，操作系統(tǒng)俊犯，計(jì)算機(jī)網(wǎng)絡(luò)，數(shù)據(jù)庫(kù)伤哺，Linux命令燕侠，Android，后端服務(wù)器立莉，正則表達(dá)式等知識(shí)绢彤，我大概花了30多分鐘做選擇題，導(dǎo)致后面做編程題的時(shí)間連一個(gè)半小時(shí)都不到蜓耻。
這道題是三道編程題中的第二道茫舶，解題時(shí)我犯了一個(gè)比較致命的錯(cuò)誤：『讀懂題意后，就順著題目描述的過(guò)程開(kāi)始敲代碼刹淌，而沒(méi)有仔細(xì)思考有沒(méi)有時(shí)間復(fù)雜度更低的解法』
按照題目的描述奇适，整個(gè)數(shù)組的操作過(guò)程無(wú)非就是：每讀入一個(gè)整數(shù)，將其放到整數(shù)序列末尾芦鳍，然后逆置整數(shù)序列嚷往。于是我按照這個(gè)過(guò)程寫出如下代碼：
public class OperateSequence {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* 逆置數(shù)組
*
* @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(" ");
}
}
}
}
}
然后提交運(yùn)行，結(jié)果如下圖
很明顯柠衅，上面這個(gè)O(n^2)的算法被卡了皮仁，感覺(jué)自己被套路了。菲宴。贷祈。
然后又重新在紙上列出n取不同值對(duì)應(yīng)的結(jié)果，整數(shù)序列按升序輸入喝峦，便于分析势誊，于是規(guī)律出來(lái)了：
1
2 1
3 1 2
4 2 1 3
5 3 1 2 4
6 4 2 1 3 5
換個(gè)姿勢(shì)看看，秒懂了吧
1
2 | 1
3 1 | 2
4 2 | 1 3
5 3 1 | 2 4
6 4 2 | 1 3 5
其最后輸出的序列分兩部分谣蠢，前一半從最后一個(gè)數(shù)開(kāi)始以2為步長(zhǎng)遞減粟耻；后一半根據(jù)整數(shù)個(gè)數(shù)的奇偶查近，分別從第二個(gè)或第一個(gè)數(shù)開(kāi)始以2為步長(zhǎng)遞增。找到了這個(gè)規(guī)律挤忙，O(n)的算法就很容易寫出來(lái)了：
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) { // 前一半從最后一個(gè)數(shù)開(kāi)始以2為步長(zhǎng)遞減
System.out.print(nums[i] + " ");
}
for (int i = n % 2; i < n - 2; i += 2) { // 后一半根據(jù)整數(shù)個(gè)數(shù)的奇偶霜威，分別從第二個(gè)或第一個(gè)數(shù)開(kāi)始以2為步長(zhǎng)遞增
System.out.print(nums[i] + " ");
}
System.out.print(nums[n - 2]); // 最后一個(gè)數(shù)
}
}
}
提交運(yùn)行上述代碼，完美AC册烈，本題OJ傳送門在此
但遺憾的是戈泼，在考試時(shí)間內(nèi)，我雖然找到了規(guī)律赏僧，但代碼沒(méi)寫完大猛。至于第三題，我連看的時(shí)間都沒(méi)有淀零。最后挽绩，三道編程題只AC1.5道。窑滞。琼牧。
平時(shí)自己刷題時(shí)都習(xí)慣先暴力求解恢筝，再去思考最優(yōu)解哀卫，但是在真實(shí)的考試中，時(shí)間是不允許的撬槽，出題人還會(huì)刻意的去卡你的時(shí)間復(fù)雜度此改，吸取這次慘痛教訓(xùn)吧。
