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 | 链表长了变慢 |
| 开放寻址法 | 冲突了找下一个空位 | 缓存友好 | 负载因子不能太高 |
class SimpleHashTable:
"""用链地址法解决冲突的哈希表"""
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
"""哈希函数:把 key 映射到桶下标"""
return hash(key) % self.capacity
def put(self, key, value):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # 更新
return
bucket.append((key, value)) # 新增
self.size += 1
# 负载因子超过阈值时扩容
if self.size > self.capacity * 0.75:
self._resize()
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
self.size -= 1
return
raise KeyError(key)
def _resize(self):
"""扩容:容量翻倍,重新哈希所有元素"""
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
# 使用示例
ht = SimpleHashTable()
ht.put("apple", 1); ht.put("banana", 2); ht.put("cherry", 3)
print(ht.get("apple")) # 1
ht.delete("banana")
print(ht.size) # 2
class OpenAddressHashTable:
"""开放寻址法(线性探测)解决冲突"""
EMPTY = object() # 空标记
DELETED = object() # 已删除标记
def __init__(self, capacity=16):
self.capacity = capacity
self.keys = [self.EMPTY] * capacity
self.values = [self.EMPTY] * capacity
self.size = 0
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
if self.size > self.capacity * 0.5: # 负载因子不能太高
self._resize()
idx = self._hash(key)
while self.keys[idx] is not self.EMPTY:
if self.keys[idx] == key:
self.values[idx] = value # 更新
return
idx = (idx + 1) % self.capacity # 线性探测:找下一个
self.keys[idx] = key
self.values[idx] = value
self.size += 1
def get(self, key):
idx = self._hash(key)
while self.keys[idx] is not self.EMPTY:
if self.keys[idx] == key:
return self.values[idx]
idx = (idx + 1) % self.capacity
raise KeyError(key)
def _resize(self):
old_keys, old_values = self.keys, self.values
self.capacity *= 2
self.keys = [self.EMPTY] * self.capacity
self.values = [self.EMPTY] * self.capacity
self.size = 0
for k, v in zip(old_keys, old_values):
if k is not self.EMPTY:
self.put(k, v)
# 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
# 自定义对象做键:需要实现 __hash__ 和 __eq__
class Point:
def __init__(self, x, y):
self.x = x; self.y = y
def __hash__(self):
return hash((self.x, self.y))
def __eq__(self, other):
return self.x == other.x and self.y == other.y
d = {Point(1, 2): "A", Point(3, 4): "B"}
print(d[Point(1, 2)]) # "A"
from collections import defaultdict
def group_anagrams(strs):
"""字母异位词分组"""
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # 排序后作为 key
groups[key].append(s)
return list(groups.values())
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# 优化:用字母计数作为 key,避免排序 O(m log m)
def group_anagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
def longest_consecutive(nums):
"""找出最长连续序列的长度"""
num_set = set(nums)
best = 0
for num in num_set:
# 只从序列起点开始计数
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
best = max(best, length)
return best
print(longest_consecutive([100, 4, 200, 1, 3, 2])) # 4 (1,2,3,4)
树是一种层次结构的数据结构。就像一棵倒着的树,根在上面,叶子在下面。
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
def delete_bst(root, val):
"""删除 BST 中值为 val 的节点(三种情况)"""
if not root: return None
if val < root.val:
root.left = delete_bst(root.left, val)
elif val > root.val:
root.right = delete_bst(root.right, val)
else:
# 找到目标节点,分三种情况
# 情况1:叶子节点 → 直接删除
if not root.left and not root.right:
return None
# 情况2:只有一个子节点 → 用子节点替换
if not root.left: return root.right
if not root.right: return root.left
# 情况3:有两个子节点 → 找右子树最小值替换
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = delete_bst(root.right, successor.val)
return root
# 演示
root = None
for v in [8, 3, 10, 1, 6, 14]:
root = insert_bst(root, v)
root = delete_bst(root, 3) # 删除节点 3
BST 可能退化成链表。平衡树通过自动调整,保证树的高度始终是 O(log n)。
| 对比 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡标准 | 严格(高度差 ≤ 1) | 宽松(最长路径 ≤ 2×最短) |
| 查找 | 更快(树更矮) | 稍慢 |
| 插入/删除 | 旋转次数多 | 旋转次数少 |
| 适用场景 | 查找密集 | 插入删除频繁 |
| 实际使用 | 数据库索引 | Java TreeMap、Linux 内核 |
AVL 树通过旋转来维持平衡。当插入或删除导致某节点的左右子树高度差 > 1 时,需要旋转。
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1 # 节点高度
class AVLTree:
def _height(self, node):
return node.height if node else 0
def _balance_factor(self, node):
"""平衡因子 = 左子树高度 - 右子树高度"""
return self._height(node.left) - self._height(node.right)
def _update_height(self, node):
node.height = 1 + max(self._height(node.left),
self._height(node.right))
def _rotate_right(self, z):
"""右旋"""
y = z.left
T3 = y.right
y.right = z
z.left = T3
self._update_height(z)
self._update_height(y)
return y
def _rotate_left(self, z):
"""左旋"""
y = z.right
T2 = y.left
y.left = z
z.right = T2
self._update_height(z)
self._update_height(y)
return y
def _rebalance(self, node):
"""检查并修复平衡"""
self._update_height(node)
bf = self._balance_factor(node)
# LL 型:左子树太高,右旋
if bf > 1 and self._balance_factor(node.left) >= 0:
return self._rotate_right(node)
# RR 型:右子树太高,左旋
if bf < -1 and self._balance_factor(node.right) <= 0:
return self._rotate_left(node)
# LR 型:先左旋左子树,再右旋
if bf > 1 and self._balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# RL 型:先右旋右子树,再左旋
if bf < -1 and self._balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def insert(self, root, val):
"""插入并自动平衡"""
if not root: return AVLNode(val)
if val < root.val:
root.left = self.insert(root.left, val)
elif val > root.val:
root.right = self.insert(root.right, val)
else:
return root # 重复值不插入
return self._rebalance(root)
def delete(self, root, val):
"""删除并自动平衡"""
if not root: return None
if val < root.val:
root.left = self.delete(root.left, val)
elif val > root.val:
root.right = self.delete(root.right, val)
else:
if not root.left: return root.right
if not root.right: return root.left
# 找后继
succ = root.right
while succ.left: succ = succ.left
root.val = succ.val
root.right = self.delete(root.right, succ.val)
return self._rebalance(root)
# 演示:按顺序插入不会退化
avl = AVLTree()
root = None
for v in [1, 2, 3, 4, 5, 6, 7]: # 顺序插入
root = avl.insert(root, v)
# 树仍然平衡,高度 O(log n),不会变成链表!
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
print(inorder(root)) # [1, 2, 3, 4, 5, 6, 7](有序)
红黑树是一种自平衡二叉搜索树,通过颜色标记和旋转规则来维持近似平衡。
# B 树插入过程演示(简化版,M=3)
# 插入序列:10, 20, 5, 6, 12, 30, 7, 17
# 步骤 1: [10]
# 步骤 2: [10, 20]
# 步骤 3: 插入 5 → 分裂 → [10]
# / \
# [5] [20]
# 步骤 4: 插入 6 → [10]
# / \
# [5,6] [20]
# 步骤 5: 插入 12 → [10]
# / \
# [5,6] [12,20]
# 步骤 6: 插入 30 → [10]
# / \
# [5,6] [12,20,30] → 满了!
# 分裂 → [10, 20]
# / | \
# [5,6] [12] [30]
# 核心思想:节点满了就分裂,保证所有叶子在同一层
堆是一种特殊的完全二叉树:最大堆中父节点 ≥ 子节点,最小堆中父节点 ≤ 子节点。
最大堆像公司:总经理 > 部门经理 > 普通员工。任何时候你都能快速找到"最大的那个"(堆顶)。
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
class MinHeap:
"""手写最小堆(理解 heapq 底层原理)"""
def __init__(self):
self.heap = []
def _sift_up(self, i):
"""上浮:插入元素后,向上调整到正确位置"""
while i > 0:
parent = (i - 1) // 2
if self.heap[i] < self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
i = parent
else:
break
def _sift_down(self, i):
"""下沉:删除堆顶后,向下调整到正确位置"""
n = len(self.heap)
while True:
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def push(self, val):
"""插入 O(log n)"""
self.heap.append(val)
self._sift_up(len(self.heap) - 1)
def pop(self):
"""弹出最小值 O(log n)"""
top = self.heap[0]
last = self.heap.pop()
if self.heap:
self.heap[0] = last
self._sift_down(0)
return top
def peek(self):
"""查看堆顶 O(1)"""
return self.heap[0]
h = MinHeap()
for x in [5, 3, 8, 1, 2]:
h.push(x)
print(h.pop()) # 1
print(h.pop()) # 2
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
mst_edges = []
for u, v, w in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
Prim 算法从一个起点出发,每次选最小的边扩展到新节点,适合稠密图。
import heapq
def prim(graph, n):
"""Prim 最小生成树(邻接表 + 优先队列)"""
visited = set()
min_heap = [(0, 0)] # (权重, 节点)
total_weight = 0
while len(visited) < n and min_heap:
w, u = heapq.heappop(min_heap)
if u in visited:
continue
visited.add(u)
total_weight += w
for v, weight in graph[u]:
if v not in visited:
heapq.heappush(min_heap, (weight, v))
return total_weight if len(visited) == n else -1
# 示例:无向带权图
graph = {
0: [(1, 2), (3, 6)],
1: [(0, 2), (2, 3), (3, 8), (4, 5)],
2: [(1, 3), (4, 7)],
3: [(0, 6), (1, 8)],
4: [(1, 5), (2, 7)]
}
print(prim(graph, 5)) # 最小生成树总权重 = 16
Dijkstra 不能处理负权边。Bellman-Ford 可以,还能检测负权环。
def bellman_ford(n, edges, start):
"""Bellman-Ford 最短路径(支持负权边)"""
dist = [float('inf')] * n
dist[start] = 0
# 松弛 V-1 次
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 第 V 次松弛:如果还能更新,说明有负权环
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # 存在负权环
return dist
# 示例:含负权边
edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 2)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 3]
Floyd 算法求任意两点之间的最短距离,代码极其简洁。
def floyd_warshall(n, graph):
"""Floyd-Warshall 全源最短路径 O(V^3)"""
# 初始化距离矩阵
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in graph:
dist[u][v] = w
# 核心:三重循环,枚举中间点
for k in range(n): # 中间点
for i in range(n): # 起点
for j in range(n): # 终点
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 示例:4 个节点的有向图
edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 3, 1), (3, 0, 5)]
dist = floyd_warshall(4, edges)
for row in dist:
print([x if x != float('inf') else '∞' for x in row])
# [0, 3, 5, 6]
# [7, 0, 2, 3]
# [6, 9, 0, 1]
# [5, 8, 10, 0]
拓扑排序用于有向无环图(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):
"""冒泡排序 O(n^2) —— 每次把最大的"冒泡"到末尾"""
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: break # 优化:没有交换说明已有序
return arr
def selection_sort(arr):
"""选择排序 O(n^2) —— 每次选最小的放到前面"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([5, 3, 8, 1, 2])) # [1, 2, 3, 5, 8]
def insertion_sort(arr):
"""插入排序 O(n^2) —— 像打扑克牌一样,把新牌插入已排序的手牌"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # 后移
j -= 1
arr[j+1] = key # 插入到正确位置
return arr
# 特点:对近乎有序的数组接近 O(n)!
print(insertion_sort([1, 2, 4, 3, 5])) # 几乎有序,很快
# 版本1:简洁写法(好理解,但需要额外空间)
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)
# 版本2:原地快排(面试常考,O(log n) 栈空间)
def quick_sort_inplace(arr, low=0, high=None):
"""原地快速排序,不需要额外数组"""
if high is None: high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
def partition(arr, low, high):
"""分区:选最后一个做 pivot,小的放左边,大的放右边"""
pivot = arr[high]
i = low - 1 # i 指向"小于区"的最后一个
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
arr = [5, 3, 8, 1, 2, 9, 4]
quick_sort_inplace(arr)
print(arr) # [1, 2, 3, 4, 5, 8, 9]
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
def upper_bound(arr, target):
"""查找第一个 > 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
def search_rotated(nums, target):
"""LeetCode 33:在旋转有序数组中查找"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return mid
# 判断哪半边有序
if nums[left] <= nums[mid]: # 左半边有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半边有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search_rotated([4,5,6,7,0,1,2], 0)) # 4
def find_peak(nums):
"""LeetCode 162:查找峰值(局部最大值)"""
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1 # 峰值在右边
else:
right = mid # 峰值在左边或就是 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 max_subarray_divide(nums):
"""LeetCode 53:分治法求最大子数组和 O(n log n)"""
def helper(l, r):
if l == r: return nums[l]
mid = (l + r) // 2
# 左半边最大
left_max = helper(l, mid)
# 右半边最大
right_max = helper(mid + 1, r)
# 跨越中点的最大
left_sum = float('-inf')
s = 0
for i in range(mid, l - 1, -1):
s += nums[i]
left_sum = max(left_sum, s)
right_sum = float('-inf')
s = 0
for i in range(mid + 1, r + 1):
s += nums[i]
right_sum = max(right_sum, s)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
return helper(0, len(nums) - 1)
print(max_subarray_divide([-2,1,-3,4,-1,2,1,-5,4])) # 6
import math
def closest_pair(points):
"""平面上最近点对的距离 O(n log n)"""
def dist(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def solve(px, py):
if len(px) <= 3:
return min(dist(px[i], px[j])
for i in range(len(px))
for j in range(i+1, len(px)))
mid = len(px) // 2
mid_x = px[mid][0]
left_px, right_px = px[:mid], px[mid:]
left_py = [p for p in py if p[0] <= mid_x]
right_py = [p for p in py if p[0] > mid_x]
d = min(solve(left_px, left_py), solve(right_px, right_py))
# 检查跨越分界线的点对
strip = [p for p in py if abs(p[0] - mid_x) < d]
for i in range(len(strip)):
for j in range(i+1, min(i+7, len(strip))):
d = min(d, dist(strip[i], strip[j]))
return d
px = sorted(points, key=lambda p: p[0])
py = sorted(points, key=lambda p: p[1])
return solve(px, py)
print(closest_pair([(2,3), (12,30), (40,50), (5,1), (12,10), (3,4)]))
# ≈ 1.41 (点 (2,3) 和 (3,4))
贪心算法的核心:每一步都选当前看起来最优的,不考虑全局,最终得到全局最优解。
吃自助餐的贪心策略:每道菜都挑最好吃的先吃。虽然不一定能吃到"全局最优组合",但在很多场景下效果很好。
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 can_jump(nums):
"""LeetCode 55:能否跳到最后一个位置"""
max_reach = 0
for i in range(len(nums)):
if i > max_reach: # 当前位置跳不到
return False
max_reach = max(max_reach, i + nums[i])
return True
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
def jump(nums):
"""LeetCode 45:跳到最后的最少步数"""
steps = 0
cur_end = 0 # 当前步能到达的最远
farthest = 0 # 下一步能到达的最远
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end: # 到达当前步的边界
steps += 1
cur_end = farthest
return steps
print(jump([2, 3, 1, 1, 4])) # 2
def merge_intervals(intervals):
"""LeetCode 56:合并所有重叠区间"""
intervals.sort(key=lambda x: x[0]) # 按起点排序
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # 重叠
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6], [8,10], [15,18]]
def find_min_arrows(points):
"""LeetCode 452:按右端点贪心"""
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for s, e in points[1:]:
if s > end: # 新箭
arrows += 1
end = e
return arrows
回溯 = 试探 + 撤销。走一步试试,不行就退回来,换一条路继续试。
走迷宫时:选一条路走到底。遇到死胡同?退回来,换一条路。直到找到出口或所有路都试完。
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
def subsets(nums):
"""LeetCode 78:生成所有子集"""
result = []
def backtrack(start, path):
result.append(path[:]) # 每个路径都是一个子集
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
def combination_sum(candidates, target):
"""LeetCode 39:找出所有和为 target 的组合(可重复使用)"""
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break # 剪枝
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i 不是 i+1,可重复
path.pop()
candidates.sort()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3], [7]]
def generate_parenthesis(n):
"""LeetCode 22:生成所有有效括号组合"""
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(path)
return
if open_count < n:
backtrack(path + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(path + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
print(generate_parenthesis(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']
动态规划(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")
def climb_stairs(n):
"""LeetCode 70:每次爬 1 或 2 阶,求方案数"""
if n <= 2: return n
a, b = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1):
a, b = b, a + b # dp[i] = dp[i-1] + dp[i-2]
return b
# 本质就是斐波那契数列!
print(climb_stairs(5)) # 8
def coin_change(coins, amount):
"""LeetCode 322:凑成 amount 最少需要多少硬币"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 凑 0 元需要 0 个硬币
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 2, 5], 11)) # 3 (5+5+1)
print(coin_change([2], 3)) # -1
def coin_change_ways(coins, amount):
"""凑成 amount 有多少种方案"""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
print(coin_change_ways([1, 2, 5], 5)) # 4
def lis_dp(nums):
"""LeetCode 300:O(n^2) DP 解法"""
n = len(nums)
dp = [1] * n # dp[i] = 以 nums[i] 结尾的 LIS 长度
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(lis_dp([10, 9, 2, 5, 3, 7, 101, 18])) # 4
def lis_binary(nums):
"""O(n log n) 二分查找优化"""
from bisect import bisect_left
tails = [] # tails[i] = 长度为 i+1 的递增子序列的最小末尾
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
print(lis_binary([10, 9, 2, 5, 3, 7, 101, 18])) # 4
def min_distance(word1, word2):
"""LeetCode 72:最少操作将 word1 变成 word2"""
m, n = len(word1), len(word2)
dp = [[0] * (n+1) for _ in range(m+1)]
# 边界:空串变成目标串需要的步数
for i in range(m+1): dp[i][0] = i # 全部删除
for j in range(n+1): dp[0][j] = j # 全部插入
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # 字符相同,不需要操作
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 删除
dp[i][j-1], # 插入
dp[i-1][j-1] # 替换
)
return dp[m][n]
print(min_distance("horse", "ros")) # 3
print(min_distance("intention", "execution")) # 5
def longest_palindrome(s):
"""LeetCode 5:中心扩展法 O(n^2)"""
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
best = ""
for i in range(len(s)):
odd = expand(i, i) # 奇数长度回文
even = expand(i, i+1) # 偶数长度回文
best = max(best, odd, even, key=len)
return best
print(longest_palindrome("babad")) # "bab" 或 "aba"
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
import mmh3 # 需要安装:pip install mmh3
from bitarray import bitarray # 需要安装:pip install bitarray
class BloomFilter:
def __init__(self, size, hash_count):
self.size = size # 位数组大小
self.hash_count = hash_count # 哈希函数个数
self.bit_array = bitarray(size)
self.bit_array.setall(0)
def add(self, item):
"""插入元素"""
for i in range(self.hash_count):
idx = mmh3.hash(item, i) % self.size
self.bit_array[idx] = 1
def contains(self, item):
"""查询元素是否存在"""
for i in range(self.hash_count):
idx = mmh3.hash(item, i) % self.size
if not self.bit_array[idx]:
return False # 一定不存在
return True # 可能存在(有误判概率)
# 使用示例
bf = BloomFilter(size=1000, hash_count=3)
bf.add("apple"); bf.add("banana")
print(bf.contains("apple")) # True
print(bf.contains("cherry")) # 大概率 False
# 简化版(不用第三方库)
class SimpleBloomFilter:
def __init__(self, size=1024, hash_count=3):
self.size = size
self.hash_count = hash_count
self.bits = [0] * size
def _hashes(self, item):
"""生成多个哈希值"""
results = []
for i in range(self.hash_count):
h = hash(item + str(i)) % self.size
results.append(h)
return results
def add(self, item):
for h in self._hashes(item):
self.bits[h] = 1
def contains(self, item):
return all(self.bits[h] for h in self._hashes(item))
跳表是 Redis 有序集合(ZSet)的底层数据结构。它通过多层索引来加速查找,实现简单,性能堪比平衡树。
import random
class SkipListNode:
def __init__(self, val=-1, level=0):
self.val = val
self.next = [None] * (level + 1) # 每层的下一个指针
class SkipList:
def __init__(self, max_level=16, p=0.5):
self.max_level = max_level
self.p = p
self.head = SkipListNode(-1, max_level)
self.level = 0 # 当前最高层
def _random_level(self):
"""随机决定节点层数"""
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def search(self, target):
"""查找 O(log n)"""
cur = self.head
for i in range(self.level, -1, -1): # 从最高层开始
while cur.next[i] and cur.next[i].val < target:
cur = cur.next[i]
cur = cur.next[0]
return cur and cur.val == target
def insert(self, val):
"""插入 O(log n)"""
update = [self.head] * (self.max_level + 1)
cur = self.head
for i in range(self.level, -1, -1):
while cur.next[i] and cur.next[i].val < val:
cur = cur.next[i]
update[i] = cur
new_level = self._random_level()
if new_level > self.level:
self.level = new_level
new_node = SkipListNode(val, new_level)
for i in range(new_level + 1):
new_node.next[i] = update[i].next[i]
update[i].next[i] = new_node
sl = SkipList()
for v in [3, 6, 7, 9, 12, 19, 21]:
sl.insert(v)
print(sl.search(7)) # True
print(sl.search(8)) # False
树状数组用于单点修改 + 前缀和查询,比线段树更简洁,常数更小。
class BIT:
"""树状数组:单点修改 + 前缀和查询,都是 O(log n)"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
"""在位置 i 增加 delta"""
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # 关键操作:lowbit
def query(self, i):
"""查询前缀和 [1, i]"""
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # 关键操作:lowbit
return s
def range_query(self, l, r):
"""查询区间和 [l, r]"""
return self.query(r) - self.query(l - 1)
# 示例
bit = BIT(10)
for i, v in enumerate([1, 3, 5, 7, 9, 2, 4, 6, 8, 10], 1):
bit.update(i, v)
print(bit.query(5)) # 1+3+5+7+9 = 25
print(bit.range_query(3, 7)) # 5+7+9+2+4 = 27
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]
def two_sum_sorted(nums, target):
"""LeetCode 167:有序数组两数之和"""
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left + 1, right + 1]
elif s < target: left += 1
else: right -= 1
def three_sum(nums):
"""LeetCode 15:三数之和(排序 + 双指针)"""
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # 跳过重复
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2], [-1,0,1]]
def length_of_longest_substring(s):
"""LeetCode 3:最长无重复子串"""
seen = {}
left = 0
best = 0
for right, c in enumerate(s):
if c in seen and seen[c] >= left:
left = seen[c] + 1 # 收缩左边界
seen[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring("abcabcbb")) # 3
def min_window(s, t):
"""LeetCode 76:最小覆盖子串"""
from collections import Counter
need = Counter(t)
missing = len(t) # 还需要匹配的字符数
left = 0
start, end = 0, float('inf')
for right, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1
while missing == 0: # 窗口已包含所有字符
if right - left < end - start:
start, end = left, right
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[start:end+1] if end != float('inf') else ""
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
def next_greater_element(nums):
"""LeetCode 496:下一个更大元素"""
n = len(nums)
result = [-1] * n
stack = [] # 存下标,栈中元素对应值单调递减
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
print(next_greater_element([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
def daily_temperatures(temps):
"""LeetCode 739:每天要等几天才升温"""
n = len(temps)
result = [0] * n
stack = []
for i in range(n):
while stack and temps[stack[-1]] < temps[i]:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
from collections import deque
def level_order(root):
"""LeetCode 102:二叉树层序遍历"""
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
def oranges_rotting(grid):
"""LeetCode 994:腐烂的橘子(多源 BFS)"""
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: queue.append((r, c, 0))
elif grid[r][c] == 1: fresh += 1
minutes = 0
while queue:
r, c, minutes = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, minutes + 1))
return minutes if fresh == 0 else -1
| 题目 | 数据结构/模式 | 难度 |
|---|---|---|
| 有效的括号 | 栈 | 简单 |
| 合并两个有序链表 | 链表 | 简单 |
| 二叉树的最大深度 | 树 + 递归 | 简单 |
| 反转链表 | 链表 | 简单 |
| 两数之和 | 哈希表 | 简单 |
| 三数之和 | 排序 + 双指针 | 中等 |
| 岛屿数量 | DFS/BFS | 中等 |
| 课程表 | 拓扑排序 | 中等 |
| 最长递增子序列 | DP / 二分 | 中等 |
| 接雨水 | 双指针 / 栈 | 困难 |
| 最小覆盖子串 | 滑动窗口 | 困难 |
| 编辑距离 | DP | 中等 |
| 最长无重复子串 | 滑动窗口 | 中等 |
| 下一个更大元素 | 单调栈 | 中等 |
| 腐烂的橘子 | 多源 BFS | 中等 |
| 单词接龙 | BFS | 困难 |
| 最大子数组和 | Kadane / DP | 中等 |
| 合并 K 个有序链表 | 分治 / 堆 | 困难 |
| 数据结构 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | 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
| 算法 | 用途 | 时间复杂度 | 条件 |
|---|---|---|---|
| DFS | 遍历、路径搜索、连通分量 | O(V+E) | 通用 |
| BFS | 最短路径(无权)、层序遍历 | O(V+E) | 通用 |
| Dijkstra | 单源最短路径 | O((V+E)logV) | 非负权 |
| Bellman-Ford | 单源最短路径 | O(V×E) | 支持负权 |
| Floyd-Warshall | 全源最短路径 | O(V³) | 通用 |
| Prim | 最小生成树 | O((V+E)logV) | 稠密图优 |
| Kruskal | 最小生成树 | O(E log E) | 稀疏图优 |
| 拓扑排序 | DAG 线性排序 | O(V+E) | 必须 DAG |
| 并查集 | 连通性判断 | ≈O(1) | 合并/查询 |