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

1 題目描述 給定一個二元樹，然後每個節點有一個 next 指針，將它指向它右邊的節點。如果沒有右邊的節點，則設為 None。 題目有特殊要求，不能使用額外的空間，也就是說不能使用 Queue 來解這題。 2 解法 我們先走簡單路線，你會發現基本上就是把同一層的節點串起來，然後再串下一層的節點。因此我們可以使用BFS的方式來解這題。講到BFS的演算法，可以參考這篇LeetCode 課前預習 - 掌握 BFS 與 DFS 指南。 2.1 Queue 我們可以知道在Iterative的方式下，先不考慮題目限制，我們可以使用Queue來解這題。 BFS的演算法 123456789101112131415161718192021def bfs_traversal(root): def bfs(nodes): # 如果沒有節點，就直接返回 if not nodes: return next_level = [] # 裝下一層的每個節點 result = [] # 裝目前這層的節點值 ...

BFS vs DFS 二元樹走訪或稱二元樹遍歷，簡單來說就是走訪樹中各節點，轉化為線性關係。 主要分成兩種策略方式 深度優先搜尋（Depth-first Search，DFS）:從根節點出發，選擇某一子樹並以垂直方向由上到下處理，將其子節點訪問完後，再選擇另一子樹走訪。 廣度優先搜尋（Breadth-first Search，BFS）:從根節點出發，以水平方向由左到右走訪，將同階層的兄弟節點訪問完之後，再走訪下一階層的節點。 深度優先搜尋 DFS 假設根結點為N、左子樹為L、右子樹為R 前序走訪(Pre-order Traversal): NLR, 根節點 → 左子樹 → 右子樹 中序走訪(In-order Traversal): LNR, 左子樹 → 根節點 → 右子樹 後序走訪(Post-order Traversal): LRN, 左子樹 → 右子樹 → 根節點 簡單來說 都是先左子樹，再右子樹 preorder: root 在前面 inorder: root 在中間（裡面） postorder: root 在後面 preorder的實作 前序走訪： 順序是根節點 ...

1 題目描述 要把左右子樹對調，outside替換，inside也是替換。 2 解法 大問題：要把一個樹的左右子樹對調 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹對調。 最小的問題：當 root 是 None 時，回傳 None。 假設就是我們呼叫 invertTree(root.left) 與 invertTree(root.right) 會回傳對調後的左右子樹，我們只要把左右子樹對調就可以了。 1234567class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return None root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root 3 總結 大概花了20分，這題不難，但是我 ...

1 題目描述 檢查兩棵樹是否相同 2 解法 這題跟101-Symmetric Tree的解法很像，所以很簡單： 一樣套用 Recursion 的思維，我們先將大問題變成小問題 大問題：知道兩個樹是否相同 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹是對稱的。 大小關係式：(p.val == q.val) and (p.left, q.left) and (p.right, q.left) 當前的值相同 and 左子樹相同 and 右子樹相同 最小的問題：當 p 和 q 都觸底的時候，是如果都是None就代表True，但是當其中一邊有值，另一邊沒有值，就不相同了。 1234def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if not p or not q: return False return p.val == q.val and self.isSameTre ...

1 題目描述 提供給你 preorder 與 inorder 的數列，請你建立一個二元樹。首先 讓我們先了解 preorder 與 inorder 的定義。 Inorder Traversal -> LEFT -> ROOT ->RIGHT PreOrder Traversal -> ROOT -> LEFT -> RIGHT 2 解法 你會發現，preorder 第一筆會是 Root，後面會先遍歷left sub-tree整顆跑完，才會再遍歷right sub-tree。而 inorder 是先遍歷left sub-tree，再遍歷root，最後是right sub-tree。你會發現 preorder 跟 inorder 的優缺點如下： preorder: 好處：因為第一個值是root，所以可以直接取得root的值 缺點：無法知道左右子樹的範圍 inorder: 好處：可以知道左右子樹的範圍 缺點：無法知道root的值 因此我們要利用彼此雙方的好處，互補彼此的缺點。這時候我們就可以利用遞迴的方式來建立二元樹。 2.1 取su ...

1 題目描述 檢查是否對稱。 Follow up: Could you solve it both recursively and iteratively? 2 解法 2.1 Recursioin 一樣套用Recursion的思維，我們先將大問題變成小問題 大問題：知道一個樹是否對稱 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹是否對稱。 大小關係式：(left.val == right.val) and (left.left, right.right) and (left.right, right.left) 當前的值 and 外面對稱 and 裡面對稱 最小的問題：當 left 和 right 都觸底的時候，是對稱的，但是當其中一邊有值，另一邊沒有值，就不對稱了。 我們可以定義一個遞歸函數，它將兩個節點作為輸入，一個來自左子樹，一個來自右子樹。如果兩個節點都為 null，或者它們的值相等且子樹對稱，則輔助函數傳回 true。 大概是這樣的感覺： 1234567891011121314151617class Solution: def i ...

1 題目描述 計算Binary Tree的最大深度。 2 解法 我們先將大問題變成小問題 大問題：知道一個樹的最大深度 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹的最大深度。 大小問題的關係：因此，為了找到這個二元樹的最大深度，我們必須取出遞歸給我們的 2 個深度中的最大值，然後加 1 以將當前級別（即根的級別）考慮到我們的深度中。 最小的問題是，當 root 是 None 時，我們的深度為 0。 大小問題關係式：max(左子樹深度, 右子樹深度) + 1(root) 寫成python大概會長這樣 1234def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 還有另一種思維，那就是最小的問題就是當 root 有值，但是就一個節點，沒有 right 與 left，這時候我們的深度就是 1 ...

前言 會想要寫這篇是因為在碰到binary tree的時候會大量的使用recursion，因此想先瞭解Recursion的核心思維，希望能讓自己將遞迴的概念內化，讓他從此不再高不可攀。那我們就開始吧！首先，來聊聊基礎遞迴常見的思維方式之一， 先將一個大問題，拆解成幾個較小的問題 如果發現這些較小的問題當中，也能依照相同的方式拆解成更小的問題 每當小問題解決時，大問題也可以依靠小問題的結果來解決 從大問題到小問題，每層的解決方法都是一樣的，除了最小問題以外 根據以上幾點，我可以不段套用相同的函數，讓他自己幫自己解決問題 以上就是遞迴的基本核心精神，如何分析看不懂沒關係，我們先來看個最基本的例子 實戰範例 從 1 加到 n 如果使用迴圈的方式 12345def sum(n): result = 0 for i in range(1, n+1): result += i return result 我們的思考方式如下： 大問題：從1加到n 小一點的問題：從1加到n-1 那我們只要先處理好小問題，最後再把其答案加上n就好了 12def sum_1_to_ ...

Transformers 相關的庫 Transformers 核心庫: 模型加載 模型訓練 Tokenizer 分詞器: 對數據進行預處理，將文本轉換成模型可以理解的格式(Token序列) Datasets 數據集庫: 下載公開的數據集，並且進行預處理 Evaluate 評估函示: 像是準確率 F1, BLEU, ROUGE 等等 PEFT 高校微調方法: 只訓練一小部分參數，而不是全部重新訓練，提供常用的微調方法 Accelerate 分布式訓練: 對訓練過程進行加速，提供了分布式訓練的方法 Optimum 優化加速庫: 提供了一些優化方法，比如混合精度訓練，對訓練過程進行加速 Gradio 可視化庫: 提供了一些可視化的方法，透過幾行程式達到快速外部交互的效果 前置環境 需要安裝以下套件： python conda pytorch 以我的狀況為例，我是cuda支援的版本是12.4，這代表小於12.4的版本都可以支援cuda，建議使用pip進行安裝 30xx 或是 40xx 顯卡要安裝 cu11 以上的版本 最後測試是否安裝成功 12345C:\Users\Name> ...

簡介 相信各位在準備面試的時候，Binary Search Tree 這個資料結構一定會被問到，他是 Tree 大本營中最先學到的一種演算法，在資料的搜尋、插入、刪除上都有很好的表現，在Balanace Tree的狀況下可以達到O(logn)，所謂的Balanace Tree就像是左邊跟右邊的枝葉數量差不多，不會出現左邊很多右邊很少的情況，這樣才能達到O(logn)的時間複雜度。 定義 那我們先來說說BST的四個特性： 根(root)的左邊節點(left node)其子樹(sub-tree)中所有的節點值都小於根(root)的值。 根(root)的右邊節點(right node)其子樹(sub-tree)中所有的節點值都大於根(root)的值。 任意節點的左右子樹都符合BST。 不存在任何key/value相等的節點。 小提醒：我把第四點畫起來是因為很多人會不記得第四點，但遇過面試有問，但想一下就會知道如果有相等值的節點就會違反第一點或第二點。 如果我還是想要塞入相同的值怎麼辦？ BST的變體如果硬要塞相同的值，有一些變體可以處理重複的值，這些變體包括 左傾或右傾策略 (Le ...