21 章完整教程 · 从数组到图论 · 从零基础到面试通关
一句话:数据结构就是数据的"摆放方式"。同样的数据,摆放方式不同,操作效率天差地别。
想象你有一堆衣服要收纳:
• 随手扔进衣柜 → 找某件衣服要翻半天(无结构)
• 按季节叠好分层放 → 很快就能找到(有序结构)
• 按颜色挂起来 → 一目了然(索引结构)
数据结构就是决定"数据怎么放",从而决定"查找/插入/删除有多快"。
数据结构是"数据怎么存",算法是"数据怎么算"。两者密不可分:
| 对比 | 数据结构 | 算法 |
|---|---|---|
| 关注点 | 数据怎么存、怎么组织 | 数据怎么处理、怎么算 |
| 类比 | 仓库的货架布局 | 取货/发货的流程 |
| 例子 | 数组、链表、树、图 | 排序、搜索、动态规划 |
同一段逻辑,用不同写法,运行时间可能差几万倍。我们需要一种方式来衡量算法的快慢,而不依赖于具体的电脑。
判断一个算法好不好,不能靠"感觉快不快",得有一个标准。时间复杂度就是这个标准——它告诉你:当数据量变大时,运行时间会怎样变化?
假设 n = 1000:
• O(1) = 1 次操作
• O(log n) ≈ 10 次操作
• O(n) = 1000 次操作
• O(n log n) ≈ 10000 次操作
• O(n^2) = 1,000,000 次操作
差距一目了然!这就是为什么选对算法那么重要。
# 无论列表多长,取第一个元素都是 O(1)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
first = lst[0] # O(1)
# 字典查找也是 O(1)
d = {"name": "Alice", "age": 25}
print(d["name"]) # O(1)
# 遍历列表 O(n)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for x in lst: # O(n)
total += x
# 双重循环 O(n^2)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(lst)
for i in range(n):
for j in range(n): # n * n = n^2
pass
# 二分查找:每次排除一半数据
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 1000 个数据最多查 10 次 (log2(1000) ≈ 10)
# 1000000 个数据最多查 20 次
| 空间复杂度 | 含义 | 例子 |
|---|---|---|
| O(1) | 只用固定几个变量 | 交换两个变量 |
| O(n) | 需要一个和输入等大的数组 | 复制一个列表 |
| O(log n) | 递归调用栈的深度 | 二分查找的递归版 |
数组是一段连续的内存空间,里面存放相同类型的数据。
电影院一排有 10 个座位,编号 0 到 9:
• 每个座位放一个人(元素)
• 座位是连续的(内存连续)
• 你知道编号就能直接找到对应座位(随机访问 O(1))
• 中间插入一个人?后面所有人都要往后挪(插入 O(n))
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问(按索引) | O(1) | 直接计算地址 |
| 查找(按值) | O(n) | 最坏遍历整个数组 |
| 尾部插入 | O(1)* | 直接放到末尾 |
| 中间插入 | O(n) | 后面的元素都要后移 |
| 删除 | O(n) | 后面的元素都要前移 |
# 创建数组
arr = [3, 1, 4, 1, 5, 9, 2, 6]
# 访问 O(1)
print(arr[0]) # 3
print(arr[3]) # 1
# 查找 O(n)
idx = arr.index(5) # 找到 5 的下标
# 尾部插入 O(1)
arr.append(7)
# 中间插入 O(n)
arr.insert(2, 99) # 在下标 2 处插入
# 删除 O(n)
arr.remove(99) # 删除第一个值为 99 的元素
del arr[0] # 删除下标 0 的元素
# 遍历 O(n)
for x in arr:
print(x, end=" ")
# 暴力解法 O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# 哈希优化 O(n)
def two_sum_hash(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
print(two_sum_hash([2, 7, 11, 15], 9)) # [0, 1]
链表是一种不需要连续内存的数据结构。每个节点包含数据和指向下一个节点的指针。
想象一个寻宝游戏:第一个线索告诉你"去公园长椅下面找",长椅下面有纸条"去图书馆第三排书架"……每条线索都知道下一条在哪里,串成一整条链。你必须从头开始,一个一个跟下去。
| 对比 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续 | 分散 |
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) | O(n) 或 O(1) |
| 删除 | O(n) | O(1)* |
| 缓存友好 | 好 | 差 |
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def prepend(self, val):
"""头部插入 O(1)"""
self.head = ListNode(val, self.head)
def append(self, val):
"""尾部插入 O(n)"""
node = ListNode(val)
if not self.head:
self.head = node
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def delete(self, val):
"""删除第一个值为 val 的节点"""
dummy = ListNode(0, self.head)
prev, cur = dummy, self.head
while cur:
if cur.val == val:
prev.next = cur.next
break
prev, cur = cur, cur.next
self.head = dummy.next
def display(self):
parts = []
cur = self.head
while cur:
parts.append(str(cur.val))
cur = cur.next
print(" -> ".join(parts) + " -> None")
ll = LinkedList()
ll.append(3); ll.append(1); ll.append(4)
ll.display() # 3 -> 1 -> 4 -> None
ll.prepend(0)
ll.display() # 0 -> 3 -> 1 -> 4 -> None
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
栈是一种后进先出(LIFO)的数据结构。只能从一端(栈顶)进行插入和删除。
食堂里一摞盘子:放盘子只能放在最上面(push),取盘子只能从最上面拿(pop)。最后放上去的,最先被取走——后进先出。
# Python 的 list 天然支持栈操作
stack = []
stack.append(1) # 入栈 O(1)
stack.append(2)
stack.append(3)
print(stack.pop()) # 出栈 → 3(后进先出)
print(stack[-1]) # 查看栈顶 → 2
def is_valid(s):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for c in s:
if c in "([{":
stack.append(c)
elif c in ")]}":
if not stack or stack[-1] != pairs[c]:
return False
stack.pop()
return len(stack) == 0
print(is_valid("({[]})")) # True
print(is_valid("([)]")) # False
def eval_rpn(tokens):
"""逆波兰表达式求值(后缀表达式)"""
stack = []
for t in tokens:
if t in "+-*/":
b, a = stack.pop(), stack.pop()
if t == "+": stack.append(a + b)
elif t == "-": stack.append(a - b)
elif t == "*": stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(t))
return stack[0]
# "2 1 + 3 *" = (2+1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"])) # 9
队列是一种先进先出(FIFO)的数据结构。从队尾入队,从队头出队。
新来的人排到队尾(enqueue),队头的人先买到离开(dequeue)。先来的先走——先进先出。
from collections import deque
queue = deque()
queue.append("Alice") # 入队 O(1)
queue.append("Bob")
queue.append("Charlie")
print(queue.popleft()) # 出队 O(1) → Alice
print(queue.popleft()) # → Bob
循环队列用数组实现,让首尾相连,充分利用空间:
class CircularQueue:
"""用数组实现的循环队列"""
def __init__(self, capacity):
self.queue = [None] * capacity
self.capacity = capacity
self.front = 0
self.rear = 0
self.count = 0
def enqueue(self, item):
if self.count == self.capacity:
raise Exception("队列已满")
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity # 循环
self.count += 1
def dequeue(self):
if self.count == 0:
raise Exception("队列为空")
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity # 循环
self.count -= 1
return item
cq = CircularQueue(5)
cq.enqueue(1); cq.enqueue(2); cq.enqueue(3)
print(cq.dequeue()) # 1
print(cq.dequeue()) # 2
import heapq
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
print(heapq.heappop(pq)) # 1(最小的先出)
哈希表通过一个哈希函数把键映射到数组下标,实现 O(1) 的查找、插入和删除。
图书馆有 100 万个座位,找"张三":
• 没有索引:从第 1 个开始一个一个找 → O(n)
• 有索引:算一下姓氏笔画 → 直接走到第 38 号书架 → O(1)
两个不同的键可能映射到同一个位置——这叫哈希冲突。
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 链地址法 | 冲突位置挂链表 | 简单,负载因子可 > 1 | 链表长了变慢 |
| 开放寻址法 | 冲突了找下一个空位 | 缓存友好 | 负载因子不能太高 |
# dict 和 set 都是哈希表
d = {"apple": 1, "banana": 2}
print(d["apple"]) # O(1) 查找
d["cherry"] = 3 # O(1) 插入
s = {1, 2, 3}
s.add(4) # O(1)
print(3 in s) # O(1) 查找
# 注意:只有可哈希的类型才能做键
# 可哈希:int, str, tuple
# 不可哈希:list, dict, set
树是一种层次结构的数据结构。就像一棵倒着的树,根在上面,叶子在下面。
CEO 是根节点,各部门总监是子节点,普通员工是叶子节点。每个人只有一个直接上级,但可以有多个下属。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(root):
"""前序:根->左->右"""
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root):
"""中序:左->根->右"""
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root):
"""后序:左->右->根"""
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
from collections import deque
def level_order(root):
"""层序遍历(BFS)"""
if not root: return []
result, queue = [], deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return result
def max_depth(root):
if not root: return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
二叉搜索树的核心性质:左子树所有节点 < 根 < 右子树所有节点。
在 1~100 之间猜数字:猜 50,说"大了"→ 只需在 1~49 中继续猜。每次排除一半——这就是 BST 查找的思路!
def search_bst(root, target):
"""查找 O(log n) 平均"""
if not root: return None
if target == root.val: return root
if target < root.val: return search_bst(root.left, target)
return search_bst(root.right, target)
def insert_bst(root, val):
"""插入 O(log n) 平均"""
if not root: return TreeNode(val)
if val < root.val: root.left = insert_bst(root.left, val)
elif val > root.val: root.right = insert_bst(root.right, val)
return root
BST 可能退化成链表。平衡树通过自动调整,保证树的高度始终是 O(log n)。
| 对比 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡标准 | 严格(高度差 ≤ 1) | 宽松(最长路径 ≤ 2×最短) |
| 查找 | 更快(树更矮) | 稍慢 |
| 插入/删除 | 旋转次数多 | 旋转次数少 |
| 适用场景 | 查找密集 | 插入删除频繁 |
| 实际使用 | 数据库索引 | Java TreeMap、Linux 内核 |
堆是一种特殊的完全二叉树:最大堆中父节点 ≥ 子节点,最小堆中父节点 ≤ 子节点。
最大堆像公司:总经理 > 部门经理 > 普通员工。任何时候你都能快速找到"最大的那个"(堆顶)。
import heapq
# Python 的 heapq 是最小堆
heap = []
heapq.heappush(heap, 3) # 插入 O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heapq.heappop(heap)) # 弹出最小值 O(log n) → 1
# 从列表建堆 O(n)
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(nums) # [1, 2, 8, 3, 5](堆的数组表示)
# 最大堆技巧:取负数
max_heap = []
for x in [3, 1, 4]:
heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap)) # 4
def heap_sort(arr):
"""堆排序 O(n log n)"""
heapq.heapify(arr) # 建堆 O(n)
result = []
while arr:
result.append(heapq.heappop(arr)) # 逐个弹出 O(log n)
return result
print(heap_sort([5, 3, 8, 1, 2])) # [1, 2, 3, 5, 8]
import heapq
def top_k(nums, k):
"""找出最大的 K 个数 O(n log k)"""
return heapq.nlargest(k, nums)
print(top_k([3, 1, 4, 1, 5, 9, 2, 6], 3)) # [9, 6, 5]
图由顶点(节点)和边组成,用来表示"多对多"的关系。
微信好友关系就是一张图:每个人是节点,好友关系是边。你和朋友之间可能有共同好友,形成复杂的网络。
# 邻接矩阵(适合稠密图)
# graph[i][j] = 1 表示 i 和 j 之间有边
graph_matrix = [
[0, 1, 1, 0], # 节点 0 连接 1, 2
[1, 0, 1, 1], # 节点 1 连接 0, 2, 3
[1, 1, 0, 1], # 节点 2 连接 0, 1, 3
[0, 1, 1, 0], # 节点 3 连接 1, 2
]
# 邻接表(适合稀疏图,更常用)
from collections import defaultdict
graph = defaultdict(list)
edges = [(0,1), (0,2), (1,2), (1,3), (2,3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 无向图要加反向边
# graph = {0: [1,2], 1: [0,2,3], 2: [0,1,3], 3: [1,2]}
| 对比 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n^2) | O(n + m) |
| 判断是否有边 | O(1) | O(degree) |
| 遍历邻居 | O(n) | O(degree) |
| 适用 | 稠密图 | 稀疏图(更常用) |
from collections import deque
def dfs(graph, start, visited=None):
"""深度优先搜索"""
if visited is None: visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
def bfs(graph, start):
"""广度优先搜索"""
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Dijkstra 算法求单源最短路径——从一个起点到其他所有点的最短距离。要求边权非负。
导航软件找最短路线的原理:从你的位置出发,每次都走当前"最近的未访问路口",逐步扩展,直到覆盖所有路口。
import heapq
def dijkstra(graph, start):
"""Dijkstra 最短路径 O((V+E) log V)"""
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # (距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in graph[u]: # (邻居, 权重)
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
# 带权图(邻接表)
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
print(dijkstra(graph, 'A')) # {'A':0, 'B':1, 'C':3, 'D':4}
最小生成树:用最少的边权总和连接所有节点。
def kruskal(n, edges):
"""Kruskal 最小生成树"""
edges.sort(key=lambda x: x[2]) # 按权重排序
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
mst_weight = 0
for u, v, w in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
mst_weight += w
return mst_weight
拓扑排序用于有向无环图(DAG)——把节点排成一个线性序列,使得所有边从前指向后。
大学里有些课有先修要求:学数据结构之前要学程序设计,学操作系统之前要学数据结构。拓扑排序就是找到一个合法的选课顺序。
from collections import deque, defaultdict
def topological_sort(num_courses, prerequisites):
"""拓扑排序(BFS / Kahn 算法)"""
graph = defaultdict(list)
in_degree = [0] * num_courses
for dest, src in prerequisites:
graph[src].append(dest)
in_degree[dest] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_courses else []
# 课程 0->1->2 的依赖关系
print(topological_sort(3, [[1,0], [2,1]])) # [0, 1, 2]
| 算法 | 时间(平均) | 时间(最坏) | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([5, 3, 8, 1, 2])) # [1, 2, 3, 5, 8]
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target: return i
return -1 # O(n)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: left = mid + 1
else: right = mid - 1
return -1
# 变体:查找第一个 >= target 的位置
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target: left = mid + 1
else: right = mid
return left
| 方法 | 时间 | 要求 | 适用场景 |
|---|---|---|---|
| 顺序查找 | O(n) | 无 | 无序小数组 |
| 二分查找 | O(log n) | 有序数组 | 有序大数组 |
| 哈希查找 | O(1) | 哈希表 | 频繁查找 |
| 树查找 | O(log n) | BST/平衡树 | 动态数据 |
分治(Divide and Conquer)的核心思想:把大问题拆成小问题,分别解决,再合并结果。
一个大蛋糕不好切?先切成两半,每半再切成两半……直到切成小块。每小块很容易处理。最后把结果拼起来。
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 分
right = merge_sort(arr[mid:]) # 分
return merge(left, right) # 合
def power(base, exp):
"""快速求 base^exp O(log exp)"""
if exp == 0: return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half # 分治
else:
return base * power(base, exp - 1)
print(power(2, 10)) # 1024
贪心算法的核心:每一步都选当前看起来最优的,不考虑全局,最终得到全局最优解。
吃自助餐的贪心策略:每道菜都挑最好吃的先吃。虽然不一定能吃到"全局最优组合",但在很多场景下效果很好。
def activity_selection(activities):
"""选择最多的不重叠活动"""
activities.sort(key=lambda x: x[1]) # 按结束时间排序
count = 0
last_end = 0
for start, end in activities:
if start >= last_end: # 贪心:选最早结束的
count += 1
last_end = end
return count
def find_content_children(children, cookies):
"""每个孩子分配一块饼干,求最多满足几个孩子"""
children.sort()
cookies.sort()
child = cookie = 0
while child < len(children) and cookie < len(cookies):
if cookies[cookie] >= children[child]:
child += 1 # 满足了这个孩子
cookie += 1
return child
回溯 = 试探 + 撤销。走一步试试,不行就退回来,换一条路继续试。
走迷宫时:选一条路走到底。遇到死胡同?退回来,换一条路。直到找到出口或所有路都试完。
def permute(nums):
"""生成全排列"""
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i, num in enumerate(remaining):
path.append(num)
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop() # 回溯:撤销选择
backtrack([], nums)
return result
print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
def solve_n_queens(n):
"""N 皇后问题"""
result = []
def backtrack(row, cols, diag1, diag2, board):
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
if col in cols or row-col in diag1 or row+col in diag2:
continue # 剪枝
board[row][col] = 'Q'
backtrack(row+1, cols|{col}, diag1|{row-col},
diag2|{row+col}, board)
board[row][col] = '.' # 回溯
backtrack(0, set(), set(), set(),
[['.']*n for _ in range(n)])
return result
动态规划(DP)的核心:把大问题拆成重叠子问题,记住子问题的解,避免重复计算。
普通递归就像闭卷考试:同一道题反复做。DP 就像开卷考试:做过的题记在笔记本上,下次直接查答案。
| 对比 | 贪心 | 回溯 | 动态规划 |
|---|---|---|---|
| 策略 | 每步选最优 | 穷举所有可能 | 记住子问题解 |
| 是否回退 | 不回退 | 回退 | 不回退 |
| 适用 | 局部最优=全局最优 | 需要穷举 | 最优子结构+重叠子问题 |
# 普通递归 O(2^n) —— 大量重复计算
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# 动态规划 O(n) —— 记住已算过的
def fib_dp(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空间优化 O(1)
def fib_opt(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def knapsack(weights, values, capacity):
"""0-1 背包问题"""
n = len(weights)
# dp[i][w] = 前 i 个物品、容量为 w 时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # 不选第 i 个
if w >= weights[i-1]:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
print(knapsack([2,3,4,5], [3,4,5,6], 8)) # 10
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[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]
print(lcs("abcde", "ace")) # 3 ("ace")
Trie 是一种专门处理字符串前缀的树结构,广泛用于搜索引擎自动补全、拼写检查。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
trie = Trie()
trie.insert("cat"); trie.insert("car")
print(trie.search("cat")) # True
print(trie.search("ca")) # False
并查集用于处理连通性问题:判断两个元素是否属于同一集合,合并两个集合。
一群人各自为派:A 和 B 结盟 → 合并为一派。C 和 D 结盟 → 合并为一派。问"A 和 C 是一派吗?"→ 查找他们各自的"帮主"。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
"""查找根节点(带路径压缩)"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""合并两个集合"""
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
def connected(self, x, y):
return self.find(x) == self.find(y)
uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3)
print(uf.connected(0, 1)) # True
print(uf.connected(0, 2)) # False
线段树用于区间查询和区间修改,支持 O(log n) 的区间求和、区间最大值等操作。
class SegmentTree:
"""线段树:区间求和"""
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
self._build(data, 2*node, start, mid)
self._build(data, 2*node+1, mid+1, end)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def query(self, left, right):
"""查询区间 [left, right] 的和 O(log n)"""
return self._query(1, 0, self.n-1, left, right)
def _query(self, node, start, end, left, right):
if right < start or end < left: return 0
if left <= start and end <= right: return self.tree[node]
mid = (start + end) // 2
return (self._query(2*node, start, mid, left, right) +
self._query(2*node+1, mid+1, end, left, right))
st = SegmentTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 3)) # 3+5+7 = 15
LRU(Least Recently Used)缓存淘汰最久没使用的数据。面试高频题!
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # 淘汰 key=2
print(cache.get(2)) # -1
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x):
self.stack_in.append(x)
def pop(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right: return root
return left or right
from collections import deque
def max_sliding_window(nums, k):
"""滑动窗口最大值(单调队列)"""
result = []
dq = deque() # 存下标,保持队列单调递减
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]
| 题目 | 数据结构 | 难度 |
|---|---|---|
| 有效的括号 | 栈 | 简单 |
| 合并两个有序链表 | 链表 | 简单 |
| 二叉树的最大深度 | 树 + 递归 | 简单 |
| 反转链表 | 链表 | 简单 |
| 两数之和 | 哈希表 | 简单 |
| 三数之和 | 排序 + 双指针 | 中等 |
| 岛屿数量 | DFS/BFS | 中等 |
| 课程表 | 拓扑排序 | 中等 |
| 最长递增子序列 | DP / 二分 | 中等 |
| 接雨水 | 双指针 / 栈 | 困难 |
| 最小覆盖子串 | 滑动窗口 | 困难 |
| 编辑距离 | DP | 中等 |
| 数据结构 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 栈 | O(n) | O(n) | O(1) | O(1) |
| 队列 | O(n) | O(n) | O(1) | O(1) |
| 哈希表 | - | O(1) | O(1) | O(1) |
| BST | O(log n) | O(log n) | O(log n) | O(log n) |
| 堆 | O(1)(堆顶) | O(n) | O(log n) | O(log n) |
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | O(n^2) | O(n^2) | O(1) | Yes |
| 插入 | O(n^2) | O(n^2) | O(1) | Yes |
| 归并 | O(n log n) | O(n log n) | O(n) | Yes |
| 快排 | O(n log n) | O(n^2) | O(log n) | No |
| 堆排 | O(n log n) | O(n log n) | O(1) | No |
# list —— 动态数组
lst = [1, 2, 3]
lst.append(4) # O(1)
lst.pop() # O(1)
lst[0] # O(1) 访问
# deque —— 双端队列
from collections import deque
dq = deque([1, 2, 3])
dq.append(4) # 右端入 O(1)
dq.popleft() # 左端出 O(1)
# dict —— 哈希表
d = {"a": 1}
d["a"] # O(1) 查找
d["b"] = 2 # O(1) 插入
# set —— 集合(哈希表)
s = {1, 2, 3}
s.add(4) # O(1)
3 in s # O(1) 查找
# heapq —— 最小堆
import heapq
heap = [3, 1, 2]
heapq.heapify(heap) # O(n)
heapq.heappush(heap, 0) # O(log n)
heapq.heappop(heap) # O(log n)
# defaultdict —— 带默认值的字典
from collections import defaultdict
dd = defaultdict(int)
dd["key"] += 1 # 自动初始化为 0