題目
New Year Chaos
舉例輸入
2
5
2 1 5 3 4
5
2 5 1 3 4
舉例輸出
3
Too chaotic
解析
文章首次來了個中階題,還真的有點難
題旨:一條隊伍,開放插隊,一個人最多插隊兩次,給予變動後的隊伍,試問插隊過程發生了幾次
若無法推算則輸出Too chaotic
所以我們要判斷的事情有兩件
1.換了幾次?
2.有沒有可能換成輸入?
function minimumBribes(q) {
let bribeCountObj = {};
//交換標誌
let swapped = false;
q.forEach((item) => bribeCountObj[item] = 0);
//賄絡次數
let bribeCount = 0;
//這圈檢測內圈是不是仍有運作,因為有可能一次排不完
for (let i = 0; i < q.length; i++) {
//這圈開始排序
for (let j = 0; j < q.length; j++) {
//規則是如果目前的數大於後面的數"且"目前的數兩次的賄絡額度沒用完
let n = j + 1;
if (q[j] > q[n] && bribeCountObj[q[j]] < 2) {
//這個人的賄絡次數+1
bribeCountObj[q[j]] += 1;
// 位子互調
[q[j],q[n]]=[q[n],q[j]]
// //此圈有調換
swapped = true;
bribeCount++;
}
}
//如果這次都沒有排序,代表不需要再跑內層排序動作
if (swapped) {
swapped = false
} else {
break;
}
}
//檢測如果內容為正常序列,印出排序次數,否則印Too chaotic
console.log(isSorted(q) ? bribeCount : 'Too chaotic');
}
function isSorted(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}