快訊!我的新書登上天瓏網路書店11月份暢銷榜第一名啦!看過的都說讚!歡迎大家前往訂購!
>>>> AI 職場超神助手:ChatGPT 與生成式 AI 一鍵搞定工作難題 <<<<

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/


17年資歷女工程師,專精於動畫、影像辨識以及即時串流程式開發。經常組織活動,邀請優秀的女性分享她們的技術專長,並在眾多場合分享自己的技術知識,也活躍於非營利組織,辦理活動來支持特殊兒及其家庭。期待用技術改變世界。

如果你認同我或想支持我的努力,歡迎請我喝一杯咖啡!讓我更有動力分享知識!