面试题精讲:数据结构

1. 红黑树 (Red-Black Tree)

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

红黑树 vs AVL 树：
- AVL 树：严格平衡（任意节点左右子树高度差不超过1）。查询极快，但插入和删除时需要频繁旋转，开销大。
- 红黑树：非严格平衡。它通过牺牲一定的查询性能，换取了更低的增删成本（单次最多3次旋转）。
结论：
- 如果你的应用中 搜索次数远多于增删（如只读数据库），选 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 级。

规律： 方法数等于 2 的 n-1 次方。

f = lambda n: 1 << (n - 1)  # 位运算替代乘法/幂运算，性能最优

3. 杨氏矩阵查找

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

思路： 从右上角（或左下角）开始寻找，排除整行/整列。
- 若当前值 > 目标：左移一列。
- 若当前值 < 目标：下移一行。
复杂度： 时间 O(m+n)，空间 O(1)。

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 转换为 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.next = head
        
        return next_node

4.2 交叉链表求交点

核心思路： 浪漫相遇法，空间复杂度 O(1)，无需计算链表长度差。两个指针 A 和 B 同时出发，走完自己的链表就去走对方的链表，由于总路径相同，它们一定会在交点相遇（无交点则同时走到 None）。

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

4.3 单链表逆置

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

def reverse_linked_list(head):
    if not head or not head.next:
        return head
        
    pre, cur = None, head
    while cur:
        tmp = cur.next  # 1. 暂存下一个节点，防止断链
        cur.next = pre  # 2. 核心：反转当前指针
        pre = cur       # 3. pre 前移
        cur = tmp       # 4. cur 前移
    return pre

5. Python 实用容器操作

5.1 列表去重（保持顺序）

Python 3.7+ 字典是有序的，利用这一特性最简洁高效：

items = ['b','c','d','b','c','a','a']
unique_items = list(dict.fromkeys(items))

5.2 Python 创建字典的多种姿势

直接字面量：最常用且性能最好。
```
d = {'name': 'earth', 'port': '80'}
```

工厂方法 dict：支持元组列表或关键字参数。

d = dict([('name', 'earth'), ('port', '80')])
d = dict(name='earth', port='80')

fromkeys 方法：初始化具有统一默认值的字典。

d = {}.fromkeys(('x', 'y'), -1)  # 注意：默认值如果是可变对象，所有key会共享

5.3 合并两个有序列表

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

def merge_sorted_list(a, b):
    result = []
    i = j = 0
    # 双指针遍历，避免 pop(0) 的 O(n) 开销
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    # 合并剩余部分
    result.extend(a[i:])
    result.extend(b[j:])
    return result

6. 基础排序与查找

6.1 二分查找

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

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # 避免 (high + low) 大数溢出（Python虽无溢出，但跨语言通用）
        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

6.2 快速排序

面试核心： 分治思想。平均时间复杂度 O(n log n)，空间复杂度取决于递归深度。

def quicksort(arr):
    if len(arr) < 2:
        return arr
    
    pivot = arr[0]  # 可优化为随机选或三数取中
    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)

7. 二叉树高频考点

7.1 节点定义与层次遍历

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

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

def level_order_lookup(root):
    if not root:
        return []
    result = []
    current_row = [root]
    while current_row:
        result.append([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
    return result

7.2 深度优先遍历

利用系统栈实现，改变访问根节点的时机得到三种顺序：

# 前序：根 -> 左 -> 右
def pre_order(root, res=None):
    if res is None: res = []
    if not root: return res
    res.append(root.data)
    pre_order(root.left, res)
    pre_order(root.right, res)
    return res

# 中序：左 -> 根 -> 右
def mid_order(root, res=None):
    if res is None: res = []
    if not root: return res
    mid_order(root.left, res)
    res.append(root.data)
    mid_order(root.right, res)
    return res

# 后序：左 -> 右 -> 根
def post_order(root, res=None):
    if res is None: res = []
    if not root: return res
    post_order(root.left, res)
    post_order(root.right, res)
    res.append(root.data)
    return res

7.3 其他基础考点

# 求最大树深
def get_max_depth(root):
    if not root:
        return 0
    return max(get_max_depth(root.left), get_max_depth(root.right)) + 1

# 判断两棵树是否相同
def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q or p.data != q.data:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

8. 其他经典算法

8.1 变位词判断

三种复杂度实现，从“暴力破解”到“空间换时间”：

class Anagram:
    @staticmethod
    def is_anagram_sort(s1, s2):
        """排序法：逻辑最简洁，时间 O(n log n)"""
        return sorted(s1) == sorted(s2)

    @staticmethod
    def is_anagram_count(s1, s2):
        """计数法：性能最高，时间 O(n)，空间 O(1)（仅小写字母）"""
        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)

8.2 找零问题

典型动态规划问题，避免重复计算：

def coin_change(values, money):
    dp = [float('inf')] * (money + 1)
    dp[0] = 0
    
    for cents in range(1, money + 1):
        for coin in values:
            if coin <= cents:
                dp[cents] = min(dp[cents], dp[cents - coin] + 1)
    return dp[money] if dp[money] != float('inf') else -1

面试题精讲:数据结构#

#1. 红黑树 (Red-Black Tree)

#2. 经典递归与动态规划

#2.1 台阶问题 (Fibonacci 变种)

#2.2 变态台阶问题

#3. 杨氏矩阵查找

#4. 链表高频技巧

#4.1 成对调换链表节点

#4.2 交叉链表求交点

#4.3 单链表逆置

#5. Python 实用容器操作

#5.1 列表去重（保持顺序）

#5.2 Python 创建字典的多种姿势

#5.3 合并两个有序列表

#6. 基础排序与查找

#6.1 二分查找

#6.2 快速排序

#7. 二叉树高频考点

#7.1 节点定义与层次遍历

#7.2 深度优先遍历

#7.3 其他基础考点

#8. 其他经典算法

#8.1 变位词判断

#8.2 找零问题