Yoru Karu Studio

程式設計學習筆記 | 生活心得

Linked List（鏈結串列）完整指南

luk 發佈於 2024-12-21 收錄於 Data-Structures

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（廣度優先搜尋與深度優先搜尋）

luk 發佈於 2024-12-20 收錄於 Algorithm

前言

BFS（Breadth-First Search，廣度優先搜尋）和 DFS（Depth-First Search，深度優先搜尋）是圖論和樹結構中最基礎也最重要的兩個演算法。幾乎所有的圖和樹相關問題都會用到這兩種遍歷方式。

本文將從基礎概念開始，逐步深入到實際應用，幫助你徹底掌握這兩個演算法。

LeetCode 解題思路：20. Valid Parentheses（有效的括號）

luk 發佈於 2024-12-20 收錄於 Leetcode

題目描述給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 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（羅馬數字轉整數）

luk 發佈於 2024-12-13 收錄於 Leetcode

題目描述

羅馬數字包含以下七種字符：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 和 9
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90
C 可以放在 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

LeetCode 解題思路：9. Merge Two Sorted Lists（合併兩個有序鏈表）

luk 發佈於 2024-12-09 收錄於 Leetcode

題目描述給定兩個已排序的鏈結串列 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 都按照非遞減順序排列核心概念：什麼是 head？在深入解法之前，先理解一個重要概念：head（頭節點）。鏈結串列結構： head -> [1] -> [2] -> [3] -> [4] -> null ↑ 這個就是 head（頭節點）為什麼 head 很重要？存取整個串列的唯一入口：在鏈結串列中，我們只能透過 head 來存取整個串列代表整個串列：當題目說「返回合併後鏈結串列的頭節點」，就是要返回新串列的第一個節點解法一：迭代法（使用虛擬頭節點）什麼是 dummy node（虛擬頭節點）？ dummy node 是一個輔助節點，它的值不重要（通常設為 0），主要目的是簡化鏈結串列操作的邊界條件。

LeetCode 解題思路：125. Valid Palindrome（有效回文）

luk 發佈於 2024-12-07 收錄於 Leetcode

題目描述

如果在將所有大寫字符轉換為小寫字符、並移除所有非字母數字字符之後，短語正著讀和反著讀都一樣，則可以認為該短語是一個回文串。

字母和數字都屬於字母數字字符。

給定一個字串 s，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫。

範例 1：

輸入：s = "A man, a plan, a canal: Panama"
輸出：true
解釋："amanaplanacanalpanama" 是回文串

範例 2：

輸入：s = "race a car"
輸出：false
解釋："raceacar" 不是回文串

範例 3：

輸入：s = " "
輸出：true
解釋：在移除非字母數字字符之後，s 是一個空字串 ""
由於空字串正著反著讀都一樣，所以是回文串

限制條件：

1 <= s.length <= 2 * 10^5
字串 s 由 ASCII 字符組成