Shannon's Blog 🐟 技術 | 生活 | 旅行

1 題目描述 這題簡單來說就是給定一個字串s和一個字典wordDict，判斷s是否可以被空格分割成一個或多個在字典中出現的單詞。 2 解法 2.1 我的作法 但是這個為什麼說他是一個dp問題，是因為他就像背包問題一樣，s是背包，wordDict是物品，我們要看看s能不能裝下wordDict裡面的物品。如果裝錯物品可能導致裝不下。 我的想法一開始是一個用切割的方式切成兩塊，然後把所有可能的組合都存到字典裡面，最後找到可以把目前切割結果組合成s的組合。 切割成兩塊 例如：applepenapple a + pplepenapple ap + plepenapple app + lepenapple … 123for i in range(1, n): check_w = word[0:i] rest_w = word[i:n] 如果找到一組，切成兩塊的結果都是True就找到了 假設helper是一個可以判斷是否可以切割成wordDict的函數 關係式：helper(word[0:i]) and helper(word[i:n]) 12345for i in ran ...

1 題目描述 有一排房子，每個房子裡面有一定的錢，但是不能連續偷兩個房子，否則會報警，在不觸發報警的狀況下求最多可以偷到多少錢。 2 解法 按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是： Step1: Recursive Step2: Recursive with Memoization Step3: Iterative + Tabulation Step4: Iterative with Constant Space Step1: Recursive 一道很典型的通過子問題去解決原問題的題目，所以可以透過遞歸以及動態規劃解決。 假設：知道了前 n - 1 家店最多能偷的錢數，前 n - 2 家店最多能偷的錢數。 關係式：如果我們想要知道前 n 家商店最多能偷多少錢，我們可以選擇偷 偷：偷第 n 家商店 + 前 n - 2 家商店最多能偷的錢數。 不偷：不偷第 n 家商店 + 前 n - 1 家商店最多能偷的錢數。 最小問題：如果今天 n = 0，那麼就是0，如果n = 1 ...

1 題目描述 爬樓梯，每次可以爬一階或是兩階，求爬到第n階有幾種方法。 2 解法 按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是： Step1: Recursive Step2: Recursive with Memoization Step3: Iterative + Tabulation Step4: Iterative with Constant Space Step1: Recursive 最基本也是最蠢的就是我們要先發現，基本上走樓梯的方法數量是f(n) = f(n-1) + f(n-2)，這樣的遞迴式，我們可以直接寫出來。 123456def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2) Step2: Recursive with Memoization 那我們就思考，是不 ...

前言 我希望可以熟悉DP的思維，剛好看到這篇Medium | Ultimate Guide to Dynamic Programming獲得蠻多的讚，所以打算這篇為基礎做筆記。 在解決Dynamic Programming重要的前提是： 耐心: DP問題通常需要花時間來思考，不要急著寫程式 熟悉遞迴: DP問題通常可以用遞迴的方式來解決，因此熟悉遞迴是很重要的 Recursion遞迴跟DP的不同 遞歸和動態規劃的主要關聯在於： 重疊子問題：如果一個遞歸算法在計算過程中重複解決相同的子問題，可以使用動態規劃來優化。這時，遞歸算法可以轉化為帶備忘錄的遞歸（自頂向下的動態規劃）。 最優子結構：如果一個問題的最優解可以由其子問題的最優解構成，那麼可以使用動態規劃來解決這個問題。 有一個很簡單的例子，使用Fibonacci數列來說明這兩個概念。 Fibonacci數列的遞歸解法123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) ...

1 題目描述 2 解法 我的問題是在，我一開始以為，只要把上一個節點，傳下去，跟下一層的節點進行比較就好了。但是我錯了！ 我一開始腦子想著 你會發現上圖根本不是正確的二元搜尋樹，因為節點3比root小，不應該出現在右子樹中…所以我就卡住了。 2.2 使用Recursion 其實這題真的目的在於，在 左子樹，只要一往右走，就要考慮到根節點的值，不能大於root.val。而在右子樹，只要一往右走，就要考慮到根節點的值，不能小於root.val。我想了好久，都沒想到到底要怎麼樣知道走不同子樹的路線時（在左子樹還是在右子樹），還能知道當前到底走在哪個方向（一往右走，還是一往左走）…直到我試著畫出每個節點的上下限。 你會發現，根本不需要顧慮左還是右子樹，你會發現： 只要是往左走，max一定會更新成parent.val，而min則是繼承自上一層的min。 只要是往右走，min一定會更新成parent.val，而max則是繼承自上一層的max。 然後神奇的事情發生了: 因為在左子樹往右走時，max會一路繼承上一層的max，追溯到源頭就是root! 也就是說，我們在左子樹往右走時，m ...

1 題目描述 在二元搜尋樹中，找到第 k 小的節點值。 2 解法 看到二元搜尋樹就要知道，中序遍歷的結果就是一個排序好的陣列。因此我們可以透過中序遍歷的方式，來找到第 k 小的節點值。也就是先 left - root - right 的方式遍歷，當我們遍歷到第 k 個節點時，就可以回傳。大概可以這樣思考： 我們先走到底，也就是一直往左走，直到走到最左邊的節點。 當觸底的時候，我們開始計數，每次遍歷到一個節點，就把 count+1。 當 count 與 k 相等時，就回傳當前節點的值。 否則，遍歷右邊的節點。 那我們開始來一步步拆解這個問題吧！ Step 1 我們先走到底 123456def inorder(root): # 如果沒有節點了，就停止 if not root: return # 先走到底 inorder(root.left) Step 2 當觸底的時候，我們開始計數 1234567def inorder(root): if not root: return inorder(root.left) # ...

1 題目描述 給定一個二元樹，返回其節點值的之字形層序遍歷。換句話說，從左到右，逐層遍歷所有節點，然後每一層的節點值交替方向。 第 1 層從左到右，第 2 層從右到左，第 3 層從左到右，第 4 層從右到左，交替進行。 2 解法 2.1 我的解法 仔細看會發現一個規律，就是當我們在做層序遍歷的時候，我們可以透過BFS的方式，在不同的層，當發現是偶數層時，要從左到右，我們可以stack先塞right再left。而在奇數層時，要從右到左，我們可以stack先塞left再right。 123456789101112# 透過pop的方式取出最晚進去的節點node = nodes.pop()# 紀錄當前的層cur_level.append(node.val)# 如果是偶數層 Left到Right，因此我們先塞Right再Left，按照後進先出的方式達到 Left -> Right if level % 2 == 1: if node.right: next_level.append(node.right) if node.left: next_level.append(n ...

1 題目描述 假如你站在樹的右邊，看著樹，你會看到樹的右邊的節點。紀錄下來這些節點。 2 解法 一開始我看到這題的時候，腦子浮現的是，我就是努力的往右邊走，如果右邊沒辦法走了，就往左邊走，這樣就可以記錄下來右邊的節點了。但是我的想法無法解決以下這個情境： 12345 1 / \2 3 \ 5 以下的程式碼是錯誤的，他只會記錄到right subtree的最右邊，但是left subtree也就是 2 跟 5 節點不會被尋訪。 1234567891011121314class Solution: res = [] def rightSideView(self, root: TreeNode) -> List[int]: if root is None: return [] if root: self.res.append(root.val) # 如果右邊有節點，就往右邊走 if root.right: self.rightSideVie ...

1 題目描述 給一個二元樹，找到兩個節點的最低共同祖先。（祖先可以是自己） 2 解法 2.1 我的解法 看到這題的時候我腦子裡面出現兩種情況： 如果兩個節點在同一個子樹下（p是q的子節點或是q是p的子節點），那祖先會是p或是q。 如果兩個節點在不同的子樹下（p和q分別在左右子樹下），那祖先會是把他們倆分開時的root。 情境1: p 是 q 的祖先 或是 q 是 p 的祖先 情境2: p 和 q 在不同的子樹下 因此我們可以針對這兩種情況來寫遞歸。 情境1 我們可以建立一個function檢查兩個點是否在同一個子樹下，如果是的話，回傳p或是q。 123456def check_same_subtree(parent, child): if parent is None: return False if parent == child: return True return check_same_subtree(parent.left, child) or check_same_subtree(parent.right, ...

1 題目描述 給定一個二元樹，返回其節點值的層序遍歷。換句話說，從左到右，逐層遍歷所有節點。 2 解法 這題很明顯，我們可以使用BFS的方式來解，因為BFS是一種逐層遍歷的方式。 我們會需要 next_level 來存放下一層的節點，然後透過呼叫自己，放入next_level的節點。 nodes 是當層的所有節點。 values 是用來存放當層的節點值。 result 就是結果。 Recursive 12345678910111213141516171819class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: def bfs_helper(nodes): if not nodes: return next_level, values = [], [] for node in nodes: values.append( ...