贪心算法原理
贪心算法在每一步选择当前看起来最优的选项（局部最优），希望由此导致全局最优。
贪心不总是正确的贪心策略不是万能的。需要证明局部最优选择不会影响未来决策，才能保证全局最优。常用的证明方法：贪心选择性质（交换论证）、归纳法。
贪心 vs 动态规划
| 方面 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每步做一个不可回头的选择 | 枚举所有可能，取最优 |
| 正确性 | 需要证明贪心选择性质 | 只要子结构最优，就正确 |
| 效率 | 通常更高效（O(n log n) 或 O(n)） | 通常需要 O(n²) 或更高 |
| 适用 | 活动选择、霍夫曼编码 | 背包问题、编辑距离 |
经典贪心题目
活动选择问题（区间调度）
给定 n 个活动，每个活动有开始时间和结束时间。选择尽可能多的互不重叠的活动。
def activity_selection(intervals):
# 贪心策略：每次选结束时间最早的活动（为后续活动留最多时间）
intervals.sort(key=lambda x: x[1]) # 按结束时间排序
selected = []
last_end = -float('inf')
for start, end in intervals:
if start >= last_end: # 不与上一个活动重叠
selected.append((start, end))
last_end = end
return selected
# 示例
acts = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11)]
print(activity_selection(acts))
# [(1,4), (5,7), (8,11)] — 3 个活动跳跃游戏
def can_jump(nums: list) -> bool:
# 贪心：维护当前能到达的最远位置
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: # 当前位置不可达
return False
max_reach = max(max_reach, i + jump)
return True
def jump_min_steps(nums: list) -> int:
"""跳跃游戏 II：最少跳几次到达末尾"""
jumps = curr_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == curr_end: # 到达当前跳的边界，必须跳
jumps += 1
curr_end = farthest
return jumps分发饼干
def find_content_children(g: list, s: list) -> int:
# g[i]: 第 i 个孩子的胃口；s[j]: 第 j 块饼干的尺寸
# 贪心：用最小的够吃的饼干满足胃口最小的孩子
g.sort(); s.sort()
i = j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]: # 这块饼干能满足这个孩子
i += 1
j += 1
return i # 满足的孩子数Huffman 编码思路
Huffman 编码是一种贪心算法，给高频字符分配短编码，低频字符分配长编码，实现无损压缩。
import heapq
def build_huffman(freq_dict):
"""构建 Huffman 树，返回各字符的编码"""
# 每次取频率最小的两棵树合并（贪心选择：最小代价先合并）
heap = [(freq, char) for char, freq in freq_dict.items()]
heapq.heapify(heap)
while len(heap) > 1:
f1, c1 = heapq.heappop(heap) # 最小频率
f2, c2 = heapq.heappop(heap) # 次小频率
merged = (f1 + f2, (c1, c2)) # 合并为新节点
heapq.heappush(heap, merged)
return heap[0] # 返回 Huffman 树根回溯算法框架
回溯是一种系统化穷举的算法：在所有可能的选择中尝试每一条路径，遇到不满足条件的情况就"回溯"撤销选择，尝试下一条路径。
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径.copy()) # 记录结果
return
for 选择 in 选择列表:
if 不满足约束条件: # 剪枝
continue
做选择 # 将选择加入路径
backtrack(路径, 新的选择列表)
撤销选择 # 恢复现场（关键！）排列问题：全排列
# 无重复元素的全排列
def permute(nums: list) -> list:
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:]) # 注意要复制！
return
for i, x in enumerate(remaining):
path.append(x)
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop() # 撤销选择
backtrack([], nums)
return result
# 含重复元素的全排列（去重）
def permute_unique(nums: list) -> list:
result = []
nums.sort() # 排序，让相同元素相邻
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: continue
# 跳过重复：同一层选择中，相同值只取第一次出现的
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result组合问题
# 组合总和（元素可重复使用）
def combination_sum(candidates, 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
# 电话号码字母组合
def letter_combinations(digits: str) -> list:
if not digits: return []
phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
result = []
def backtrack(idx, path):
if idx == len(digits):
result.append(''.join(path))
return
for ch in phone[digits[idx]]:
path.append(ch)
backtrack(idx + 1, path)
path.pop()
backtrack(0, [])
return result子集问题
def subsets(nums: list) -> list:
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
# n 个元素共有 2^n 个子集
# 示例：subsets([1,2,3]) → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]N 皇后
在 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后不在同一行、同一列、同一对角线。
def solve_n_queens(n: int) -> list:
result = []
board = [['.'] * n for _ in range(n)]
cols = set() # 已被占用的列
diag1 = set() # 已被占用的左上-右下对角线（row - col 相同）
diag2 = set() # 已被占用的右上-左下对角线（row + col 相同）
def backtrack(row):
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'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# 递归下一行
backtrack(row + 1)
# 撤销选择
board[row][col] = '.'
cols.discard(col)
diag1.discard(row - col)
diag2.discard(row + col)
backtrack(0)
return result
# n=4 有 2 个解，n=8 有 92 个解数独求解器
def solve_sudoku(board) -> None:
def is_valid(row, col, num):
char = str(num)
# 检查行
if char in board[row]: return False
# 检查列
if any(board[r][col] == char for r in range(9)): return False
# 检查 3×3 方块
br, bc = 3 * (row // 3), 3 * (col // 3)
for r in range(br, br+3):
for c in range(bc, bc+3):
if board[r][c] == char: return False
return True
def backtrack() -> bool:
for row in range(9):
for col in range(9):
if board[row][col] != '.': continue # 跳过已填
for num in range(1, 10):
if is_valid(row, col, num):
board[row][col] = str(num)
if backtrack():
return True # 找到解
board[row][col] = '.' # 撤销
return False # 1-9 都不行，回溯
return True # 所有格子填满，成功
backtrack()回溯剪枝技巧
1. 约束传播：提前排除无效选项（如 N 皇后用 set 记录冲突）
2. 排序优先：先尝试最有可能成功的选择（fail-first 原则）
3. 可行性剪枝：当剩余元素不够组成答案时提前退出（如组合总和检查超出）
4. 最优性剪枝：当当前路径不可能比已知最优解更好时剪枝
恭喜完成全部10章！
你已经学习了算法与数据结构的全貌：
复杂度分析 → 数组/字符串 → 链表 → 栈/队列 → 哈希表 → 树 → 图 → 排序 → 动态规划 → 贪心/回溯
下一步：在 LeetCode 上按专题练习，每道题都先尝试独立思考，再对照这里的框架分析。