前言

算法和数据结构是程序员面试的重头戏。本文整理了面试中最高频的题型和解题思路，配合代码示例，帮你理清思路、高效备战。

算法

复杂度分析

大 O 表示法

大 O 表示法描述了算法执行时间随输入规模增长的趋势。

复杂度 名称 常见示例
O(1) 常数时间 数组下标访问
O(log n) 对数时间 二分查找
O(n) 线性时间 遍历数组
O(n log n) 线性对数 归并排序、快速排序
O(n²) 平方时间 冒泡排序、双重循环
O(2ⁿ) 指数时间 递归求斐波那契
O(n!) 阶乘时间 旅行商问题 
1
2
3
4
5
6
7
8
9
10
11
# 常见操作的时间复杂度
my_list = [1, 2, 3, 4, 5]

my_list[0]           # O(1) - 索引
my_list.append(6)    # O(1) - 尾部追加
my_list.pop()        # O(1) - 尾部删除
my_list.insert(0, 0) # O(n) - 头部插入（需要移动所有元素）
0 in my_list         # O(n) - 线性搜索

my_set = {1, 2, 3}
0 in my_set          # O(1) - 哈希查找

数组与字符串

双指针

双指针是数组问题中最常用的技巧之一。

1
2
3
4
5
6
7
8
9
10
11
12
13
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """有序数组的两数之和"""
    left, right = 0, len(numbers) - 1

    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left + 1, right + 1]
        elif current < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
def length_of_longest_substring(s: str) -> int:
    """无重复字符的最长子串"""
    char_index = {}
    max_len = 0
    left = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
def subarray_sum(nums: list[int], k: int) -> int:
    """和为 K 的子数组个数"""
    prefix_sum = {0: 1}
    count = 0
    current_sum = 0

    for num in nums:
        current_sum += num
        if current_sum - k in prefix_sum:
            count += prefix_sum[current_sum - k]
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1

    return count

链表

基础操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    """反转链表"""
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def has_cycle(head: ListNode) -> bool:
    """检测环形链表"""
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

def find_middle(head: ListNode) -> ListNode:
    """找到链表中点"""
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

栈与队列

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
def daily_temperatures(temperatures: list[int]) -> list[int]:
    """每日温度：距离下一次更高温度的天数"""
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 单调递减栈，存索引

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)

    return answer

栈与括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
def is_valid_parentheses(s: str) -> bool:
    """有效的括号"""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for char in s:
        if char in '([{':
            stack.append(char)
        elif not stack or stack.pop() != pairs[char]:
            return False

    return len(stack) == 0

二叉树

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root: TreeNode) -> list[int]:
    """中序遍历（迭代）"""
    result, stack = [], []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

def level_order(root: TreeNode) -> list[list[int]]:
    """层次遍历（BFS）"""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

递归技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def max_depth(root: TreeNode) -> int:
    """二叉树最大深度"""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_symmetric(root: TreeNode) -> bool:
    """对称二叉树"""
    def check(left, right):
        if not left and not right: return True
        if not left or not right: return False
        return (left.val == right.val and
                check(left.left, right.right) and
                check(left.right, right.left))
    return check(root.left, root.right)

动态规划

DP 五步法

  1. 定义 dp 数组的含义
  2. 找出递推公式
  3. 初始化 dp 数组
  4. 确定遍历顺序
  5. 推导 dp 数组验证

经典题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def climb_stairs(n: int) -> int:
    """爬楼梯：每次爬 1 或 2 阶"""
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def max_subarray(nums: list[int]) -> int:
    """最大子数组和"""
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

def coin_change(coins: list[int], amount: int) -> int:
    """零钱兑换：最少硬币数"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

0-1 背包

1
2
3
4
5
6
7
8
9
10
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """0-1 背包问题"""
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

高频考点速查

数据结构 必会操作 LeetCode 题号
数组 双指针、滑动窗口 1, 15, 209, 3
链表 反转、环检测 206, 141, 21
栈 括号、单调栈 20, 739, 155
队列 BFS、滑动窗口 102, 239
二叉树 遍历、对称、深度 94, 101, 104
哈希表 两数之和、去重 1, 128
堆 TopK、合并 215, 347
图 DFS/BFS、拓扑排序 200, 207
DP 爬楼梯、背包 70, 198, 322

面试心态建议

「面试官在意的不是你是否第一次就写出最优解，而是你的思考过程和沟通能力。」

  1. 先确认题意，复述一遍确保理解正确
  2. 说出你的思路再开始写代码
  3. 先写暴力解，再优化
  4. 主动分析时间空间复杂度
  5. 写完自查边界条件和测试用例

总结

算法面试的本质是 模式识别。刷题时注意总结规律——很多题只是换了一个壳子，内核是相同的经典解法。坚持每天 1-2 题，三个月后你会发现质的飞跃。