更新時間：2025-03-29

• LeetCode題解專欄：實戰算法解題 (專欄)
• 技術博客總目錄：計算機技術系列目錄頁

優先整理熱門100及面試150，不定期持續更新，歡迎關注！

---

17. 電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數字到字母的映射如下，與電話按鍵相同。注意 1 不對應任何字母。

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范圍 ['2', '9'] 的一個數字

---

方法一：回溯法

通過遞歸生成所有可能的字母組合，每次遞歸選擇一個字母加入當前路徑，處理下一個數字。

代碼實現(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtrack(result, new StringBuilder(), digits, 0, mapping);return result;}private void backtrack(List<String> result, StringBuilder current, String digits, int index, String[] mapping) {if (index == digits.length()) {result.add(current.toString());return;}char digit = digits.charAt(index);String letters = mapping[digit - '2']; // 根據數字獲取對應字母集合for (char c : letters.toCharArray()) {current.append(c);                // 添加當前字母backtrack(result, current, digits, index + 1, mapping); // 遞歸處理下一個數字current.deleteCharAt(current.length() - 1); // 回溯，刪除最后添加的字母}}
}

復雜度分析:

• 時間復雜度： O(3^m*4^n)，其中 m 是輸入中對應 3 個字母的數字個數，n 是 4 個字母的數字個數。
• 空間復雜度： O(k)，k 為結果數量，遞歸棧深度最大為輸入長度。

---

方法二：迭代法（隊列）

通過逐步擴展現有組合生成所有可能結果，利用隊列管理中間過程。

代碼實現(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};Queue<String> queue = new LinkedList<>();queue.offer(""); // 初始空字符串for (int i = 0; i < digits.length(); i++) {char digit = digits.charAt(i);String letters = mapping[digit - '2'];int size = queue.size();for (int j = 0; j < size; j++) {String s = queue.poll();for (char c : letters.toCharArray()) {queue.offer(s + c); // 生成新組合并入隊}}}result.addAll(queue);return result;}
}

復雜度分析:

• 時間復雜度： O(3^m*4^n)，每個數字的處理需要遍歷當前隊列中所有元素。
• 空間復雜度： O(3^m*4^n)，隊列存儲所有中間組合。

---

方法三：迭代法（逐步構造）

直接通過遍歷每個數字并擴展現有結果，生成所有組合。

代碼實現(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};result.add(""); // 初始空字符串for (char digit : digits.toCharArray()) {List<String> temp = new ArrayList<>();String letters = mapping[digit - '2'];for (String s : result) {for (char c : letters.toCharArray()) {temp.add(s + c); // 將當前字母與現有字符串拼接}}result = temp; // 更新結果}return result;}
}

復雜度分析:

• 時間復雜度： O(3^m*4^n)，每次迭代生成新的組合。
• 空間復雜度： O(3^m*4^n)，存儲所有中間結果。

---

19. 刪除鏈表的倒數第 N 個結點

給你一個鏈表，刪除鏈表的倒數第 n 個結點，并且返回鏈表的頭結點。

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

提示：

• 鏈表中結點的數目為 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

---

方法一：雙指針法（一次遍歷）

使用快慢指針技巧，讓快指針先移動n步，然后同時移動快慢指針。當快指針到達鏈表末尾時，慢指針正好指向要刪除節點的前驅節點。通過啞節點簡化邊界條件處理。

1. 初始化啞節點：避免處理頭節點刪除的特殊情況。
2. 快指針先移動n步：拉開快慢指針的間距。
3. 同步移動快慢指針：直到快指針到達鏈表末尾。
4. 刪除目標節點：修改慢指針的next指針跳過目標節點。

代碼實現(Java)：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode fast = dummy, slow = dummy;// 快指針先移動n步for (int i = 0; i < n; i++) {fast = fast.next;}// 同步移動，直到快指針到達末尾while (fast.next != null) {fast = fast.next;slow = slow.next;}// 刪除目標節點slow.next = slow.next.next;return dummy.next;}
}

復雜度分析:

• 時間復雜度：O(L)，其中 L 為鏈表長度，只需一次遍歷。
• 空間復雜度：O(1)，僅使用固定額外空間。

---

方法二：計算鏈表長度（兩次遍歷）

先遍歷鏈表獲取長度 L，再定位到倒數第n個節點的前驅位置（正數第 L-n 個節點），直接刪除目標節點。

1. 獲取鏈表長度：遍歷鏈表統計節點總數。
2. 定位前驅節點：通過長度計算前驅位置，移動到該位置。
3. 刪除目標節點：修改前驅節點的next指針。

代碼實現(Java)：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;int length = getLength(head);ListNode curr = dummy;// 移動到前驅節點位置for (int i = 0; i < length - n; i++) {curr = curr.next;}// 刪除目標節點curr.next = curr.next.next;return dummy.next;}// 輔助函數：計算鏈表長度private int getLength(ListNode head) {int len = 0;while (head != null) {len++;head = head.next;}return len;}
}

復雜度分析:

• 時間復雜度：O(L)，兩次遍歷，總體仍為線性時間。
• 空間復雜度：O(1)，僅使用固定額外空間。

---

20. 有效的括號

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

• 左括號必須用相同類型的右括號閉合。
• 左括號必須以正確的順序閉合。
• 每個右括號都有一個對應的相同類型的左括號。

示例 1：

輸入：s = "()"
輸出：true

示例 2：

輸入：s = "()[]{}"
輸出：true

示例 3：

輸入：s = "(]"
輸出：false

示例 4：

輸入：s = "([])"
輸出：true

提示：

• 1 <= s.length <= 10^4
• s 僅由括號 '()[]{}' 組成

---

方法：棧輔助法

利用棧結構匹配括號，通過遍歷字符串處理括號閉合關系。

1. 提前剪枝：字符串長度為奇數時直接返回false，因為有效括號必須成對出現
2. 棧結構操作：
   • 遇到左括號時壓入棧頂。
   • 遇到右括號時彈出棧頂元素，檢查是否匹配。
3. 三種失效情況處理：
   • 右括號出現時棧為空（無對應左括號）。
   • 右括號與棧頂左括號類型不匹配。
   • 遍歷結束后棧中仍有未匹配左括號。

代碼實現(Java)：

class Solution {public boolean isValid(String s) {if (s.length() % 2 != 0) return false; // 奇數長度直接無效Deque<Character> stack = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') { // 左括號入棧stack.push(c);} else { // 右括號匹配if (stack.isEmpty()) return false; // 棧空說明無對應左括號char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {return false;}}}return stack.isEmpty(); // 最后檢查棧是否為空}
}

復雜度分析：

• 時間復雜度: 單次遍歷字符串O(n)，棧操作O(1)，總時間復雜度O(n)。

---

聲明

1. 本文版權歸 CSDN 用戶 Allen Wurlitzer 所有，遵循CC-BY-SA協議發布，轉載請注明出處。
2. 本文題目來源 力扣-LeetCode ，著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。