1. 红黑树 (Red-Black Tree)

面试核心： 为什么 Linux 内核、Python 字典（某些版本）和 Java HashMap 选择红黑树？

  • 红黑树 vs AVL 树：
    • AVL 树：严格平衡（高度差 $\le 1$）。查询极快，但插入和删除时需要频繁旋转，开销大。
    • 红黑树：非严格平衡。它通过牺牲一定的查询性能，换取了更低的增删成本（旋转次数少）。
  • 结论： * 如果你的应用中 搜索次数远多于增删（如只读数据库），选 AVL。
    • 如果 搜索、增删频率相当（如通用容器），红黑树 是最佳折中方案。

2. 经典递归与动态规划

2.1 台阶问题 (Fibonacci 变种)

一只青蛙一次可以跳 1 级或 2 级台阶，求跳上 $n$ 级台阶的方法数。

  • Python 3 最佳实践（空间换时间）：
def fib(n):
    # 迭代法：时间 O(n)，空间 O(1)
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return b

2.2 变态台阶问题

一次可以跳 1, 2, ..., $n$ 级。

  • 规律： $f(n) = 2^{n-1}$。
f = lambda n: 1 << (n - 1)  # 位运算最快

3. 杨氏矩阵查找

面试核心： 如何在行列皆有序的矩阵中寻找目标值？

  • 思路： 从右上角（或左下角）开始寻找。
    • 若当前值 > 目标：左移。
    • 若当前值 < 目标：下移。
  • 复杂度： $O(m+n)$。
def find_in_matrix(matrix, target):
    if not matrix: return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        val = matrix[row][col]
        if val == target: return True
        elif val > target: col -= 1
        else: row += 1
    return False

4. 链表技巧

4.1 成对调换链表节点

1->2->3->4 $\Rightarrow$ 2->1->4->3

def swap_pairs(head):
    if head and head.next:
        next_node = head.next
        head.next = swap_pairs(next_node.next)
        next_node.next = head
        return next_node
    return head

4.2 交叉链表求交点

核心思路： 浪漫相遇法。 两个指针 $A$ 和 $B$ 同时出发，走完自己的路就去走对方的路，由于 $L_a + L_b = L_b + L_a$，它们一定会在交点相遇。

def get_intersection_node(headA, headB):
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

5. 列表去重（保持顺序）

在 Python 中，如何优雅地去重并保留原序？

# Python 3.7+ 字典是有序的，利用这一特性最简洁：
items = ['b','c','d','b','c','a','a']
unique_items = list(dict.fromkeys(items))

6. 链表成对调换 (Swap Nodes in Pairs)

面试核心： 考察递归思维与链表指针的操作细节。

任务：将 1->2->3->4 转换为 2->1->4->3。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 递归终止条件：节点为空或只有一个节点
        if head is None or head.next is None:
            return head
        
        # 记录第二个节点
        next_node = head.next
        # 递归处理后续节点，并将其挂在当前 head 的后面
        head.next = self.swapPairs(next_node.next)
        # 将 next_node 指向当前的 head，完成反转
        next_node.next = head
        
        return next_node

7. Python 创建字典的多种姿势

面试核心： 了解 Python 语法的灵活性及底层工厂方法。

  1. 直接创建 (Literal)：最常用且性能最好。 
    d = {'name': 'earth', 'port': '80'}
  2. 工厂方法 (dict)：支持元组列表或关键字参数。 
    d = dict([('name', 'earth'), ('port', '80')])
d = dict(name='earth', port='80')
  3. fromkeys 方法：用于初始化具有统一默认值的字典。 
    d = {}.fromkeys(('x', 'y'), -1) # {'x': -1, 'y': -1}

8. 合并两个有序列表

面试核心： 归并排序的核心步骤，考查边界处理能力。

循环解法 (推荐：空间复杂度更优)

def merge_sorted_list(a, b):
    result = []
    while a and b:
        # 每次弹出更小的那个元素
        if a[0] <= b[0]:
            result.append(a.pop(0))
        else:
            result.append(b.pop(0))
    # 将剩余部分直接合并
    result.extend(a or b)
    return result

9. 交叉链表求交点

面试核心： 空间复杂度 $O(1)$ 的解法。

思路：如果两个链表相交，那么从交点到尾部的一段是公共的。

def get_intersection_node(l1, l2):
    # 计算两个链表的长度差，让长的先走
    p1, p2 = l1, l2
    len1 = len2 = 0
    while p1: len1 += 1; p1 = p1.next
    while p2: len2 += 1; p2 = p2.next
    
    # 指针复位
    p1, p2 = l1, l2
    # 消除长度差
    if len1 > len2:
        for _ in range(len1 - len2): p1 = p1.next
    else:
        for _ in range(len2 - len1): p2 = p2.next
        
    # 同步走，相遇点即交点
    while p1 != p2:
        p1 = p1.next
        p2 = p2.next
    return p1

面试核心： 注意 mid 计算防止溢出的细节，以及边界条件的控制。

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # 避免 (high + low) // 2 在大数时溢出
        mid = low + (high - low) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None

# 测试
my_list = [1, 3, 5, 7, 9]
print(f"Index of 3: {binary_search(my_list, 3)}") # Output: 1

11. 快速排序 (Quick Sort)

面试核心： 分治思想（Divide and Conquer）。平均时间复杂度 $O(n \log n)$，空间复杂度取决于实现方式。

def quicksort(arr):
    """
    Python 风格的快排实现（利用列表推导式）
    """
    if len(arr) < 2:
        return arr
    
    # 选取基准值（Pivot）
    pivot = arr[0]
    # 分区（Partition）
    less = [i for i in arr[1:] if i <= pivot]
    greater = [i for i in arr[1:] if i > pivot]
    
    # 递归调用
    return quicksort(less) + [pivot] + quicksort(greater)

# 测试
print(quicksort([2, 4, 6, 7, 1, 2, 5]))

12. 找零问题 (Coin Change)

面试核心： 典型的动态规划（DP）问题。通过构建最优子结构，避免重复计算。

def coin_change(values, money):
    """
    values: 硬币面额列表，如 [25, 21, 10, 5, 1]
    money: 需要找零的总金额
    返回: 达到该金额所需的最少硬币数
    """
    # 初始化 DP 数组，长度为 money + 1，初始值为无穷大
    # dp[i] 表示凑齐金额 i 所需的最少硬币数
    dp = [float('inf')] * (money + 1)
    dp[0] = 0
    
    for cents in range(1, money + 1):
        for coin in values:
            if coin <= cents:
                # 状态转移方程：取当前金额减去该硬币面值后的最少硬币数 + 1
                dp[cents] = min(dp[cents], dp[cents - coin] + 1)
                
    return dp[money] if dp[money] != float('inf') else -1

# 示例：找零 63 元
# print(coin_change([25, 21, 10, 5, 1], 63))

13. 二叉树的构建与遍历

面试核心： 考察对递归结构（Node）和队列（Queue）在广度优先搜索（BFS）中应用的掌握。

14. 二叉树节点定义

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# 构建示例树
#        1
#      /   \
#     3     2
#    / \   / \
#   7   6 5   4
#  /
# 0
tree = Node(1, 
            Node(3, Node(7, Node(0)), Node(6)), 
            Node(2, Node(5), Node(4)))

15. 层次遍历 (BFS / Level Order Traversal)

面试核心： 使用列表推导式或双端队列 collections.deque 实现高效遍历。

def level_order_lookup(root):
    if not root:
        return
    
    # 使用当前层节点列表
    current_row = [root]
    while current_row:
        # 打印当前层的所有数据
        print([node.data for node in current_row])
        
        # 获取下一层的所有非空子节点
        next_row = []
        for node in current_row:
            if node.left: next_row.append(node.left)
            if node.right: next_row.append(node.right)
        
        current_row = next_row

# 调用
# level_order_lookup(tree)

进阶技巧： 面试中常要求按层返回嵌套列表（如 [[1], [3, 2], [7, 6, 5, 4], [0]]），上述逻辑只需稍作修改即可实现。

16. 深度优先遍历 (DFS) 与 17. 三种遍历顺序

面试核心： 深度优先遍历（DFS）本质上是利用了栈（递归即系统栈）的特性。改变访问根节点的时机，就得到了前、中、后序遍历。

核心代码实现

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# 1. 前序遍历 (根 -> 左 -> 右)
def pre_order(root):
    if not root: return
    print(root.value, end=' ')
    pre_order(root.left)
    pre_order(root.right)

# 2. 中序遍历 (左 -> 根 -> 右)
def mid_order(root):
    if not root: return
    mid_order(root.left)
    print(root.value, end=' ')
    mid_order(root.right)

# 3. 后序遍历 (左 -> 右 -> 根)
def post_order(root):
    if not root: return
    post_order(root.left)
    post_order(root.right)
    print(root.value, end=' ')

18. 求最大树深 (Max Depth)

面试核心： 分治法。整棵树的高度 = max(左子树高度, 右子树高度) + 1。

def get_max_depth(root):
    if not root:
        return 0
    return max(get_max_depth(root.left), get_max_depth(root.right)) + 1

19. 判断两棵树是否相同 (Same Tree)

面试核心： 递归比较。两棵树相同的条件是：当前节点值相等，且左右子树也分别相同。

def is_same_tree(p, q):
    # 均为 None 则相同
    if not p and not q:
        return True
    # 一个为空或值不等则不同
    if not p or not q or p.value != q.value:
        return False
    # 递归比较子树
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

20. 重建二叉树：根据前序与中序求后序

面试核心： 1. 前序遍历的第一个元素永远是当前的根节点。 2. 在中序遍历中找到该根节点，其左侧即为左子树，右侧为右子树。

def rebuild_tree(pre_order_list, in_order_list):
    if not pre_order_list or not in_order_list:
        return None
    
    # 1. 确定根节点
    root_val = pre_order_list[0]
    root = Node(root_val)
    
    # 2. 在中序序列中定位根节点，以此切分左右子树
    pivot_index = in_order_list.index(root_val)
    
    # 3. 递归构建
    # 左子树的前序：pre_order_list[1 : pivot_index + 1]
    # 左子树的中序：in_order_list[: pivot_index]
    root.left = rebuild_tree(pre_order_list[1:pivot_index+1], in_order_list[:pivot_index])
    
    # 右子树的前序：pre_order_list[pivot_index + 1 :]
    # 右子树的中序：in_order_list[pivot_index + 1 :]
    root.right = rebuild_tree(pre_order_list[pivot_index+1:], in_order_list[pivot_index+1:])
    
    return root

# 重建后通过后序遍历验证
def verify_post_order(root):
    if not root: return
    verify_post_order(root.left)
    verify_post_order(root.right)
    print(root.value, end=' ')

21. 单链表逆置 (Reverse Linked List)

面试核心： 考察对指针（引用）变化的精确控制。

任务：将 1->2->3->...->9 转换为 9->8->...->1。

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

def reverse_linked_list(head):
    """
    通过三个指针迭代实现逆置：pre, cur, tmp
    """
    if not head or not head.next:
        return head
        
    pre = None
    cur = head
    while cur:
        tmp = cur.next  # 1. 暂存下一个节点
        cur.next = pre  # 2. 核心：将当前指针反转指向前一个
        pre = cur       # 3. pre 前移
        cur = tmp       # 4. cur 前移
    return pre

# 测试代码
link = Node(1, Node(2, Node(3, Node(4, Node(5)))))
root = reverse_linked_list(link)
while root:
    print(root.data, end=" -> ")
    root = root.next

22. 变位词判断 (Anagram Detection)

面试核心： 同一个算法的不同复杂度实现，体现了从“暴力破解”到“空间换时间”的进阶思路。

方法 1：逐位检查 (暴力法)

  • 原理：遍历第一个字符串，在第二个字符串中寻找并标记。
  • 复杂度：$O(n^2)$。

方法 2：排序对比

  • 原理：将两个字符串转化为列表并排序，若排序后完全一致则是变位词。
  • 复杂度：$O(n \log n)$。

方法 3：计数统计 (最优解)

  • 原理：利用哈希思想（或长度为 26 的数组）记录字符出现频率。
  • 复杂度：$O(n)$。
class Anagram:
    @staticmethod
    def is_anagram_v2(s1, s2):
        """排序法：逻辑最简洁"""
        return sorted(s1) == sorted(s2)

    @staticmethod
    def is_anagram_v3(s1, s2):
        """计数法：性能最高"""
        if len(s1) != len(s2): return False
        
        # 记录字符频次
        counts = [0] * 26
        for char in s1:
            counts[ord(char) - ord('a')] += 1
        for char in s2:
            counts[ord(char) - ord('a')] -= 1
            
        # 检查是否全部归零
        return all(c == 0 for c in counts)

# 测试
print(Anagram.is_anagram_v3('apple', 'pleap')) # True

23. 动态规划 (Dynamic Programming)

面试核心： 动态规划不仅仅是找零或斐波那契，它的核心在于：

  1. 寻找最优子结构。
  2. 定义状态转移方程。
  3. 存储中间结果（备忘录/DP表）。

为了提升“道满Python AI”面试教程的深度，引入 最长公共子序列 (LCS) 和 0-1 背包问题 是极佳的选择。这两个问题是动态规划（DP）的“教科书级”案例，能帮助学员深刻理解二维状态转移方程。

🏆 动态规划进阶：经典模型实战

24. 最长公共子序列 (Longest Common Subsequence, LCS)

面试核心： 子序列（Subsequence）不要求连续，只需保持相对顺序。常用于版本控制（如 git diff）和基因序列比对。

1. 状态转移方程

设 $dp[i][j]$ 为字符串 $s1$ 前 $i$ 个字符与 $s2$ 前 $j$ 个字符的最长公共子序列长度：

  • 若 $s1[i-1] == s2[j-1]$：则 $dp[i][j] = dp[i-1][j-1] + 1$
  • 若不相等：则 $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$

2. Python 代码实现

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # 构建 (m+1) x (n+1) 的二维 DP 表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
    return dp[m][n]

# 测试: "abcde" 与 "ace" -> "ace", 长度为 3
print(f"LCS Length: {lcs('abcde', 'ace')}")

25. 0-1 背包问题 (0-1 Knapsack Problem)

面试核心： 核心在于“选”或“不选”。每个物品只有一件，不可拆分。

1. 状态转移方程

设 $dp[i][j]$ 为前 $i$ 件物品放入容量为 $j$ 的背包能获得的最大价值：

  • 不选第 $i$ 件：$dp[i][j] = dp[i-1][j]$
  • 选第 $i$ 件（前提是当前容量 $j \ge weight[i]$）：$dp[i][j] = \max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])$

2. Python 优化版实现（一维滚动数组）

在面试中，能写出一维数组优化的版本会极大地加分，因为它将空间复杂度从 $O(NW)$ 降到了 $O(W)$。

def knapsack_01(weights, values, capacity):
    """
    weights: 物品重量列表
    values: 物品价值列表
    capacity: 背包最大容量
    """
    n = len(weights)
    # 使用一维数组优化空间
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 必须逆序遍历，防止重复计算同一件物品（这是 0-1 背包的关键）
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
            
    return dp[capacity]

# 测试: 物品重量 [1, 3, 4], 价值 [15, 20, 30], 背包容量 4
# 选第1件和第2件(1+3=4)，总价值 15+20=35；选第3件价值30。最大价值为 35。
print(f"Max Value: {knapsack_01([1, 3, 4], [15, 20, 30], 4)}")