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

前言 會想要寫這篇是因為在碰到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 ...

1 題目描述 合併兩個有序的鍊錶，並且返回一個新的鍊錶。新的鍊錶是由兩個鍊錶的節點組成的。 2 解法 跟 leetcode-2-add-two-numbers 很類似，因為它涉及到多個 listNode 的操作，並且將操作結果合併為一個，因此我們可以使用 dummy_head 來幫助我們串接結果。因為他是排序，所以要比較兩個數字的大小，但是我們最怕的是在取listNode的值時發現他是None而導致錯誤，因為題目說數字範圍是[0, 50] 因此我們取 100 當作最大值，因此我們可以使用 digit1 = list1.val if list1 else 100 的方式，儘管遇到 none 仍然可以繼續執行迴圈，直到兩個 list1 跟 list2 都觸底，以避免 None 的問題。 1234567891011121314151617181920212223242526272829class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextcl ...

1 題目描述 這題就是兩個鍊錶表示的數相加，這樣就可以實現兩個很大的數相加了，關鍵要能無需考慮數值 int ，float 的限制了。但是如果你把 ListNode 直接串啟程字串並且轉換成數字，這你就大錯特錯了！因為這樣就失去了這題的意義了。 2 解法 2.1 我的解法 我一開始沒意識到，這題的 ListNode 是倒序的，所以我一開始的想法是把兩個 ListNode 轉換成數字，然後相加，再轉換成 ListNode。但是這樣就失去了這題的意義了。因為有一個test case是超級長的[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]直接突破了int的限制。 所以我的解法無法通過這個 test case。建議參考下一個方法 12345678910111213141516171819202122232425262728293031class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) ...

1 題目描述 判斷一個 linked list 是否有 cycle，如果有就返回 True，沒有就返回 False。 特殊要求空間複雜度為 O(1)。 2 解法 2.1 我的解法 一開始我的想法很簡單，但是空間複雜度為 O(n)。就是把每個節點都放進一個 set 裡面，如果有重複的節點就返回 True，否則返回 False。但是這個不滿足要求空間複雜度為 O(1)。 123456789class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: check_dict = {} while head: check_dict.__setitem__(head, head.val) head = head.next if check_dict.get(head): return True return False 2.2 龜兔演算法 這個方 ...