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

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 ...

1 題目描述 簡單來說，在有序的listNode中，移除鍊錶中重複的元素，只留下沒有重複的元素。 2 解法 首先要注意的是，題目提到的是有序的鍊錶，這樣就可以很簡單的使用pointer解決這個問題。 一開始我的解法很蠢，我自己都不太想放上來了…我用三個指標，這導致我花了30分鐘才寫完，不僅僅很攏長可讀性還不高。後來我看到有人的解答是用雙指針，這樣就簡單多了。大概重新用雙指針思考一次題目，7分鐘就寫完了。 首先我們會需要兩個指針： pre 用來記錄重複的前一個元素，這樣才可以把 pre.next 接到沒有重複的元素上 cur 跟 cur.next 這兩個會不斷的比較，如果相鄰的兩個元素val相同 pre 保持原地不動 (while loop) cur 要一直往下走直到 cur.val 跟 cur.next.val 不相同 如果發現 pre.next 與 cur 不同時，就要重新接到最新的 cur 上 大概是這種感覺 12345678910111213141516171819def deleteDuplicates(self, head: Optional[ListNode] ...

1 題目描述 簡單來說，就是給定一個 linked list 和一個數字 n，要求刪除倒數第 n 個節點，並返回新的 linked list。 2 解法 2.1 我的解法 一開始想到的做法: 把所有位置的訊息存在一個 dict 裡面 然後因為已經遍歷過一次知道整個長度，直接尋找到要刪除的節點的前一個進行刪除。 1234567891011121314151617181920212223242526def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: if head.next is None: return None node_dict = {} cur = head index = 0 while cur: index += 1 node_dict.__setitem__(index, cur) cur = cur.next pre_idx = inde ...

1 題目描述 簡單來說，就是在指定的位置 m 到 n 之間，將鍊錶進行反轉。 注意的是，題目要 one pass 是指只能遍歷一次鍊錶，不能多次遍歷。 2 解法 2.1 我的解法 我的想法很簡單 先建立一個字典，紀錄 key = index, value = node 你會發現 left 到 right 之間的反轉，從 left 開始，left 應該改成 right 的值，right 應該改成 left 的值，直到 left 跟 right 相遇。 何時該停呢？當 left >= 原本的 right 時，就停止。 大概是這種感覺 1234567891011121314151617181920212223242526272829303132333435363738class Solution: def reverseBetween( self, head: Optional[ListNode], left: int, right: int) -> Optional[List ...

1 題目描述 簡單來說，就是要你複製出一個一樣的ListNode結構，而這個ListNode有一個random的參數，這個random參數是指向ListNode中的任意一個節點，這個節點可以是自己，也可以是其他節點。 2 解法 2.0 創建鍊錶 在開始前，我們總是得想辦法先做個測試資料吧…輸入是一個二維陣列，每個元素是一個list，第一個元素是值，第二個元素是random的index，如果是None就是None。 input: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]] output: ListNode 鍊錶 1234567891011121314151617181920212223242526272829303132333435363738def createLinkedList(nums: List[List[int]]) -> ListNode: if not nums: return None random_dict = {} # 存 node, random_in ...