LeetCode 207. Course Schedule 207. Course Schedule 這一個題目的設計滿巧秒的，我個人覺得這個題目綜合了樹的遍歷（遞迴）、回溯法、動態規劃以及資料與圖形轉換的設計，外加上題目可以套用在各種現實生活問題中。所以整體而言 LeetCode 給出了中等難度，但是細節很多很需要小心的想通。 先看看題目可以怎麼想，所有的課程與其先修課程基本上就是很一顆或是很多棵樹，也就是說如果一棵樹裡面沒有任何的環，我們就知道不會有一個課程他的先修課是另外一門課，而那門課的先修課又是該堂課的情況。 目標就變得很明確，我們要找出此棵樹沒有環，但是就要回到題目看看給定的課程與先修課程的關係，這是一個數列，但是並沒有特定的排列順序，所以我們需要一個可以快速查找的課程有哪些先修課的表： table = defaultdict(list) for prerequisite in prerequisites: course, prerequisiteCourse = prerequisite table[course].append(prerequisiteCourse) 這張表就是前言一開始提到的資料與圖
Classic 1676. Lowest Common Ancestor of a Binary Tree IV 1676. Lowest Common Ancestor of a Binary Tree IV Check 235. Lowest Common Ancestor of a Binary Search Tree
Classic 1650. Lowest Common Ancestor of a Binary Tree III 1650. Lowest Common Ancestor of a Binary Tree III Check 235. Lowest Common Ancestor of a Binary Search Tree
LeetCode 1644. Lowest Common Ancestor of a Binary Tree II 1644. Lowest Common Ancestor of a Binary Tree II Check 235. Lowest Common Ancestor of a Binary Search Tree
Classic 236. Lowest Common Ancestor of a Binary Tree 236. Lowest Common Ancestor of a Binary Tree Check 235. Lowest Common Ancestor of a Binary Search Tree
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree * 235. Lowest Common Ancestor of a Binary Search Tree * 236. Lowest Common Ancestor of a Binary Tree * 1644. Lowest Common Ancestor of a Binary Tree II * 1650. Lowest Common Ancestor of a Binary Tree III * 1676. Lowest Common Ancestor of a Binary Tree IV 235, 236 的做法完全一模一樣。 # Definition for a
1884. Egg Drop With 2 Eggs and N Floors 1884. Egg Drop With 2 Eggs and N Floors 這個題目其實是一個經典的演算法：雙蛋問題 ，這是一個很經典的考題，但是我是面試完了才知道。 題目的敘述如同維基百科所寫： 給你兩個相同的異常堅硬的雞蛋，通過在一棟100層的樓的不同層扔下雞蛋進行實驗，試驗出可以摔碎該雞蛋的最高樓層（臨界樓層）。已知未碎的雞蛋可以重複使用。求最少的實驗次數 n，使得在 n 次實驗後，一定能判斷出該臨界樓層。 為了更加精確地思考問題，該問題中必須滿足以下的條件： 1. 如果雞蛋在某一層沒有碎，它不會在任何更低層的破碎。 2. 如果雞蛋在某一層碎了，它在更高層上一定會碎。 3. 雞蛋可能在一樓摔破，也可能在最高層還不摔破。 以上就是這個題目的精神，其實這個題目很像是我們在求時間複雜度的最糟狀況。 先思考的是如果我有無限顆雞蛋的情況下，最少的實驗次數一定是從中間的樓層開始丟，如果沒有破掉，我就在往更高樓的地方找，如果破掉了，我就往下找，每次的搜尋我都減少一半的搜索空間，如果我有一百層樓，搜索的次數會是 \(log_{2}100
LeetCode 5. Longest Palindromic Substring 5. Longest Palindromic Substring 這一題是我們要找出子字串中的最長的回文，其實最好從暴力解法開始學習起，前面的題目已經重複提過了好多次的回文的性質，這裡就用暴力法先來思考以下。 暴力法 (TLE) 那暴力法的方式就是我們窮舉出所有的子字串，並去看看哪一個字串是回文，而且長度最長就好了，窮舉的方式如下，直接就先固定左標，滑動右標一個一個把子字串窮舉出來。 class Solution: def longestPalindrome(self, s: str) -> str: substrings = [] # i 不用走到最後，因為走到最後的話就等於沒有字元了 for i in range(len(s)-1): # j 直接從 i 的下一個字元開始看起即可，長度為一個字元不用考慮。 for j in range(i+1, len(s)): substrings.
LeetCode 15. 3 Sum 15. 3 Sum 於是這樣就可以開始擴展當 n > 2 的時候， 該怎麼辦呢？ * 當 n == 1 的時候，沒有所謂的總和問題，所以答案為空集合。 * 當 n == 2 的時候，就是所謂的 2 Sum ，可以透過上方的方式找到 * 當 n == 3 的時候，是不是可以把設定的目標先剪去第一個陣列中的第 i 個數字，得到一個新目標，接著在剩下的兩個陣列中，用新的目標找 2 Sum 。 * … * 當 n == k 的時候，就可以推導出，先將目標減去第一個陣列中的第 i 個數字，得到一個新目標後，在接下來的 k - 1 個陣列中，找出 k-1
LeetCode 1041. Robot Bounded In Circle 題目是給定機器人一串字串，裡面包含了前進、右轉、左轉這三種指令。題目問說，如果持續給這個機器人一樣的指令很多次，機器人是否會回到原點？ 這題一開始我的直覺法是遞迴或是回朔的想法來解，因為我們需要機器人一直探索，一般來說如果要做遞迴或是回溯的題型，會很明確的定義出終止條件（Base case），還有動態轉移方程的變數，但是根據題目所寫，我們的目的是要機器人可以回到原點，回到原點就是我們的中止條件，但是要怎麼遞迴，其實我是想不出來的，因為看到題目的範例中，有指令走一次就回到原點了，也有走四次才回到原點。那到底走幾次能會到原點，一般來說遞迴的題目會有個 n 來方便我們慢慢一層一層地走下去，做為窮舉的最大上限，但是這題乍看之下還真的不知道，我們也不可能設定一個超大的 n 不斷地走看看到底有沒有中間會回到原點的情況。 其實我覺得這種題目比起出在 online assement ，應該更適合出在現實生活的白板題，因為我真的想破頭想不到要怎麼寫，所以自己想辦法出了幾個可以回到原點的指令（想到這個指令其實也很難）慢慢的在紙上畫出，才觀察出「好像」可以走回原點的指令，都在執行最多四次後就一定會回來！
LeetCode 354. Russian Doll Envelopes 354. Russian Doll Envelopes 這一題難度困難，最終的解法不難，難點是需要一點小技巧，跟怎麼推敲出題目的核心。 題目是我們有多封信封，長寬不一，我們要把小的信封放進大的信封，再放入更大的信封…依序下去。但是信封之間有可能完全沒辦法互相套入，例如，[1,3] 和 [2,4] ，前面的信封可以套入到後面的信封，我們就將其套入，但像是[1,5] 和 [2,4]，這時候就不再套入，最後我們要算出都套入完之後，套最多信封的那個信封有幾個信封。 這題的限制是前一個的信封的長寬，要小於下一個信封的長寬，如果我們在現實生活中，我們要套的話，我們會怎麼找信封呢？ 直覺的想法是，我一定是要先找出長和寬都相對最大的信封，因為這樣最有可能裝入最多的小信封，或者是，我手上拿著的信封，如果我要找下一個信封套著我，這個信封的長寬一定是要比我們現在這個信封大。下一個數字一定要嚴格的比我現在的數字大，這個題目就很像是遞增子序列，又我們要找到最多信封的套法，就變成要找了最長遞增子序列的問題。這個邏輯並不好想，我也是直接看別人的做法才知道的，不過可以先嘗試知道這個邏輯後，
LeetCode 300. Longest Increasing Subsequence 300. Longest Increasing Subsequence 這一個題目是比較容易用直覺判斷出是動態規劃的題目，難的地方是這個題目的動態轉移方程式，這一個題目，如果要想到動態轉移方程式的話，那就是我們在第 i 個位置的時候，其意義為何？ 先從基本的型態會是什麼？最長的遞增子序列就只有自己而已，那時候 dp[i] 就會是 1 。 這時候我們想要知道的就是 當我們已經知道 dp[0..i-1] 的所有數值時，要怎麼求 dp[i] 的數值？ 分兩個步驟想，第一個步驟是，我們要找到最長遞增子序列，和當前 nums[i] 有用的，只有在我前面，比我小的數字才有用，因為比他大的，都不可能增加最長遞增子序列的長度，所以我們要去找 nums[0..i-1]中 ，比 nums[i] 還小的數字。 找到之後，
LeetCode 146. LRU Cache 146. LRU Cache LRU Cache 這是一題經典題型，完全沒有概念的讀者我會建議一開始直接先看解答，懂概念後再做也沒關係的題目，因為這道題目的原理並不難，不如先把所有的東西都先搞定，面試前做熟就好了，因為就算知道原理，在真正要寫出程式的時候太多細節需要要求了，而且就算面試中面試官跟你講解了 LRU 快取的概念，沒有看過做法，真的很難做出來。 LRU Cache 個這裡一開始我就打算直接破題，這個題目的敘述可以直接到 LeetCode 上面看。 如果這輩子從來沒有寫過 LRU Cache 尤其大學不是念資工系的學生（像是我），極少數人應該可以在 45 分鐘內想到這題目需要用到 Doubly Linked List + Hash Table 。就算是上課有提到，我想教授應該也會直接跟大家講這個題目的核心觀念，不用太折騰自己要在 45 分鐘想出並寫完。 為何需要 Doubly Linked List ？ Doubly Linked List 可以幫我們做兩件事情，
LeetCode 435. Non-overlapping Intervals 435. Non-overlapping Intervals 這一題比前面的系列題目還稍難一點，但是思維很像一樣需要先將時間區間排序好，接著的目標是要找到移除幾個區間才能讓所有的會議都沒有重複的時間，這一題不能先把可以合併的時間都合併起來，因為當我們都合併起來之後，就會找不到到底哪一個需要被合併。 當所有的區間都按照順序排好後，就可以從早到晚開始去兩兩個區間判斷，需要考慮的情況有三種： 1. 沒有重疊 2. 有重疊，但是前一個時間區間的「結束點」比當前區間的結束時間點還「晚」，刪除「其中」一個區間 3. 有重疊，但是前一個時間區間的「結束點」比當前區間的結束時間點還「早」，刪除「其中」一個區間 這題最困難的地方就是想出這三個斷點，以及後面所謂的「其中」要怎麼選擇。 接著我們要去看為什麼上面這段話還需要判斷結束時間點，先看第二個條件： 如果說「前」一個時間區間的「結束」時間比「當前」區間的「結束」時間晚，那我們一定是很直覺的要刪除「比較大」的區間，
LeetCode 989. Add to Array-Form of Integer 989. Add to Array-Form of Integer class Solution: def addToArrayForm(self, num: List[int], k: int) -> List[int]: num[-1] += k for i in reversed(range(len(num))): carry = num[i] // 10 num[i] = num[i] % 10 if i: num[i-1] += carry while carry: num = [carry%10] + num carry
LeetCode 121. Best Time to Buy and Sell Stock 121. Best Time to Buy and Sell Stock 不斷的找出前低點，並且看看目前的價格是不是高點，當前的價格減去之前的最低點比當前的最高獲利高，那就代表我們有更好的獲利，更新最高獲利的數值。 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 min_cost = prices[0] max_profit = 0 for price in prices: min_cost = min(min_cost, price) max_profit = max(max_
LeetCode 138. Copy List with Random Pointer 138. Copy List with Random Pointer 這一題更能顯現為什麼 Hash Table 是一個非常好用的查找工具，這一題比前面幾題難困難的點在於，之前我們遍歷過的點，只要標記成造訪過，我們就可以不用再管他了，可是這一題多了一個如果說每個節點會隨機指向任何一個節點，也就是說會造成這個 Linked List 是有環的，我們就不能單純的遍歷整個 Linked List 來完成，不然複製 Linked List 是很簡單的一件事情，只要一步一步向前走就可以完成了。 我當時想到的一點就是，Hash Map 可以快速的幫我映射出原本圖型中的節點，可以快速對應到新圖型中的節點。 所以我決定先把這個映射建立起來，因為如果我有映射了，原圖型隨機對應到的節點，我用節點 X 做代表，我也可以用 Hash Table 去找到，那個 X 節點他在新圖形映射的節點 X' 是哪一個。這時候我就可以把這隨機連結的節點給連接起來了。 """ # Definition
LeetCode 259. 3Sum Smaller 259. 3Sum Smaller class Solution: def threeSumSmaller(self, nums: List[int], target: int) -> int: count = 0 nums.sort() for i in range(len(nums)): num = nums[i] left = i + 1 right = len(nums) - 1 while left < right: threeSum = num + nums[left] + nums[right] if threeSum < target: count += right
LeetCode 15. 3Sum 15. 3 Sum # target: 0 # [-1, -1, 2, -1] # -> [-1, -1, 2], [-1, 2, -1] choose one # Approach # For each number # 1. target - nums[0]: 1 # 2. Find two number in the rest of array which sum to -1 # -> Become a smaller question. it is 2 sum
LeetCode 170. Two Sum III - Data structure design 170. Two Sum III - Data structure design 在 2 Sum 裡面，有一個比較高效率的解法，就是使用 Hash Table 來解決問題，這題物件的題目就很簡單，不過有一個小地方要注意，那就是之前我們的 Hash Table 是記錄元素在陣列中的位置，但是這個物件讀取資料的方式是透過 Data Stream 的方式讀入，我們並沒有儲存位置，我們反而是記錄這個數字出現的次數。 可是這樣就會有一個問題要注意，例子是如果我先輸入一個 2 。接著，程式收到指令，再去找看看有沒有兩個數字的總和是 4 ，這個情況底下，我要找的另外一個數字也是 2 ，所以要判斷兩個情況： 1. 如果 2 Sum 是兩個一樣的數字，要檢查是否該數字已經輸入過了兩次 2. 如果不同，那就只要判斷另外一個數字是否存在就好 class
LeetCode 937. Reorder Data in Log Files 937. Reorder Data in Log Files 自定義排序 1. 如果第一個字是文字，有比較高的優先級，再以內容以字典序排列，如果內容的字典序相同，以識別碼的字典旭排序 2. 如果內容的第一的字是數字，為次之，則按照一般數字排列的方式排列。 class Solution: def reorderLogFiles(self, logs: List[str]) -> List[str]: def key(log): identifier, content = log.split(' ', 1) return (0, content, identifier) if content[0].isalpha() else (1, ) return sorted(
LeetCode 490. The Maze 490. The Maze 這一個題目可以使用廣度優先搜索來解，這一個題目的困難是在於要如何理解球的運動方向。 一般而言廣度優先搜索的探索步伐是一部，可是這個題目裡面，球會滾到撞牆為止，所以當我在座標 (row, col) 時，一樣是要往四個方向去探索，不過這個題目裡面，往四個方向探索的方式是要把球滾到撞牆為止，在去撞牆的路上，如果跨過已經走過的點的話，是可以直接跨過去的。 因此只要下個前往的座標沒有超過邊界，且不是 1 的話，球都可以一直滾。 接著要判斷的是，球滾到的位置之前有沒有到達過，如果說已經到達過了，代表這個座標曾經造訪過，但是到不了終點，我們就不會基於這個座標繼續執行廣度優先搜索 ，不過如果說剛好滾到的座標就是終點，那就是可以達到終點，題目可以回傳 True 。 反之如果題目已經探索完畢卻沒有走到終點，那就回傳 False 。 class Solution: def hasPath(self, maze: List[List[int]], start: List[int], destination: List[
