題目內容
題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/
題意分析
又是一個有故事的題目，最討厭了，不要管魚的故事的話，大概就是有一個循序數列會從0~N-1這樣子，例如[1,2,3,4,5]，但是不會照著順序排列，而是會打散著的排列，如[4,3,2,1,5]，然後有另一個陣列B，會指定該數字是往上還是往下，如[0,1,0,0,0]，接著往下的若是遇到往上的，就比大小，刪掉較小的數字。
然後回傳最後剩下的數字的數量
解題紀錄
這是我第一次的解題紀錄
function solution(A, B) {
var point = 0
while(point < B.length){
var currnet_direction = B[point]
if(currnet_direction == 0){//往上
while(point > 0 && A[point-1] < A[point]){
//吃掉目標
A.splice(point,1)
B.splice(point,1)
}
//換目標
point++
}else{//往下
while(point < B.length-1 && A[point+1] < A[point]){
//吃掉目標
A.splice(point+1,1)
B.splice(point+1,1)
}
//換目標
point++
}
}
return A.length
}
只拿了12分，慘不忍睹，應該有思考邏輯上的錯誤。
仔細想一下這一題，我覺得應該會是2N左右的複雜度，就是往上遍歷一次、往下遍歷一次。往下遍歷時，選擇方向為下的，且之後的數字的方向為上的，把該吃掉的吃掉。接著再從下往上一次，選擇方向為上的，且之前的數字的方向為下的，把該吃掉的吃掉，應該就會試剩下的了。
下面為嘗試的實作程式碼
function solution(A, B) {
var alive_A = []
var alive_B = []
// 往下
while(A.length > 0){
var target = A.shift()
var target_direction = B.shift()
while(target_direction == 1 && B[0] == 0 && target > A[0]){
A.shift()
B.shift()
}
alive_A.push(target)
alive_B.push(target_direction)
}
A = alive_A
B = alive_B
alive_A = []
alive_B = []
//往上
while(A.length > 0){
var target = A.pop()
var target_direction = B.pop()
while(target_direction == 0 && B[B.length-1] == 1 && target > A[A.length-1]){
A.pop()
B.pop()
}
alive_A.push(target)
alive_B.push(target_direction)
}
return alive_A.length
}
25%，慘不忍睹+1。
我發現問題是他們往上或往下可能不會只有兩次，而是會不停地變換方向，所以應該會需要把這樣的程式碼抽出來，然後使用迴圈或遞迴的去呼叫。但是比較慘的是，下面的效能測試其實是超時的，若是再透過遞迴或者迴圈，整個效能應該會更差。
觀察之後，因為我是整個陣列去掃，而事實上，他們往上或往下的範圍不會是整個陣列，而會是遇到與自己方向不同的範圍。所以我覺得應該不會是完整的掃過兩次迴圈，而是會有兩層的迴圈，然後根據現在的方向，掃到以自己方向為準最多可吃掉的位置做停止，在構想上應該比較類似我第一次的做法。
function solution(A, B) {
var point = 0
var finish = 0
while(A.length > 0){
if(point >= A.length ){
point = A.length-1
}
//console.log("main", A, B, point)
if(point == 0 && B[point] == 0){
finish ++
A.shift()
B.shift()
}else if(point == A.length-1 && B[A.length-1] == 1){
finish ++
A.pop()
B.pop()
}else{
var target_direction = B[point] == 0 ? -1:1
while(A[point] > A[point+target_direction] && B[point] != B[point+target_direction]){
A.splice(point+target_direction,1)
B.splice(point+target_direction,1)
}
point = point+target_direction
}
}
return finish
}
邏輯正確了，但是效能不佳…要來優化了!
上面的作法會耗時間是因為下面的原因
- 使用了 while 迴圈，導致較長的運行時間。while 迴圈對於每條魚的比較都需要遍歷數組中的某些元素。相比之下，前面的實現使用了 for 迴圈，因此在處理每條魚時，它只需要對數組中的一個元素進行操作。
- 這個實現使用了多次數組操作，例如 splice()、shift() 和 pop()。這些操作可能會導致重新分配和複製整個數組，導致更長的運行時間。若只使用了一個堆疊紀錄往上的魚，原本的全部都是往下的，操作次數會少得多。
為了解決這個問題，我們可以使用一個堆疊，它用於記錄下游游動的魚，這些魚還沒有被吃掉。從頭到尾遍歷所有魚，並將所有向上游動的魚推入堆疊。如果遇到向下游動的魚，則將其與堆疊中的魚進行比較。如果堆疊中的魚較小，則將其彈出，並繼續與新的堆疊頂部進行比較，直到它遇到較大的魚，或者堆疊為空。
在這個算法中，堆疊中的魚保證向下游動，因此它們是可以被吃掉的魚。當向上游動的魚遇到堆疊頂部的魚時，它們的大小也被比較。如果它們相等，它們都可以保持存活，因為它們不會相互吃掉。如果向上游動的魚比堆疊頂部的魚大，則堆疊中的魚會被吃掉，否則向上游動的魚會被堆疊頂部的魚吃掉。在此過程中，我們不斷更新堆疊的內容，以便在下一輪比較中使用。
最後，堆疊中剩下的所有魚都可以保持存活，因為它們沒有遇到向下游動的魚，或者在它們前面的向下游動的魚都比它們大。
function solution(A, B) {
var alive = 0
var downstream = []
for (var i = 0; i < A.length; i++) {
if (B[i] == 1) {
downstream.push(A[i])
} else {
//開始吃掉之前的往下的魚直到自己被吃掉
while (downstream.length > 0 && downstream[downstream.length - 1] < A[i]) {
downstream.pop()
}
if(downstream.length == 0){
//過關
alive++
}
}
}
return alive + downstream.length
}
https://app.codility.com/demo/results/trainingHMNQVG-XRN/
