LeetCode

淺談 Heap 資料結構 前言 這個系列會紀錄我在 Leetcode 上複習的一些常見的東西。基本上會跟著探索卡的進度走。雖然這系列應該早就在課堂上學會了，但我就豆腐腦，雖然已經理解了，但是只要一過一段時間，記憶就這樣被回收了，我都懷疑我腦袋有一個GC回收器… 優先佇列 (Priority Queue) 再講 Heap 之前，要先介紹一下優先佇列 Priority Queue： 既然優先佇列的名稱裡都有佇列了，那他肯定跟佇列有關係對吧？ 優先佇列就像是普通的先進先出(FIFO)的佇列一樣，但是其每個元素都有優先權(Priority)這個變數，優先佇列的特點就是：優先權較高者的永遠會先被處理，如果對 Heap 有印象的人，看到現在應該知道為什麼要先介紹優先佇列了。 那要怎麼實現 Priority Queue 呢？ Priority Queue 就如同佇列一樣有兩個關鍵方法：push()、pull() 如果將元素存放在一個未排序列表中， 那push() 操作正常來說只需要O(1)就能完成，因為只是單純的將元素推到這個列表的最後端，範例如下： func push(n *Node) { unsortedList = append(unsortedList, n) } 但是pull()操作呢？ 正常來說需要O(n)時間，也就是需要遍歷完整個列表，範例如下： func pull() *Node { if len(unsortedList) == 0 { return nil } maxIndex, highest := 0, unsortedList[0] for i := 1; i < len(unsortedList); i++ { if highest.Priority < unsortedList[i].Priority { highest = unsortedList[i] maxIndex = i } } // remove highest item unsortedList = append(unsortedList[:maxIndex], unsortedList[maxIndex + 1:]....

題目要求是要輸入一個運算式回傳該運算式的結果 有下列規則 “t”，代表為 True “f”，代表為 False “!(expr)"，表示將expr得出的布林值反向 “&(expr1,expr2,…)"，表示將所有expr{num}做AND “|(expr1,expr2,…)"，表示將所有expr{num}做OR 馬上進入程式碼撰寫的部分，主要是以遞迴解決 我的想法應該算蠻差的，效能那些部分都不能強求，所以僅放上來做參考，歡迎底下討論 class Solution { companion object{ // 運算子列表 val operator = arrayOf('!', '&', '|') } fun parseBoolExpr(expression: String): Boolean { // 如果運算式為空，回傳 `False` if (expression.isEmpty()) return false return expr(expression) } fun expr(expression: String): Boolean{ // 如果運算式的首個元素不包含於運算子列表(!、&、|)，回傳 `False` if (!operator.contains(expression[0])) return false // 取得運算子 val mod = expression[0] // 檢查運算子後的下一個字元是否為 `(` val optStart = if(expression[1] == '(') 1 else throw RuntimeException("not valid pattern") // 檢查運算式的最後一個字源是否為 `)` val optEnd = if(expression[expression....