[LeetCode] #725. Split Linked List in Parts

-

題目

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts".

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode's representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

直覺解

構想：

先計算整個 list 有多長，分成「list 長度 < k」和「list 長度 >= k」兩種狀況處理。
若 list 長度 < k，則每個 part 只有一個節點，剩下的位置就用 null 補滿。
若 list 長度 >= k，則計算每個 part 有多長，最後根據每個 part 的長度去分割 list。

javascript 實作：

const splitListToParts = function(root, k) { 

    const result = [] 

    let current = root 

    let prevNode 

    let length = 0 

    // 計算整個 list 有多長 

    while (current !== null) { 

        current = current.next 

        length++ 

    } 

 

    // 處理 list 長度 < k 的狀況 

    if (length < k) { 

        for (let i = 0; i < length; i++) { 

            result.push(root) 

            prevNode = root 

            root = root.next 

            prevNode.next = null 

        } 

         

        for (let i = 0; i < k - length; i++) { 

            result.push(null) 

        } 

        return result 

    } 

     

    // 處理 list 長度 >= k 的狀況 

    // 1. 計算每個 part 有多長 

    const quotient = Math.floor(length / k) 

    let remainder = length % k 

    const lengthOfParts = [] 

    for (let i = 0; i < k; i++) { 

         if (remainder > 0) { 

            lengthOfParts.push(quotient + 1) 

            remainder-- 

        } else { 

            lengthOfParts.push(quotient) 

        } 

    } 

 

    // 2. 根據每個 part 的長度去分割 list 

    lengthOfParts.forEach((length, index) => { 

        result.push(root) 

        for (let i = 0; i < length; i++) { 

            if (root === null) { 

                break 

            } 

            prevNode = root 

            root = root.next 

        } 

 

        if (prevNode) { 

            prevNode.next = null 

        }  

    }) 

    return result 

}

效能：

Runtime: 96 ms, faster than 19.44% of JavaScript online submissions for Split Linked List in Parts.
Memory Usage: 41 MB, less than 18.06% of JavaScript online submissions for Split Linked List in Parts.

構想：

先計算整個 list 有多長，再計算每個 part 有多長，最後根據每個 part 的長度去分割 list。

python 3 實作：

def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]: 

    result = [] 

         

    # count length of linked list 

    length = 0 

    current = root 

    while current: 

        current = current.next 

        length += 1 

         

    # count length of each parts 

    part_length = [] 

    for i in range(k): 

        part_length.append(length // k) 

    for i in range(length % k): 

        part_length[i] += 1 

         

    # split linked lis 

    for i in range(k): 

        if root: 

            result.append(root) 

            for i in range(part_length[i]): 

                current = root 

                root = root.next 

            current.next = None 

        else: 

            result.append(None) 

                 

    return result

效能：

Runtime: 40 ms, faster than 56.69% of Python3 online submissions for Split Linked List in Parts.
Memory Usage: 14.8 MB, less than 69.70% of Python3 online submissions for Split Linked List in Parts.

參考別人的解後

python 3 實作優化一：

構想：計算每個 part 的長度時，不再使用 for 回圈一個一個算，改成直接計算「比較長的有幾個」、「比較短的有幾個」。

def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]: 

    result = [] 

         

    # count length of linked list 

    length = 0 

    current = root 

    while current: 

        current = current.next 

        length += 1 

         

    # count length of each parts 

    chunk_size = length // k 

    larger_chunk = length % k 

    part_length = [chunk_size + 1] * larger_chunk + [chunk_size] * (k - larger_chunk) 

         

    # split linked lis 

    for i in range(k): 

        if root: 

            result.append(root) 

            for i in range(part_length[i]): 

                current = root 

                root = root.next 

            current.next = None 

        else: 

            result.append(None) 

                 

    return result

效能：

Runtime: 28 ms, faster than 98.33% of Python3 online submissions for Split Linked List in Parts.
Memory Usage: 14.7 MB, less than 69.70% of Python3 online submissions for Split Linked List in Parts.


python 3 實作優化二：

構想：不再另外宣告 result = [] 來儲存答案，而是直接把 part_length 改造成答案。為了方便對照，刪掉的地方姑且用 # 註解掉。

def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]: 

    # result = [] 

         

    # count length of linked list 

    length = 0 

    current = root 

    while current: 

        current = current.next 

        length += 1 

         

    # count length of each parts 

    chunk_size = length // k 

    larger_chunk = length % k 

    part_length = [chunk_size + 1] * larger_chunk + [chunk_size] * (k - larger_chunk) 

         

    # split linked list 

    for index, length in enumerate(part_length): 

        if root: 

            part_length[index] = root 

            for i in range(length): 

                current = root 

                root = root.next 

            current.next = None 

        else: 

            part_length[index] = None 

                 

    return part_length

效能（好像沒有比較節省空間）：

第一次

Runtime: 40 ms, faster than 56.69% of Python3 online submissions for Split Linked List in Parts.
Memory Usage: 14.7 MB, less than 69.70% of Python3 online submissions for Split Linked List in Parts.

第二次

Runtime: 32 ms, faster than 92.94% of Python3 online submissions for Split Linked List in Parts.
Memory Usage: 14.8 MB, less than 69.70% of Python3 online submissions for Split Linked List in Parts.

第三次

Runtime: 28 ms, faster than 98.33% of Python3 online submissions for Split Linked List in Parts.
Memory Usage: 14.8 MB, less than 69.70% of Python3 online submissions for Split Linked List in Parts.

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more