Gary Lai

986. Interval List Intersections 這一題應該算是時間區間的最後一個變形，可以想像成，有兩個人的班表，我們要找出他們哪些時間有一起上班，可能是這個時間這兩個人才可以開會，如果說這個題目問超過兩個人，其實也不會太難，就很像是 N sum 或是 Merger K Linked List 的題目一樣，兩兩的班表慢慢合併，再找出所有重複的區間就可以。 之前的題目主要是找聯集，這是我們想要找到的是時間區間的交集，所以之前的方法這裡不太可以用，另外兩個時間表也都已經排序好了，所以我們這裡也不需要考慮排序的問題，那我們要怎麼取交集呢？ 跟之前一樣，我們可以先想想有哪些交集的情況： 1. [1, 4] , [2, 6]  交集： [2, 4] 2. [1, 6], [2, 4] 交集： [2, 4] 3. [1, 3], [3,

163. Missing Ranges 雖然這一題 LeetCode 是標記簡單，但是細節上要想清楚我覺得難度應該有接近中等的等級，會把這一題我放在時間區間問題，是因為概念很類似 759. Employee Free Time ， 在那個題目裡面，我們要找出員工們的空閒時間，找的方法就是先把重疊的區間全部都先整理好，再從區間之間來找到空閒的時間。 這一題也算是時間區間的問題，不過題目給的不是區間，是一連串的時間點，這個時間點是經過排序的，另外這個題目又再加上一個額外的條件，那就是時間區先的下限與上限是另外設定的，而且這個上下限，可以與原本時間區間的上下限重疊，也可以不重疊，像是下面的例子就是上下限與題目給定的陣列都重疊，LeetCode 題目中給的例子下限有重疊，上限沒有重疊。 nums = [0,1,3,50,75] lower = 0 upper = 75 題目的回傳答案也有條件，首先就是要先了解到題目要求的區間是怎麼樣？那就是如果有區間是 [1, 3] 那要回傳的答案就是 ["2"] ，如果是 [1, 4]

253. Meeting Rooms II 這題我們要算的是，時間有重疊沒有關係，但是告訴我們至少需要幾間會議室，我們才能安排好所有的會議（面試）。 往下閱讀之前，很建議先去看 252. Meeting Rooms 。 這裡會假設已經寫過了  252. Meeting Rooms  這道題目，那我們就會知道要去看有沒有重疊，最重要的一件事情就是先將時間區間排序好，這樣就可以縮減成用一個條件來判斷時間到底有沒有重疊。 之前的題目只要判斷有沒有重疊就好，可是在這個題目如果有重疊，沒有關係，加開一個會議室就好，所以我們一次可能有很多個會議在進行，我在這裡其實馬上想歪了，覺得這個題目是不要要用遞迴或是動態規劃的方式來做？老實說我也卡住了一陣子。 在這裡也是建議先觀察題目，我的起始思考點我有點難總結，所以我盡可能的描述我的思考過程，希望能幫助到你，不過我希望我的經驗能夠幫助到你。 我開始思考的點是，如果我們現在有幾個會議之前就已經因為有重疊所以加開會議室了，我要最大化的利用資源，當我在看我的一個新的時間表的時候，我要怎麼知道我需不需要加開會議室呢？ 我在現實生活中會怎麼找？我應該會

772. Basic Calculator III 前面兩題解完，此題題目有變化，答案無變化 class Solution: def calculate(self, s: str) -> int: def helper(s): num = 0 stack = [] sign = '+' while s: c = s.popleft() if c.isdigit(): num = 10 * num + int(c) if c == '(': num = helper(s) if c in '+-*

133. Clone Graph 這一題雖然會用到 Graph 的遍歷，BFS 或是 DFS 都可以，不過真正需要理解的核心並不是遍歷，因為這個題目的遍歷並不難。 因為這個題目是一個圖，所以說要確定可以遍歷完所以的節點，又確保不會走過已經走過的路，最重要的就是要記憶過自己走過哪裡。 廣度優先搜索 """ # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution: def cloneGraph(self, node: 'Node') ->

1485. Clone Binary Tree With Random Pointer 概念和 138. Copy List with Random Pointer 一模一樣。 # Definition for Node. # class Node: # def __init__(self, val=0, left=None, right=None, random=None): # self.val = val # self.left = left # self.right = right # self.random = random class Solution: def copyRandomBinaryTree(self, root: 'Node')

2. Add Two Numbers 這一題雖然不是加一，不過很類似，所以我放在一起。 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: carry = False head = ans = ListNode() while l1 or l2: val = 0 if l1

18. 4 Sum class Solution: def twoSum(self, nums: List[int], start: int, target: int) -> List[List[int]]: left = start right = len(nums) - 1 res = [] while left < right: total = nums[left] + nums[right] leftVal = nums[left] rightVal = nums[right] if total < target: left += 1 elif total > target: right

224. Basic Calculator {% hint style="info" %} 先做 227. Basic Calculator II 和 394. Decode String{% endhint %} class Solution: def calculate(self, s: str) -> int: def helper(s): num = 0 stack = [] sign = '+' while s: c = s.popleft() if c.isdigit(): num = 10 * num + int(c) if c == '(

307. Range Sum Query - Mutable class BIT: def __init__(self, n: int): self.sums = [0] * (n + 1) def lowbit(self, i: int): return i & -i def update(self, i:int , delta: int): while i < len(self.sums): self.sums[i] += delta i += self.lowbit(i) def query(self, i:

866. Prime Palindrome 9. Palindrome Number 和 204. Count Primes 的結合。 class Solution: def isPalindrome(self, n): if n < 0 or (n % 10 == 0 and n != 0): return False left = n right = 0 while left > right: right = right * 10 + left % 10 left //= 10 return left == right or left == right //10

680. Valid Palindrome II 這一題是 125. Valid Palindrome 的變形，考的是如果說最多可以修改一個字元，那是否可以形成回文？ 在 LeetCode 很多的題目裡面，有時候修改和刪除其實是等價的（參考編輯距離的題目 72. Edit Distance） 例如： abca 我們把 b 改成 c 或是 c 改成 b 又或是把 b 刪掉或把 c 刪掉，都可以成為回文。其實有點像是容錯的概念，又換句話說就是我們乾脆跳過這個檢查點好了。 這一題我們會使用遞迴來做，會使用遞迴來做的原因是因為我們就不用花大量的精力，去判斷我們是要給右指針跳過，或是左指針跳過，在這裏，我們也可以使用一個 bool 來判斷是不是已經修改過了。 class Solution: def validPalindrome(self,

755. Pour Water 最後一個倒水問題了。 class Solution: def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]: for _ in range(volume): # start pouring left left = k for i in range(k - 1, -1, -1): # hit left wall, stop if heights[i] > heights[i + 1]: break # droplet go

167. Two Sum II - Input array is sorted 如果已經排序好了，可以直接用 2 Sum 雙指針的方法。 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left = 0 right = len(numbers) - 1 while left < right: total = numbers[left] + numbers[right] if total == target: return [left + 1, right + 1]

445. Add Two Numbers II # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head node = self.reverseList(head.next) head.next.next

42. Trapping Rain Water 要寫這一題之前，要先了解 11. Container With Most Water 的概念，這一題比較特別，題目給定的陣列像是表達一個等高線圖，其中這個等高線內就會有山谷，有山谷的地方就能儲存水，我們要求出總共能夠有多少水被儲存在這個山谷。 先了解這個題目給的所有條件，那就是如果說今天給定的等高線圖，如果只有兩個點，這樣是沒有辦法儲存任何水的，山谷能有的最多水要被包在兩側的山峰內。如果只有一邊有高峰，那水都會流走。 也就是說最少要有類似 [1, 0, 1] 這樣的情況才能有水。 接著分析比較複雜一點的情況，像是 [1, 0, 2, 1, 3] 這樣的話，在位置 0 到 2 之間，其山谷是 [1, 0, 2] ，這和之前水桶的問題一樣，最多只能儲存一單位的水，下一個儲存水的地方是 [2,

67. Add Binary class Solution: def addBinary(self, a: str, b: str) -> str: res = '' if len(a) > len(b): b = '0'*(len(a) - len(b)) + b else: a = '0'*(len(b) - len(a)) + a n = len(a) carry = False for i in reversed(range(n)): if

125. Valid Palindrome 回文的題目真的滿常讓我掛掉的，所以我想要記錄下來我怎麼克服這類型的題型的 雙指針 雙指針是一個很好想到的解法，從兩側往中間搜尋，終止條件是兩邊的指針到達中間位置了。 這裡是一個小地方要注意，那就是 while 的執行條件是要用 left < right 還是要用 left <= right ? 如果是 left < right 的話，代表的是當 left 大於或等於 right 的時候， while 就不再執行了 。這時候有兩種情況： * 第一種是字串是偶數，指針到最中間的時候，兩個指針再繼續下一步時，分別會跨中中間點，那其實就代表了左側與右側的字元都檢查完畢了 * 第二種是字串是奇數，指針到最中間的時候，兩個指針再繼續下一步時，會兩個點都剛好在中間點上面，這時候就達到了 while 的終止條件，我們會少比較了一種情況，可是這個情況並不重要，因為兩個指針指在同一個字元上面，那該字元不管如何，都一定會相等，還是會滿足回文的條件。 如果是 left

647. Palindromic Substrings 有了 5. Longest Palindromic Substring 的經驗，這一題就會好寫很多，不過這一題需要理解上一題的動態規劃法才會簡單，上一題的中心擴散法對於找最長的回文子字串非常有幫助，可是在這題卻不好用因為我們要找的是不重複的子字串 。暴力法當然可以解，可是時間複雜度不夠好。 動態規劃 有了動態規劃的概念後，這一個題目就變成我們要不斷的去找出哪兩個位置之間的子字串是回文。取得解答的方式就是每次執行完動態轉移方程式之後，如果位置 i 和 j 之間的字串是回文，就把字串 i 到 j 的子字串加入到答案裡面。最後我們就去統計有幾個。這個解法不只是解決了有幾個，更解決了有哪些子字串的組合，如果沒有要求的話，我們其實可以簡單一點，用一個計數器計算就好。 class Solution: def countSubstrings(self, s: str) -> int: l = len(s) dp = [[False for

234. Palindrome Linked List 這一題是一道簡單的題目，可是其實很容易不小心踩到雷。第一個直覺的想法會是我們就把 Linked List 反轉，接著比較一下是不是都一樣就好。可是如果我們要反轉 Linked List ，第一件要做的事情會是我們要先複製一個原先的 Linked List ，不然 Linked List 都是傳指標，反轉完原先的 Linked List 就沒了。 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def cloneLinkedList(self, head)

454. 4 Sum II 這一個題目的設計比較特別一點，給出四個長度一樣的陣列，要從四個陣列中挑出任意四個數字，其總和為零。 這個題目存在著暴力解，那就是四個陣列一個一個掃描，這樣的時間複雜度會是 $$O(n^4)$$ 如果說每個陣列的長度為 n 。 不過這一個題目如果用 n Sum 的思想來想的話，其實存在著另外一個解法，那就是如果我從前面兩個陣列，各挑出一個數字後，其總和如果是 k ，那我只要再另外兩個陣列，找出總和為 -k 的組合即可。 有一件事情要注意的是，從前面兩個陣列隨機挑選兩的個數字，其總和為 k 的情況其實有很多種，假設有 x 種，那後面兩個陣列每次找出總和為 -k 的情況，就可以組合出 x 種組合。 因此在計算答案時，要記得累加可以組合的情況。 這 樣的方式時間複雜度可以降低到只要在 $$O(n^2)

295. Find Median from Data Stream 這題如果透過排序的話，就會很好做，但是如果只是排序的話，時間複雜度是 $$O(nlogn)$$ 這題要利用的是 Heap 的特性，只要我們可以讓「最大」或是「最小」的數字始終保持在樹的最上方。 這樣的話時間複雜度可以保持在 $$O(logn)$$ import heapq class MedianFinder: def __init__(self): """ initialize your data structure here. """ self.max_heap = [] self.min_heap = [] heapq.heapify(self.max_heap) heapq.heapify(self.min_

123. Best Time to Buy and Sell Stock III Final Profit = (Initial Profit — Buying Price) + Selling Price class Solution: def maxProfit(self, prices: List[int]) -> int: firstBuy, firstSell = float('-inf'), 0 secondBuy, secondSell = float('-inf'), 0 for price in prices: firstBuy = max(firstBuy, -price) firstSell = max(firstSell, firstBuy + price)

140. Word Break II 這一題可以參考 139. Word Break 。 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: wordDictSet = set(wordDict) ans = [] def helper(s, curr): if len(s) == 0: ans.append(' '.join(curr)) return else: for word in wordDictSet: if len(word) <= len(s)

56. Merge Intervals 這題只要解過了 252. Meeting Rooms 、 253. Meeting Rooms II 就會非常的簡單。 252. Meeting Rooms 有教過了我們如何判斷區間重疊，這一個題目是我們要如何把重疊的區間都合併起來，並且給出所有的新時間區間。 這個題目還算好想一點，既然我們知道結果是一個陣列，那我們一開始就把第一個時間區間放到儲存結果的陣列，假設就只有一個時間區間，這就會是答案了。 接下來，我們就從後面的每一個時間區間來判斷，要如何得知前一個開會的時間呢？就是結果陣列的最後一個時間區間，接下來判斷是否需要合併，這個題目和前面兩個題目相比，比較特別的地方是，如果前一個時間區間的結束時間和後一個時間區間的開始區間相同時，我們是要合併的。 基本上就只有兩種情況，需要合併和不需要合併 先看如果說兩個時間不需要合併，這個比較簡單，我們就把當下的時間區間繼續放入就好。 如果說需要合併呢？這時候我們就需要重新計算新的時間區間，我們先把前一個時間區間拿出來，而新的時間區間很好計算，計算好再重新放入結果的陣列裡面。 新的時間區間