Yoru Karu Studio
程式設計學習筆記 | LeetCode 解題分享程式設計學習筆記 | LeetCode 解題分享
LeetCode 21: Merge Two Sorted Lists 詳細解析
題目描述 給定兩個已排序的鏈結串列 list1 和 list2 的頭節點。
將這兩個串列合併成一個已排序的串列。合併後的串列應該透過拼接前兩個串列的節點來建立。
返回合併後鏈結串列的頭節點。
範例 範例 1：
輸入：list1 = [1,2,4], list2 = [1,3,4] 輸出：[1,1,2,3,4,4]範例 2：
輸入：list1 = [], list2 = [] 輸出：[]範例 3：
輸入：list1 = [], list2 = [0] 輸出：[0]限制條件 兩個串列的節點數量範圍為 [0, 50] -100 <= Node.val <= 100 list1 和 list2 都按照非遞減順序排列 解題思路 這道題目要求我們合併兩個已排序的鏈結串列。主要有兩種解法：
方法一：迭代法 使用雙指標的概念，逐一比較兩個串列的當前節點，將較小的節點加入結果串列。
核心概念：
建立一個虛擬頭節點（dummy node）來簡化邊界條件處理 使用一個指標追蹤結果串列的當前位置 比較兩個串列的當前節點，選擇較小的加入結果 處理剩餘的節點 方法二：遞迴法 利用遞迴的特性，每次選擇較小的節點，然後遞迴處理剩餘部分。
核心概念：
基本情況：如果其中一個串列為空，返回另一個串列 比較兩個串列的頭節點 選擇較小的節點，並遞迴處理剩餘部分 程式碼實現 方法一：迭代法 # Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.
Linked List（鏈結串列）完整指南
Linked List（鏈結串列）完整教學 什麼是 Linked List？ Linked List（鏈結串列）是一種線性的資料結構，其中的元素不是儲存在連續的記憶體位置，而是透過指標（pointer）相互連接。每個元素稱為節點（Node），包含兩個部分：
資料（Data）：儲存實際的值 指標（Next）：指向下一個節點的參考 視覺化表示 [Data|Next] -> [Data|Next] -> [Data|Next] -> None ↑ ↑ ↑ Node 1 Node 2 Node 3為什麼需要 Linked List？ 與 Python List（Array）的比較 # Python List（動態陣列） python_list = [1, 2, 3, 4, 5] # 記憶體中連續存放：[1][2][3][4][5] # Linked List # 記憶體中分散存放： # [1|→] -----> [2|→] -----> [3|→] -----> [4|→] -----> [5|None]優缺點比較 操作 Python List Linked List 訪問第 i 個元素 O(1) O(n) 在開頭插入 O(n) O(1) 在結尾插入 O(1)* O(n) 在中間插入 O(n) O(1)** 刪除元素 O(n) O(1)** 記憶體使用 連續 分散 * 平均情況，可能需要擴容 ** 如果已經有該位置的參考
演算法詳解：BFS 與 DFS（廣度優先搜尋與深度優先搜尋）
LeetCode 解題思路：20. Valid Parentheses（有效的括號）
題目描述 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s，判斷字串是否有效。
有效字串需滿足：
左括號必須用相同類型的右括號閉合 左括號必須以正確的順序閉合 每個右括號都有一個對應的相同類型的左括號 範例 範例 1：
輸入：s = "()" 輸出：true範例 2：
輸入：s = "()[]{}" 輸出：true範例 3：
輸入：s = "(]" 輸出：false範例 4：
輸入：s = "([)]" 輸出：false 解釋：雖然有對應的括號，但順序不正確範例 5：
輸入：s = "{[]}" 輸出：true限制條件 1 <= s.length <= 10⁴ s 僅由括號 '()[]{}' 組成 核心概念：為什麼要用堆疊？ 括號匹配的本質 觀察有效的括號序列，你會發現一個規律：最後出現的左括號，必須最先被匹配。
範例：{[()]} ↓ 遇到 { → 需要找 } 遇到 [ → 需要找 ]（但要先處理） 遇到 ( → 需要找 )（但要先處理） 遇到 ) → 匹配最近的 ( 遇到 ] → 匹配最近的 [ 遇到 } → 匹配最近的 {這正是**後進先出（LIFO）**的特性，而堆疊就是為此而生！
LeetCode 解題思路：13. Roman to Integer（羅馬數字轉整數）
題目描述
羅馬數字包含以下七種字符：I、V、X、L、C、D 和 M。
字符 數值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如，羅馬數字 2 寫做 II，即為兩個並列的 1。12 寫做 XII，即為 X + II。27 寫做 XXVII，即為 XX + V + II。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：
I可以放在V(5) 和X(10) 的左邊，來表示 4 和 9X可以放在L(50) 和C(100) 的左邊，來表示 40 和 90C可以放在D(500) 和M(1000) 的左邊，來表示 400 和 900
給定一個羅馬數字，將其轉換成整數。
範例 1：
輸入：s = "III"
輸出：3
解釋：III = 3範例 2：
輸入：s = "LVIII"
輸出：58
解釋：L = 50, V = 5, III = 3範例 3：
輸入：s = "MCMXCIV"
輸出：1994
解釋：M = 1000, CM = 900, XC = 90, IV = 4