Yoru Karu Studio

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

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 字符組成

LeetCode 解題思路：104. Maximum Depth of Binary Tree（二元樹的最大深度）

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

題目描述

給定一個二元樹，返回其最大深度。

二元樹的最大深度是從根節點到最遠葉子節點的最長路徑上的節點數。

注意：葉子節點是指沒有子節點的節點。

範例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3
解釋：
    3
   / \
  9  20
    /  \
   15   7
最大深度為 3

範例 2：

輸入：root = [1,null,2]
輸出：2
解釋：
  1
   \
    2
最大深度為 2

範例 3：

輸入：root = []
輸出：0
解釋：空樹的深度為 0

限制條件：

樹中節點數的範圍是 [0, 10^4]
-100 <= Node.val <= 100

LeetCode 解題思路：94. Binary Tree Inorder Traversal（二叉樹的中序遍歷）

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

LeetCode 解題思路：Binary Tree Inorder Traversal（二叉樹的中序遍歷）題目描述給定一個二叉樹的根節點 root，返回它的中序遍歷。範例範例 1：輸入：root = [1,null,2,3] 1 \ 2 / 3 輸出：[1,3,2]範例 2：輸入：root = [] 輸出：[]範例 3：輸入：root = [1] 輸出：[1]限制條件樹中節點數目在範圍 [0, 100] 內 -100 <= Node.val <= 100 進階：遞迴演算法很簡單，你可以通過迭代演算法完成嗎？核心概念 1. 什麼是中序遍歷？中序遍歷（Inorder Traversal）的順序是：左子樹 → 根節點 → 右子樹對於二叉樹： 4 / \ 2 6 / \ / \ 1 3 5 7 中序遍歷順序：1 → 2 → 3 → 4 → 5 → 6 → 7 （注意：對於二叉搜索樹，中序遍歷會得到升序序列）2.