題目描述
拉里有一串N個數字的陣列A，A={a1,a2,…,aN-1,aN}，每個數字ai都是獨特不重複的。拉里想要用他的機器人來排序這個陣列A，他的機器人可以不限次數地任意旋轉某3個連續相同的元素，舉例來說：ABC旋轉一次之後會變成BCA，再旋轉一次會變成CAB，再旋轉一次又會回到ABC。
如果A={1,6,5,2,4,3}，然後機器人旋轉了(6,5,2)，A的內容就會變成{1,5,2,6,4,3}。
計算每組測試資料，並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以，輸出「YES」；如果不行，輸出「NO」。
原題網址
輸入格式
輸入第一行包含一個整數T，為測試資料的數量，範圍在1到10之間(包含1和10)。
接下來的的2T行，每兩行表示一組測試資料。一組測試資料的第一行是一個整數N，為A陣列的大小，範圍在3到1000之間(包含3和1000)。第二行輸入N個整數表示A陣列的內容，可以用ai來表示輸入的元素數值，數值範圍在1到N之間(包含1和N)，每個元素的數值都不相同。
輸出格式
計算每組測試資料，並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以，輸出「YES」，否則輸出「NO」。
範例輸入
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4
範例輸出
YES
NO
額外解釋
用Aj表示每次旋轉後A陣列的內容。
測試資料1：
A0={3,1,2}→rotate(3,1,2)→A1={1,2,3}
A陣列已經排序好了，因此輸出「YES」。
測試資料2：
A0={1,3,4,2}→rotate(3,4,2)→A1={1,4,2,3}
A1={1,4,2,3}→rotate(4,2,3)→A2={1,2,3,4}
A陣列已經排序好了，因此輸出「YES」。
測試資料3：
沒有辦法將A陣列排序好，輸出「NO」。
解題概念
可以把這題所用到的演算法，當作是氣泡排序法(Bubble Sort)的改版。原始的氣泡排序法一次旋轉兩個元素，而這裡用到的演算法一次需旋轉三個元素。我們可以從第一個元素(陣列索引0)開始，由陣列的最尾端開始往前旋轉，把最小的數值旋轉至第一個元素的位置。接著再從第二個元素(陣列索引1)開始，由陣列的最尾端開始往前旋轉，把最小的數值旋轉至第二個元素的位置，如此一來就可以完成這三旋轉的氣泡排序法。
至於該如何判斷這三旋轉的氣泡排序法是否排序成功，只需要在排到最後時，判斷最後兩個元素的順序是否正確即可，因為在這最後兩個元素之前的元素都已經確定排序好了。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
int testCase = sc.nextInt();
TestCase:
while (testCase-- > 0) {
final int n = sc.nextInt();
final int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = sc.nextInt();
}
final int n_dec3 = n - 3;
for (int i = 0; i <= n_dec3; ++i) {
for (int j = n_dec3; j >= i; --j) {
final int x = a[j];
final int y = a[j + 1];
final int z = a[j + 2];
if (z <= y && z <= x) {
a[j] = z;
a[j + 1] = x;
a[j + 2] = y;
} else if (y <= x && y <= z) {
a[j] = y;
a[j + 1] = z;
a[j + 2] = x;
} else{
// don't need to rotate
}
}
}
System.out.println(a[n - 2] <= a[n - 1] ? "YES" : "NO");
}
}
}