1. 为什么我们需要一个算法刷题本？

作为一名从ACM竞赛转战工业界的算法工程师，我深刻理解系统化刷题的重要性。很多初学者会陷入"刷了就忘"的困境，这正是我设计这个算法刷题本的初衷。不同于普通的刷题记录，这个刷题本整合了题目解析、代码实现和知识点串联三大功能模块。

在实际面试中，01背包问题及其变种出现的频率高达37%（根据2023年LeetCode企业题库统计）。但大多数求职者只是机械记忆模板，当遇到"分割等和子集"这类变形题时就会束手无策。我的刷题本特别强调问题变形和举一反三的能力培养。

关键认知：刷题不是目的，建立算法思维模型才是核心。一个题目在刷题本中的完整记录应该包含：暴力解法→优化思路→最终方案→相似题型对比这四大要素。

2. 刷题本的核心架构设计

2.1 题目分类体系

我采用三维分类法：

1. 算法类型：动态规划(DP)、图论、搜索等
2. 难度等级：按企业面试频率划分而非OJ标称难度
3. 解题模式：模板题/变形题/组合题

例如01背包问题会标记为：

[DP][高频][模板]

这种分类方式来自我面试300+候选人的经验总结。企业面试中，DFS/BFS的实际考察频率是ACM竞赛的2.3倍，而高级数据结构如红黑树的考察率不足5%。

2.2 题目解析模块

每个题目的解析包含：

## 322. 零钱兑换 ### 问题重述 （用面试场景的语言重新表述问题） ### 暴力解法 - 时间复杂度：O(S^n) - 空间复杂度：O(n) - 代码实现：（展示完整可运行代码） ### DP优化思路 1. 状态定义：dp[i]表示金额i的最小硬币数 2. 转移方程：dp[i] = min(dp[i], dp[i-coin]+1) 3. 边界条件：dp[0]=0 ### 常见面试变种 - 求方案数（完全背包问题） - 硬币限量（多重背包问题） - 输出具体方案（增加path数组） ### 企业真题变形 2023年字节跳动面试题：给定货币面值，判断能否恰好支付某金额（存在性判断）

2.3 代码实现规范

所有代码遵循：

1. 工业级编码规范（含防御性编程）
2. 多语言实现（Python/Java/C++）
3. 测试用例设计技巧

例如01背包的Python实现：

def knapsack(weights, values, capacity): """ :type weights: List[int] :type values: List[int] :type capacity: int :rtype: int """ n = len(weights) dp = [[0]*(capacity+1) for _ in range(n+1)] for i in range(1, n+1): for w in range(1, capacity+1): if weights[i-1] <= w: dp[i][w] = max( dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1] ) else: dp[i][w] = dp[i-1][w] return dp[n][capacity] # 测试用例设计要点： # 1. 空背包特殊情况 # 2. 超重物品边界情况 # 3. 价值全相同的情况

3. 动态规划专题精讲（以01背包为例）

3.1 标准模板解析

01背包问题的四步分析法：

1. 状态定义：dp[i][w]表示前i件物品放入容量w的背包的最大价值
2. 初始化：dp[0][...] = 0（零物品情况）
3. 状态转移：基于物品选/不选两种情况
4. 结果提取：dp[n][capacity]

3.2 空间优化技巧

将二维DP优化为一维的关键点：

def knapsack(weights, values, capacity): dp = [0]*(capacity+1) for i in range(len(weights)): for w in range(capacity, weights[i]-1, -1): # 逆序遍历是关键 dp[w] = max(dp[w], dp[w-weights[i]]+values[i]) return dp[capacity]

易错点：正序遍历会导致物品被重复计算（变成完全背包问题）

3.3 常见变形题攻略

3.3.1 分割等和子集（LeetCode 416）

def canPartition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False]*(target+1) dp[0] = True for num in nums: for i in range(target, num-1, -1): dp[i] = dp[i] or dp[i-num] return dp[target]

3.3.2 最后一块石头的重量 II（LeetCode 1049）

问题转化为：将石头分成两堆，使两堆重量差最小

def lastStoneWeightII(stones): total = sum(stones) target = total // 2 dp = [False]*(target+1) dp[0] = True for stone in stones: for i in range(target, stone-1, -1): dp[i] = dp[i] or dp[i-stone] for i in range(target, -1, -1): if dp[i]: return total - 2*i return 0

4. 刷题本的高级应用技巧

4.1 错题本功能设计

我建议为每个错题记录：

1. 首次错误原因（分类标签）：
   • 思路错误（算法选择不当）
   • 实现错误（边界条件遗漏）
   • 优化不足（时间复杂度高）
2. 重刷时间表（基于艾宾浩斯遗忘曲线）

4.2 企业面试真题分析

以2023年Google面试题为例：

给定物品列表和背包容量，求恰好装满背包的方案数

解法对比：

1. 标准01背包：求最大价值
2. 变形解法：将max改为sum，初始化dp[0]=1

4.3 代码模板速查表

动态规划通用解题框架：

def dp_template(inputs): # 1. 定义dp数组 dp = [ ... ] # 2. 初始化基础情况 dp[0] = ... # 3. 状态转移 for i in range(...): for j in range(...): dp[i][j] = ... # 状态转移方程 # 4. 返回结果 return dp[...]

5. 刷题计划制定方法论

5.1 阶段式学习路径

根据我的培训经验，建议按以下顺序攻坚：

1. 基础阶段（2周）：

   • 线性DP（70%）
   • 基础DFS/BFS（30%）

2. 进阶阶段（3周）：

   • 背包问题（40%）
   • 二叉树（30%）
   • 二分查找（30%）

3. 冲刺阶段（2周）：

   • 图论算法（50%）
   • 复杂DP（50%）

5.2 每日刷题配比

高效训练方案：

• 新题：3道（按当前阶段重点）
• 旧题：2道（从错题本抽取）
• 时间分配：
  • 思考：每道题≤30分钟
  • 看题解：≤15分钟
  • 代码实现：≤20分钟

5.3 效率监测指标

建议跟踪这些核心指标：

1. 首次通过率（反映思维严谨度）
2. 最优解率（反映算法掌握度）
3. 重刷正确率（反映记忆牢固度）

我设计的刷题本包含自动统计功能，可以生成如下训练报告：

本周训练报告： - 动态规划专题：85%通过率 - 图论专题：62%通过率（需加强） - 平均思考时间：25分钟（优于80%用户）

6. 工业级代码优化技巧

6.1 防御性编程实践

在面试中展示专业性的关键细节：

def binary_search(nums, target): if not nums: # 空数组检查 return -1 left, right = 0, len(nums)-1 while left <= right: # 等号处理边界条件 mid = left + (right-left)//2 # 避免溢出 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 明确返回未找到

6.2 测试用例设计原则

覆盖这些关键场景：

1. 空输入
2. 极值测试
3. 重复元素
4. 有序/无序边界
5. 性能边界（大数据量）

例如测试快速排序：

test_cases = [ ([], []), # 空数组 ([1], [1]), # 单元素 ([1,1,1], [1,1,1]), # 全重复 ([3,1,4,2], [1,2,3,4]), # 普通情况 (list(range(10**5,0,-1)), list(range(1,10**5+1))) # 大数据量 ]

6.3 复杂度优化实战

从O(n²)到O(nlogn)的经典案例 - 最长递增子序列：

# 标准DP解法 O(n²) def lengthOfLIS(nums): dp = [1]*len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j]+1) return max(dp) if dp else 0 # 优化解法 O(nlogn) import bisect def lengthOfLIS(nums): tails = [] for num in nums: idx = bisect.bisect_left(tails, num) if idx == len(tails): tails.append(num) else: tails[idx] = num return len(tails)

7. 高频算法题型深度剖析

7.1 二叉树专题

7.1.1 迭代式中序遍历模板

def inorderTraversal(root): res = [] stack = [] curr = root while curr or stack: while curr: # 深入左子树 stack.append(curr) curr = curr.left curr = stack.pop() res.append(curr.val) curr = curr.right # 转向右子树 return res

7.1.2 最近公共祖先（LCA）问题

def lowestCommonAncestor(root, p, q): if not root or root == p or root == q: return root left = lowestCommonAncestor(root.left, p, q) right = lowestCommonAncestor(root.right, p, q) if left and right: # p和q分布在两侧 return root return left if left else right # 返回非空的一侧

7.2 图论算法精要

7.2.1 Dijkstra算法实现

import heapq def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 heap = [(0, start)] while heap: current_dist, current_node = heapq.heappop(heap) if current_dist > distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(heap, (distance, neighbor)) return distances

7.2.2 拓扑排序检测环

def canFinish(numCourses, prerequisites): indegree = [0]*numCourses adj = [[] for _ in range(numCourses)] for dest, src in prerequisites: adj[src].append(dest) indegree[dest] += 1 queue = [i for i in range(numCourses) if indegree[i] == 0] count = 0 while queue: node = queue.pop() count += 1 for neighbor in adj[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) return count == numCourses

8. 刷题本的扩展应用

8.1 面试模拟系统

我建议在刷题本中添加：

1. 白板编程模式（限时无IDE）
2. 语音解释功能（模拟面试陈述）
3. 面试官视角评估（按大厂评分标准）

8.2 知识图谱构建

将题目关联成知识网络：

动态规划 → 背包问题 → 01背包 → 分割等和子集 ↳ 最长公共子序列 → 编辑距离

8.3 个性化推荐算法

基于以下维度推荐题目：

1. 历史薄弱环节
2. 目标公司高频考点
3. 知识体系完整性

我的刷题本采用协同过滤算法，为每个用户生成独特的训练路径。例如对DP薄弱但图论较强的用户，会推荐更多区间DP和树形DP题目来补齐短板。