452. Minimum Number of Arrows to Burst Balloons 可以先看 435. Non-overlapping Intervals 的最後一個解法 這個題目是希望我們可以用最少的箭矢去射破所有氣球，如果我們算出有幾個「不重疊的區間」，就代表我們需要幾支箭矢。 有一點比較特別的地方是，在之前的時間區間問題如果前一個時間區間的結束時間和當下的時間區間開始時間區間相同時（prev[1] == prev[0]）我們是算不重疊的區間，不過在這個題目，這樣算是重疊的區間，箭矢依然可以射破兩個區間。 所以我們要找到的不重疊區間，前一個時間區間的結束時間，要完全小於現在這個區間的開始時間。 class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: points.sort(key=lambda x: (x[1], x[0]

732. My Calendar III 題目在考 253. Meeting Rooms II 。 class MyCalendarThree: def __init__(self): self.intervals = [] def minMeetingRooms(self, intervals: List[List[int]]) -> int: intervals.sort() heap = [] heapq.heappush(heap, intervals[0][1]) count = 1 for i in range(1, len(intervals)): interval = intervals[i] if interval[0] >= heap[

139. Word Break 每次檢查一個單字，看看單字有沒有符合是目標字串的前綴字元，如果說有符合的話，繼續從剩的字串檢查下去，剩餘的字串起始位置是符合的單字的長度。 遞迴 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: wordDict = set(wordDict) def helper(s): if len(s) == 0: return True for word in wordDict: if len(word) <= len(s): if s.startswith(word): if helper(s[len(

1. 2 Sum Two sum 最簡單的就是用窮舉法把所有的組合都列出來，時間複雜度為 \(O(n^2)\) ，而且一直到 n Sum 都可以使用這樣的方式來做。當然就是時間複雜度太高了。 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i,

309. Best Time to Buy and Sell Stock with Cool down class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 buys = [float('-inf')] * len(prices) sells = [0] * len(prices) for i in range(len(prices)): buys[i] = max(buys[i-1] if i > 0

4. Median of Two Sorted Arrays class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: min_heap = [] max_heap = [] def balance_heap(num): if len(min_heap) >= len(max_heap): top = heapq.heappushpop(min_heap, num) heapq.heappush(max_heap, -top) elif len(min_heap) < len(

16. 3Sum Closest

516. Longest Palindromic Subsequence 這一題和 647. Palindromic Substrings 很像，只是其中的差異是一個問的是「子字串」，一個問的是「子序列」。 子序列的排列情況會比子字串多很多，可是其實比較好想，利用回文的特性，我們要檢查的狀態就只有兩種： 1. 頭尾一樣，接著繼續檢查中間的最長回文子序列。 2. 頭尾不同，分別看先移動頭部的指標，和先移動尾部的指標，看哪邊可以拿到比較長的回文子序列。 遞迴 這樣的情況就可以寫出遞迴的關係式，其中有兩種基本狀況要處理，繼續複習回文的特性，那就是要考慮字串的長度是奇數或是偶數。 1. 如果是奇數長度的回文，最終的情況會是左右指針指向同一個位置，這時候的回文長度是 1 。 2. 如果是偶數長度的回文，最終的情況會是左右指針相鄰，位置差一，且兩個字是一模一樣的，這時候的回文長度是 2 。 class Solution: def longestPalindromeSubseq(self, s: str)

1490. Clone N-ary Tree 和 133. Clone Graph 的意義相同 DFS """ # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else [] """ class Solution: def cloneTree(self, root: 'Node') -> 'Node': table = {} def dfs(node): if not

460. LFU Cache LFU 則是另外一個快取機制，主要是讓越常被存取的資料更快地取出，並包含 LRU 的機制，如果超過限制的資源，把最少用掉的刪掉，如果最少用到的資料取出的頻率相同時，則優先刪除更早以前的資料。 所以我們至少需要知道的東西有兩件 1. 每筆資料分別的使用頻率 2. 每筆資料分別進入的順序（當遇上同樣頻率時，選擇哪個要優先刪除） 所以最少我們需要的有兩樣東西，第一個是 key_to_freq 這用來記錄每一個資料的頻率，至於順序重不重要呢？這裡只要知道每一個鍵值的頻率即可，所以順序是不重要的，所以用一般的 Hash Table 就好了。 第二個是 freq_to_keys ，這裡需要花一點時間理解，我們需要紀錄每一種頻率，各有哪幾筆資料被送進來過，如果是一個陣列的話足夠嗎？應該不足夠，舉例來說，如果我們呼叫一次 get 而要造訪的資料在中間的話，我們還需要有另一個 Hash Table 來記錄去紀錄每個位置，

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

315. Count of Smaller Numbers After Self class BinaryIndexedTree: def __init__(self, n: int): self.sums = [0] * (n + 1) def lowbit(self, x): return x & -x def update(self, i): while i < len(self.sums): self.sums[i] += 1 i += self.lowbit(i) def query(self, i): r = 0 while

227. Basic Calculator II 放進去 stack 的數字，如果都是正、負數的話，就可以直接加總，麻煩的是遇到乘、除要怎麼處理？ 因為我們需要知道乘、除後面的數字，才可以處理，但是如果是一直接連的乘、除就沒有關係，因為接連的乘、除都是符合四則運算的。 所以每當我們處理完一個數字的時候，我們要注意這個數字前面是加減號，還是乘除號？sign 就是幫助我們紀錄當下處理完的這個數字，他前面的四則運算符號是什麼，一開始預設是正號就好。 所謂的「處理完」數字還有兩種情況 1. 遇到了下一個四則運算符號 2. 走到最後一位數字 所以當處理完當下的數字後，這個數字前面的四則運算符號如果是遇上加減，直接放入到 stack 就好，遇上減號記得取負。 當處理完當下的數字之後，如果前面的數字是乘、除號，我們就要再把再前面的一個數字取出來計算完畢後，重新放回 Stack 中。 最後的答案就是加總。 class Solution: def

188. Best Time to Buy and Sell Stock IV class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) < 2 or k < 1: return 0 if k > len(prices)//2: max_profit = 0 for i in range(1, len(prices)): max_profit += max(0, prices[

1136. Parallel Courses 這個題目是修課課程 I 和 II 的進階問題，其實這個題目更像是 Course Schedule III 的題目。Course Schedule III 的題目反而不像 Course Schedule 的系列題目。 題目給定一系列的課程跟先修課程的資料，和這個題目前面的系列課程一樣，如果說沒辦法排列出來，那就回覆 -1 ，如果說可以排列出來，那就回覆可以用最少需要幾個學期修完課。 這個「最少」其實是這個題目最需要燒腦的點。我在寫 LeetCode 的時候，會希望看看能不能先從之前題目的經驗去慢慢展開題目的核心。 我們先不心急，就照搬之前的程式碼，起碼我們知道一件事情，就是給的所有的課程列表，如果有環我們就直接回傳 -1 。而且我們知道，如果要找到最後的答案，把答案找出的同時，頂多和找環的時間複雜度一樣，兩倍一樣的時間複雜度並不會真的增加我們的時間複雜度，這樣的話，不如把找環當作回答題目的一個部分，找出「最少」修課路徑是另外一個部分。

369. Plus One 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 plusOne(self, head: ListNode) -> ListNode: tmp = ListNode() tmp.next = head not_nine = tmp while head: if head.val != 9: not_nine = head

303. Range Sum Query - Immutable 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:

66. Plus One 這是加一系列的第一題，其實最好想這道題目的方法就是小學時候學的直式加法，直式加法就是從最末位開始加，並且不斷的把進位帶進去下一個位數。 在程式裡面要做直式加法，可以將題目給的陣列反過來遍歷，這個題目的問題很簡單，只有加一而已，所以我們就在最後一個位數加一。 既然我們是反著遍歷，答案會從最後一位的開始取得，題目的要求是回傳後的答案也是要用陣列來表示，所以我先不考慮取得答案的順序是不是我們要的，我只要先按照順序記錄起來就好。 在遍歷的時候，有哪些情況要考量呢？ 1. 最後一位數要加一 2. 如果前面遍歷的的運算有造成進位要加一 3. 運算完上面兩種情況，判斷下一次遍歷是否需要進位？（條件二的進位就是從這裡來的） 以上的一和二可以一起來看，因為任何一個條件滿足，要做的事情都是加一，加完一後要做的事情也都是一樣的，所以最後的程式碼如下： class Solution: def plusOne(self, digits: List[int]) -> List[int]: m = len(digits) res

1930. Unique Length-3 Palindromic Subsequences 看到回文的題目，通常都可以很直覺的想要用雙指針來做題目，可是這一個題目，我們要找的是長度為 3 的回文，我的直覺是想雙指針，可是這個方法這邊我一開始就有點卡住。不知道該怎麼做，是要靠動態規劃嗎？還是遞迴的方式去檢查？ 我就先想了遞迴的方式，我先固定最左邊，去看最右邊是不是跟最左邊一樣，如果不一樣我就往內縮，那如果一樣呢？這樣看起來我不需要遞迴下去，可是在最左邊與最右邊中間可能還有很長的字串，我要怎麼處理？ 在這裡我又再卡住了一次，到了這裡我才發現，不對，題目給的條件其實是在幫助我們，因為我們要找的回文長度只要 3 ，所以如果說一個字串的左邊和右邊都確定了，那我只要知道中間有幾種不同的組合。 例如下面的字串，當我們確定最左最右都是 a 的時候，中間還有四個字串，但是是其實只是 b, a, c 三個的排列組合。 abbaca 1. aba 2. aaa 3. aca 觀察到這個組合後，

9. Palindrome Number 此題最簡單的解法會是把數字直接轉成字串，再透過字串處理，要注意的是如果是負數，直接不可能是回文，因為負號會直接影響回文的條件，一開始就可以剔除。 class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False s = str(x) left = 0 right = len(s) - 1 while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True

57. Insert Interval 這題的解法很簡單，直接把新的區間加入進去，重新使用 56. 題的解法。 class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: intervals.append(newInterval) intervals.sort() stack = [intervals[0]] for i in range(1, len(intervals)): prevInterval = stack.pop() newInterval = intervals[i] if prevInterval[1] >= newInterval[0]

122. Best Time to Buy and Sell Stock II 這個題目是每天都可以買賣股票，但是最多只能同時持有一股的股票要買之前要先賣掉股票。 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 buys = [float('-inf')] * len(prices) sells = [0] * len(prices) buys[0] = -prices[0] for i in range(1, len(prices)): buys[i] = max(

729. My Calendar I 插入時間的結束時間比當前時間的開始時間小，且插入時間的開始時間比當前的結束時間小 -> 發生重疊。 class MyCalendar(object): def __init__(self): self.calendar = [] def book(self, start, end): for s, e in self.calendar: if s < end and start < e: return False self.calendar.append((start, end)) return True # Your MyCalendar object will be instantiated and called

714. Best Time to Buy and Sell Stock with Transaction Fee class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: if len(prices) < 2: return 0 buys = [float('-inf')] * len(prices) sells = [0] * len(prices) for i in range(len(prices)): if i == 0: buys[i] = max(

673. Number of Longest Increasing Subsequence Prerequisite {% page-ref page="longest-increasing-subsequence.md" %} 核心和 300. Longest Increasing Subsequence 一樣，不過除了要記錄的是當前的最長上升子序列的長度外，要外去記憶有多少種路徑可以到，可以用 tuple 記錄（當前最長上升子序列的長度，前面有幾種路徑） 。 一開始的初始值都是 1 ，是因為如果當下的最長上升子序列就是只有自己，那只有一種方式可以到達，像是題目中給的範例 [2, 2, 2, 2, 2] 的答案是 5 一樣。 計算出當前最長子序列的長度為合並不困難，和 300. Longest Increasing Subsequence 一樣。 這裡要注意的是要去計算出前面有多少個路徑可以到達我當前的位置，要是合法的路徑的話，必須滿足兩個條件： 1. 前方位置的數值，要比我現在的數值來的小，