Posted on by

Stacks and Queues – Fish解題紀錄

題目內容

題目頁面: 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
}

邏輯正確了，但是效能不佳…要來優化了!

上面的作法會耗時間是因為下面的原因

  1. 使用了 while 迴圈，導致較長的運行時間。while 迴圈對於每條魚的比較都需要遍歷數組中的某些元素。相比之下，前面的實現使用了 for 迴圈，因此在處理每條魚時，它只需要對數組中的一個元素進行操作。
  2. 這個實現使用了多次數組操作，例如 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/