經典算法題解析：從思路到實現，掌握核心編程思維

算法是編程的靈魂，也是面試中的重點考察內容。本文精選了幾道經典算法題，涵蓋字符串處理、鏈表操作、樹遍歷等常見場景，通過詳細解析幫助你理解算法設計思路與實現細節，提升解題能力。

一、無重復字符的最長子串

題目描述

給定一個字符串?s，請你找出其中不含有重復字符的最長子串的長度。

示例：

輸入：s = "abcabcbb"?→ 輸出：3（最長子串是?"abc"）
輸入：s = "bbbbb"?→ 輸出：1（最長子串是?"b"）
輸入：s = "pwwkew"?→ 輸出：3（最長子串是?"wke"）

解題思路：滑動窗口 + 哈希表

滑動窗口是處理子串問題的高效方法，核心是維護一個動態窗口?[left, right]，確保窗口內的字符無重復。配合哈希表記錄字符最后出現的位置，可快速調整窗口邊界。

代碼實現

def length_of_longest_substring(s):char_map = {}  # 記錄字符最后出現的位置left = 0       # 滑動窗口左邊界max_len = 0    # 最大長度for right in range(len(s)):current_char = s[right]# 若當前字符已存在且在窗口內，移動左邊界if current_char in char_map and char_map[current_char] >= left:left = char_map[current_char] + 1# 更新字符的最新位置char_map[current_char] = right# 計算當前窗口長度并更新最大值current_len = right - left + 1max_len = max(max_len, current_len)return max_len

詳細解析

核心變量：
- left?和?right?分別為窗口的左右邊界，初始時?left=0。
- char_map?存儲每個字符最后一次出現的索引，用于快速判斷重復。
- max_len?記錄最長無重復子串的長度。
窗口調整邏輯：
- 遍歷字符串時，right?不斷右移，擴大窗口范圍。
- 若當前字符?current_char?已在?char_map?中，且上次出現的位置在窗口內（char_map[current_char] >= left），說明出現重復，需將左邊界?left?移到上次出現位置的下一位（char_map[current_char] + 1），確保窗口內無重復。
- 每次移動后，計算當前窗口長度（right - left + 1），并更新?max_len。
復雜度分析：
- 時間復雜度：O (n)，每個字符僅被遍歷一次。
- 空間復雜度：O (min (n, m))，m?為字符集大小（如 ASCII 字符集為 256）。

二、合并兩個有序鏈表

題目描述

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：
輸入：l1 = [1,2,4],?l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

解題思路：遞歸法

遞歸是處理鏈表問題的常用思路，通過比較兩個鏈表的當前節點值，遞歸合并剩余節點，代碼簡潔直觀。

代碼實現

# 定義鏈表節點
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists(l1, l2):# 若其中一個鏈表為空，直接返回另一個if not l1:return l2if not l2:return l1# 遞歸合并if l1.val <= l2.val:l1.next = merge_two_lists(l1.next, l2)return l1else:l2.next = merge_two_lists(l1, l2.next)return l2

詳細解析

遞歸終止條件：
- 若?l1?為空，返回?l2（空鏈表與非空鏈表合并結果為非空鏈表）。
- 若?l2?為空，返回?l1，邏輯同上。
遞歸邏輯：
- 比較?l1.val?和?l2.val，選擇值較小的節點作為當前合并鏈表的節點。
- 遞歸合并該節點的?next?指針與另一個鏈表，形成新的鏈表。
- 返回當前選擇的節點，作為合并后鏈表的一部分。
示例驗證：
以?l1 = [1,2,4]?和?l2 = [1,3,4]?為例：
- 比較?l1.val=1?和?l2.val=1，選擇?l1，遞歸合并?l1.next=[2,4]?與?l2=[1,3,4]。
- 后續步驟類似，最終合并結果為?[1,1,2,3,4,4]。
復雜度分析：
- 時間復雜度：O (m + n)，m?和?n?分別為兩鏈表長度，需遍歷所有節點。
- 空間復雜度：O (m + n)，遞歸棧深度最壞情況下為兩鏈表長度之和。

三、有效的括號

題目描述

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

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。

示例：

輸入：s = "()"?→ 輸出：True
輸入：s = "()[]{}"?→ 輸出：True
輸入：s = "(]"?→ 輸出：False

解題思路：棧結構

棧的 “后進先出” 特性非常適合處理括號匹配問題：左括號入棧，右括號則彈出棧頂元素檢查是否匹配。

代碼實現

def is_valid(s):stack = []  # 存儲左括號的棧mapping = {')': '(', ']': '[', '}': '{'}  # 右括號到左括號的映射for char in s:# 若為右括號，檢查棧頂元素是否匹配if char in mapping:# 棧為空或棧頂元素不匹配，返回Falseif not stack or stack.pop() != mapping[char]:return False# 若為左括號，直接入棧else:stack.append(char)# 遍歷結束后，棧應為空return len(stack) == 0

詳細解析

棧與哈希表的配合：
- 棧?stack?用于存儲左括號，遇到左括號直接入棧。
- 哈希表?mapping?存儲右括號到左括號的映射，方便快速查找匹配的左括號（如?')'?對應?'('）。
匹配邏輯：
- 遍歷字符串中的每個字符：
  - 若為右括號：
    - 若棧為空，說明沒有左括號與之匹配，返回?False。
    - 彈出棧頂元素，若與當前右括號不匹配（如?')'?對應棧頂不是?'('），返回?False。
  - 若為左括號，直接入棧。
- 遍歷結束后，若棧不為空，說明存在未匹配的左括號，返回?False；否則返回?True。
示例驗證：
輸入?s = "([)]"：
- 遍歷到?'('，入棧 → 棧：['(']。
- 遍歷到?'['，入棧 → 棧：['(', '[']。
- 遍歷到?')'，棧頂為?'['，不匹配 → 返回?False。
復雜度分析：
- 時間復雜度：O (n)，遍歷字符串一次。
- 空間復雜度：O (n)，最壞情況下棧存儲所有左括號。

四、二叉樹的中序遍歷

題目描述

給定一個二叉樹的根節點?root，返回它的中序遍歷結果。（中序遍歷順序：左子樹 → 根節點 → 右子樹）

示例：
輸入：root = [1,null,2,3]（二叉樹結構：根節點 1，右子節點 2，2 的左子節點 3）
輸出：[1,3,2]

解題思路：遞歸法

遞歸是實現樹遍歷的直觀方法，中序遍歷的遞歸邏輯為：先遍歷左子樹，再訪問根節點，最后遍歷右子樹。

代碼實現

# 定義二叉樹節點
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorder_traversal(root):result = []def inorder(node):if node is None:return# 遞歸遍歷左子樹inorder(node.left)# 訪問根節點result.append(node.val)# 遞歸遍歷右子樹inorder(node.right)inorder(root)return result

詳細解析

遞歸函數設計：
- 輔助函數?inorder(node)?用于實現中序遍歷，參數為當前節點?node。
- 終止條件：若?node?為空，直接返回（空樹無需遍歷）。
遍歷順序：
- 遞歸遍歷左子樹：inorder(node.left)，確保左子樹所有節點先于根節點被訪問。
- 訪問根節點：將當前節點值加入結果列表?result。
- 遞歸遍歷右子樹：inorder(node.right)，確保右子樹所有節點后于根節點被訪問。
示例驗證：
對于?root = [1,null,2,3]：
- 調用?inorder(1)，先遍歷左子樹（為空），訪問?1?→?result = [1]。
- 遞歸遍歷右子樹?2，先遍歷其左子樹?3：訪問?3?→?result = [1,3]。
- 訪問?2?→?result = [1,3,2]，最終返回?[1,3,2]。
復雜度分析：
- 時間復雜度：O (n)，遍歷所有節點一次。
- 空間復雜度：O (h)，h?為樹的高度，遞歸棧深度取決于樹高，最壞情況（鏈狀樹）為 O (n)。