学习路线与刷题指南

第四十三章：学习路线与刷题指南

你决定系统学习算法。打开 LeetCode，看到 3000+ 道题，第一反应是："从哪开始？"

这种"选择瘫痪"比题目本身更消耗你的精力。本章的目标是消除这种不确定性：给你一条清晰的路线，从"完全零基础"到"能通过顶级公司面试"，再到"可以参加竞赛"。每个阶段有明确的题目列表、时间规划、和衡量标准。

更重要的是，本章要解决一个很多刷题者忽略的问题：如何从"会做题"到"写出工程代码"。面试只是入职的门槛；入职后，你写的代码需要被同事 review、需要跑在生产环境、需要三年后仍然可维护。算法能力和工程能力之间有一座桥，本章帮你走过去。

Level 1 · 你需要知道的

1.1 按难度分级的刷题路线

阶段一：入门（0-2 个月，目标 50 题）

前置条件： 会一门编程语言的基本语法（循环、条件、函数、数组）

目标： 建立"问题→数据结构"的基本映射，能解出 Easy 题

入门阶段的核心原则：

# 原则 1：每道题限时 30 分钟
# 如果 30 分钟想不出来，看题解。不丢人。
# 入门阶段的目标是"见过"，不是"自己想出"

# 原则 2：看完题解后必须自己重写一遍
# 不看题解，打开空白编辑器，凭理解写出来
# 如果写不出来，说明你只是"看懂了"而不是"学会了"

# 原则 3：分类刷题，不要随机
# 连续做 5-8 道同类题，建立模式感
# 随机刷题相当于每次都在"冷启动"

def beginner_workflow(problem):
    """入门阶段的做题流程"""
    # 1. 读题，画例子
    understand(problem)
    
    # 2. 想 5 分钟：这道题像之前做过的哪道？
    pattern = try_match(problem, time_limit=5)
    
    # 3. 如果有思路，尝试实现（限时 25 分钟）
    if pattern:
        solution = implement(pattern, time_limit=25)
    else:
        # 4. 没思路？直接看题解
        solution = read_editorial(problem)
    
    # 5. 无论是否看了题解，都要做这一步：
    # 关闭题解，自己从头写一遍
    rewrite_from_memory(solution)
    
    # 6. 记录：这道题的题型是什么？关键 insight 是什么？
    note = {
        "题型": pattern,
        "关键洞察": "...",
        "我卡在哪": "...",
        "复习日期": today + timedelta(days=3),  # 间隔重复
    }

阶段二：中级（2-4 个月，目标 150 题）

前置条件： 入门阶段完成，Easy 解出率 > 80%

目标： 能独立解出大部分 Medium 题，掌握所有常见算法模式

中级阶段的核心原则：

# 原则 1：限时 45 分钟（模拟面试）
# 如果 45 分钟做不出来，说明你对这个题型的模式还不够熟

# 原则 2：做完后优化
# Easy 的解法不够，要追问自己：能不能更快？能不能更省空间？

# 原则 3：周复习
# 每周末花 2 小时复习本周做错/看过题解的题
# 不复习 = 浪费 70% 的刷题时间

def intermediate_workflow(problem):
    """中级阶段的做题流程"""
    # 1. 限时 45 分钟独立解题
    start = time.now()
    solution = solve_independently(problem, time_limit=45)
    
    # 2. 如果解出：
    if solution.is_correct():
        # 对比最优解 — 自己的解法是最优的吗？
        optimal = read_editorial(problem)
        if solution.complexity > optimal.complexity:
            # 学习优化技巧
            learn_optimization(solution, optimal)
    
    # 3. 如果没解出：
    else:
        # 只看提示，不看完整题解
        hint = get_hint(problem)  # "试试用动态规划" or "用单调栈"
        solution = retry_with_hint(problem, hint, time_limit=20)
        
        if not solution.is_correct():
            # 看完整题解 + 自己重写
            editorial = read_editorial(problem)
            rewrite_from_memory(editorial)
    
    # 4. 分析总结
    analysis = {
        "题型": identify_pattern(problem),
        "我的解法": solution.approach,
        "最优解法": optimal.approach if optimal else solution.approach,
        "差距原因": "...",
        "下次看到类似题，第一反应应该是": "...",
    }

阶段三：高级（4-6 个月，目标 250+ 题）

前置条件： Medium 解出率 > 70%（45 分钟内）

目标： 能解出 Hard 题，掌握高级数据结构和算法

阶段四：竞赛（6+ 个月）

前置条件： Hard 解出率 > 50%

目标： LeetCode 周赛稳定全国前 5%，或 Codeforces Rating > 1800

竞赛阶段的训练方式不同于面试准备：

COMPETITION_TRAINING = {
    "训练频率": "每天 1-2 小时 + 每周参加至少 1 场比赛",
    "训练内容": {
        "虚拟比赛": "在 LeetCode/Codeforces 上模拟比赛环境",
        "专项突破": "针对弱项集中训练（如 DP 专场、图论专场）",
        "补题": "赛后把没做出的题全部补完并理解",
    },
    "竞赛特有技能": [
        "快速码代码（模板预备）",
        "精确估计复杂度（1-2秒内判断可行性）",
        "数学推导能力",
        "处理大数据（取模、防溢出）",
    ],
    "面试用途": "竞赛经历在 Google/Meta 等公司非常加分",
}

1.2 精选题目清单（200 题）

以下清单基于 Blind75、NeetCode150、Grind75 的交集，按本书章节重新组织。每道题标注难度（E/M/H）和面试频率（1-5星）。

数组与双指针（20 题）

ARRAY_TWO_POINTERS = [
    # (题号, 题名, 难度, 频率, 关键技巧)
    (1,    "Two Sum",                    "E", "★★★★★", "哈希表 O(n)"),
    (15,   "3Sum",                       "M", "★★★★★", "排序+对撞指针"),
    (11,   "Container With Most Water",  "M", "★★★★",  "对撞指针+贪心"),
    (42,   "Trapping Rain Water",        "H", "★★★★★", "双指针/单调栈/DP"),
    (26,   "Remove Duplicates",          "E", "★★★",   "同向双指针"),
    (283,  "Move Zeroes",                "E", "★★★★",  "同向双指针"),
    (167,  "Two Sum II (Sorted)",        "M", "★★★",   "对撞指针"),
    (125,  "Valid Palindrome",           "E", "★★★",   "对撞指针"),
    (238,  "Product Except Self",        "M", "★★★★",  "前缀积/后缀积"),
    (53,   "Maximum Subarray",           "M", "★★★★★", "Kadane/前缀和"),
    (121,  "Best Time Buy/Sell Stock",   "E", "★★★★★", "维护前缀最小"),
    (152,  "Maximum Product Subarray",   "M", "★★★★",  "同时记录最大最小"),
    (33,   "Search Rotated Array",       "M", "★★★★★", "变形二分"),
    (153,  "Find Min Rotated Array",     "M", "★★★★",  "二分"),
    (4,    "Median of Two Sorted",       "H", "★★★★",  "二分 O(log(m+n))"),
    (54,   "Spiral Matrix",              "M", "★★★",   "模拟+边界"),
    (48,   "Rotate Image",               "M", "★★★",   "转置+翻转"),
    (73,   "Set Matrix Zeroes",          "M", "★★★",   "用首行首列标记"),
    (128,  "Longest Consecutive Seq",    "M", "★★★★",  "哈希集合"),
    (56,   "Merge Intervals",            "M", "★★★★★", "排序+合并"),
]

滑动窗口（10 题）

SLIDING_WINDOW = [
    (3,    "Longest Substring No Repeat", "M", "★★★★★", "哈希集合+收缩"),
    (76,   "Minimum Window Substring",    "H", "★★★★★", "哈希计数+收缩"),
    (424,  "Longest Repeating Replacement","M", "★★★★",  "定长思维"),
    (567,  "Permutation in String",        "M", "★★★★",  "定长窗口+计数"),
    (209,  "Min Size Subarray Sum",        "M", "★★★",   "变长窗口"),
    (904,  "Fruit Into Baskets",           "M", "★★★",   "最多 k 种字符"),
    (438,  "Find All Anagrams",            "M", "★★★★",  "定长窗口+计数"),
    (30,   "Substring Concat Words",       "H", "★★★",   "定长窗口"),
    (239,  "Sliding Window Maximum",       "H", "★★★★",  "单调队列"),
    (395,  "Longest Substr K Repeating",   "M", "★★★",   "分治/窗口"),
]

链表（10 题）

LINKED_LIST = [
    (206,  "Reverse Linked List",          "E", "★★★★★", "三指针迭代"),
    (21,   "Merge Two Sorted Lists",       "E", "★★★★★", "虚拟头+比较"),
    (141,  "Linked List Cycle",            "E", "★★★★★", "快慢指针"),
    (142,  "Linked List Cycle II",         "M", "★★★★",  "快慢+数学"),
    (19,   "Remove Nth From End",          "M", "★★★★",  "快慢指针"),
    (143,  "Reorder List",                 "M", "★★★★",  "找中点+反转+合并"),
    (23,   "Merge K Sorted Lists",         "H", "★★★★★", "堆/分治"),
    (25,   "Reverse Nodes k-Group",        "H", "★★★★",  "分组反转"),
    (138,  "Copy List Random Pointer",     "M", "★★★★",  "哈希/交织"),
    (148,  "Sort List",                    "M", "★★★",   "归并排序"),
]

栈与队列（10 题）

STACK_QUEUE = [
    (20,   "Valid Parentheses",            "E", "★★★★★", "栈匹配"),
    (155,  "Min Stack",                    "M", "★★★★",  "辅助栈"),
    (150,  "Eval Reverse Polish",          "M", "★★★",   "栈计算"),
    (739,  "Daily Temperatures",           "M", "★★★★",  "单调递减栈"),
    (84,   "Largest Rect Histogram",       "H", "★★★★★", "单调栈"),
    (496,  "Next Greater Element I",       "E", "★★★",   "单调栈+哈希"),
    (503,  "Next Greater Element II",      "M", "★★★",   "单调栈+循环"),
    (394,  "Decode String",                "M", "★★★★",  "栈/递归"),
    (232,  "Implement Queue using Stacks", "E", "★★★",   "双栈"),
    (85,   "Maximal Rectangle",            "H", "★★★★",  "单调栈+前缀"),
]

树（20 题）

TREES = [
    (104,  "Maximum Depth",                "E", "★★★★★", "递归/BFS"),
    (226,  "Invert Binary Tree",           "E", "★★★★",  "递归"),
    (100,  "Same Tree",                    "E", "★★★",   "递归比较"),
    (572,  "Subtree of Another Tree",      "E", "★★★",   "递归+相同判断"),
    (102,  "Level Order Traversal",        "M", "★★★★★", "BFS"),
    (105,  "Construct from Pre+In",        "M", "★★★★",  "递归分治"),
    (230,  "Kth Smallest in BST",          "M", "★★★★",  "中序遍历"),
    (98,   "Validate BST",                 "M", "★★★★★", "中序/范围递归"),
    (235,  "LCA of BST",                   "M", "★★★★",  "BST 性质"),
    (236,  "LCA of Binary Tree",           "M", "★★★★★", "后序递归"),
    (124,  "Binary Tree Max Path Sum",     "H", "★★★★★", "后序+全局变量"),
    (297,  "Serialize/Deserialize",        "H", "★★★★",  "BFS/前序"),
    (543,  "Diameter of Binary Tree",      "E", "★★★★",  "后序深度"),
    (199,  "Right Side View",              "M", "★★★★",  "BFS 每层最后"),
    (114,  "Flatten to Linked List",       "M", "★★★",   "后序/Morris"),
    (437,  "Path Sum III",                 "M", "★★★★",  "前缀和+DFS"),
    (208,  "Implement Trie",               "M", "★★★★★", "字典树"),
    (211,  "Add/Search Word",              "M", "★★★★",  "Trie+DFS"),
    (212,  "Word Search II",               "H", "★★★★",  "Trie+回溯"),
    (295,  "Find Median Data Stream",      "H", "★★★★★", "双堆"),
]

图（15 题）

GRAPH = [
    (200,  "Number of Islands",            "M", "★★★★★", "BFS/DFS"),
    (133,  "Clone Graph",                  "M", "★★★★",  "BFS/DFS+哈希"),
    (695,  "Max Area of Island",           "M", "★★★★",  "DFS"),
    (417,  "Pacific Atlantic Water",       "M", "★★★★",  "反向 BFS"),
    (207,  "Course Schedule",              "M", "★★★★★", "拓扑排序"),
    (210,  "Course Schedule II",           "M", "★★★★",  "拓扑+输出序列"),
    (261,  "Graph Valid Tree",             "M", "★★★★",  "并查集/BFS"),
    (323,  "Connected Components",         "M", "★★★",   "并查集/DFS"),
    (127,  "Word Ladder",                  "H", "★★★★",  "BFS"),
    (269,  "Alien Dictionary",             "H", "★★★★",  "拓扑排序"),
    (743,  "Network Delay Time",           "M", "★★★★",  "Dijkstra"),
    (787,  "Cheapest Flights K Stops",     "M", "★★★★",  "BFS/Bellman-Ford"),
    (332,  "Reconstruct Itinerary",        "H", "★★★",   "Hierholzer"),
    (684,  "Redundant Connection",         "M", "★★★★",  "并查集"),
    (994,  "Rotting Oranges",              "M", "★★★★",  "多源 BFS"),
]

回溯（10 题）

BACKTRACKING = [
    (78,   "Subsets",                      "M", "★★★★★", "选/不选"),
    (90,   "Subsets II",                   "M", "★★★★",  "去重"),
    (39,   "Combination Sum",              "M", "★★★★★", "可重复选"),
    (40,   "Combination Sum II",           "M", "★★★★",  "不可重复+去重"),
    (46,   "Permutations",                 "M", "★★★★★", "全排列"),
    (47,   "Permutations II",              "M", "★★★★",  "去重排列"),
    (79,   "Word Search",                  "M", "★★★★",  "网格回溯"),
    (51,   "N-Queens",                     "H", "★★★★",  "经典回溯"),
    (17,   "Letter Combinations Phone",    "M", "★★★★",  "多叉树"),
    (131,  "Palindrome Partitioning",      "M", "★★★★",  "回溯+判回文"),
]

动态规划（30 题）

DYNAMIC_PROGRAMMING = [
    # 一维 DP
    (70,   "Climbing Stairs",              "E", "★★★★★", "斐波那契"),
    (198,  "House Robber",                 "M", "★★★★★", "选/不选"),
    (213,  "House Robber II",              "M", "★★★★",  "环形 DP"),
    (322,  "Coin Change",                  "M", "★★★★★", "完全背包"),
    (139,  "Word Break",                   "M", "★★★★★", "字符串 DP"),
    (300,  "Longest Increasing Subseq",    "M", "★★★★★", "LIS 经典"),
    (416,  "Partition Equal Subset",       "M", "★★★★",  "0-1 背包"),
    (91,   "Decode Ways",                  "M", "★★★★",  "线性 DP"),
    
    # 二维 DP
    (62,   "Unique Paths",                 "M", "★★★★",  "网格 DP"),
    (64,   "Minimum Path Sum",             "M", "★★★★",  "网格 DP"),
    (1143, "Longest Common Subseq",        "M", "★★★★★", "LCS 经典"),
    (72,   "Edit Distance",               "H", "★★★★★", "字符串 DP"),
    (10,   "Regular Expression Match",     "H", "★★★★",  "字符串 DP"),
    (97,   "Interleaving String",          "M", "★★★",   "二维 DP"),
    (115,  "Distinct Subsequences",        "H", "★★★",   "二维 DP"),
    
    # 区间/状态 DP
    (5,    "Longest Palindromic Substr",   "M", "★★★★★", "区间 DP/Manacher"),
    (516,  "Longest Palindromic Subseq",   "M", "★★★★",  "区间 DP"),
    (312,  "Burst Balloons",               "H", "★★★★",  "区间 DP"),
    (1547, "Min Cost Cut Stick",           "H", "★★★",   "区间 DP"),
    
    # 背包/状态压缩
    (494,  "Target Sum",                   "M", "★★★★",  "0-1 背包变形"),
    (518,  "Coin Change 2",               "M", "★★★★",  "完全背包"),
    (474,  "Ones and Zeroes",              "M", "★★★",   "二维背包"),
    (377,  "Combination Sum IV",           "M", "★★★",   "排列型背包"),
    
    # 股票系列
    (121,  "Best Time I",                  "E", "★★★★★", "单次交易"),
    (122,  "Best Time II",                 "M", "★★★★",  "无限次交易"),
    (123,  "Best Time III",                "H", "★★★★",  "至多两次"),
    (188,  "Best Time IV",                 "H", "★★★",   "至多 k 次"),
    (309,  "Best Time Cooldown",           "M", "★★★★",  "状态机 DP"),
    (714,  "Best Time Fee",                "M", "★★★",   "状态机 DP"),
    
    # 其他
    (152,  "Maximum Product Subarray",     "M", "★★★★",  "正负分开记"),
]

贪心（10 题）

GREEDY = [
    (55,   "Jump Game",                    "M", "★★★★★", "最远可达"),
    (45,   "Jump Game II",                 "M", "★★★★",  "BFS 思维"),
    (134,  "Gas Station",                  "M", "★★★★",  "累加判断"),
    (846,  "Hand of Straights",            "M", "★★★",   "排序+贪心"),
    (763,  "Partition Labels",             "M", "★★★★",  "最远出现位置"),
    (435,  "Non-overlapping Intervals",    "M", "★★★★",  "区间贪心"),
    (621,  "Task Scheduler",               "M", "★★★★",  "桶思想"),
    (452,  "Min Arrows Burst Balloons",    "M", "★★★",   "区间贪心"),
    (1899, "Merge Triplets Target",        "M", "★★★",   "逐位贪心"),
    (678,  "Valid Parenthesis String",      "M", "★★★★",  "范围贪心"),
]

位运算与数学（10 题）

BIT_MATH = [
    (136,  "Single Number",                "E", "★★★★★", "XOR"),
    (191,  "Number of 1 Bits",             "E", "★★★",   "n & (n-1)"),
    (338,  "Counting Bits",                "E", "★★★★",  "DP+位运算"),
    (268,  "Missing Number",               "E", "★★★★",  "XOR/数学"),
    (190,  "Reverse Bits",                 "E", "★★★",   "逐位操作"),
    (371,  "Sum of Two Integers",          "M", "★★★",   "位运算加法"),
    (7,    "Reverse Integer",              "M", "★★★",   "取模"),
    (50,   "Pow(x, n)",                    "M", "★★★★",  "快速幂"),
    (43,   "Multiply Strings",             "M", "★★★",   "模拟乘法"),
    (202,  "Happy Number",                 "E", "★★★",   "快慢指针/集合"),
]

设计题（15 题）

DESIGN = [
    (146,  "LRU Cache",                    "M", "★★★★★", "哈希+双链表"),
    (460,  "LFU Cache",                    "H", "★★★★",  "双哈希+链表"),
    (380,  "Insert Delete GetRandom",      "M", "★★★★",  "数组+哈希"),
    (355,  "Design Twitter",               "M", "★★★★",  "堆+哈希"),
    (295,  "Find Median Stream",           "H", "★★★★★", "双堆"),
    (703,  "Kth Largest in Stream",        "E", "★★★",   "最小堆 size k"),
    (1396, "Design Underground",           "M", "★★★",   "双哈希"),
    (588,  "Design In-Memory FS",          "H", "★★★",   "Trie"),
    (362,  "Design Hit Counter",           "M", "★★★★",  "队列/桶"),
    (341,  "Flatten Nested List Iterator",  "M", "★★★",   "栈"),
    (895,  "Maximum Frequency Stack",      "H", "★★★★",  "哈希+栈组"),
    (432,  "All O(1) Data Structure",      "H", "★★★",   "双链表+哈希"),
    (716,  "Max Stack",                    "H", "★★★",   "双链表+TreeMap"),
    (622,  "Design Circular Queue",        "M", "★★★",   "数组+双指针"),
    (981,  "Time Based Key-Value",         "M", "★★★★",  "哈希+二分"),
]

1.3 间隔重复法（Spaced Repetition）

遗忘曲线（Ebbinghaus, 1885）告诉我们：学过的东西如果不复习，24 小时后遗忘 70%，一周后遗忘 90%。

刷题的间隔重复策略：

from datetime import datetime, timedelta

class SpacedRepetition:
    """算法题的间隔重复系统
    
    基于 SM-2 算法（SuperMemo, Wozniak 1987）的简化版
    """
    
    INTERVALS = [1, 3, 7, 14, 30, 60]  # 复习间隔（天）
    
    def __init__(self):
        self.problems = {}  # problem_id → {level, next_review, ...}
    
    def record_attempt(self, problem_id: str, solved_independently: bool,
                       time_minutes: int):
        """记录一次做题尝试"""
        if problem_id not in self.problems:
            self.problems[problem_id] = {"level": 0, "attempts": 0}
        
        prob = self.problems[problem_id]
        prob["attempts"] += 1
        prob["last_attempt"] = datetime.now()
        
        if solved_independently and time_minutes <= 45:
            # 做出来了 → 升级间隔
            prob["level"] = min(prob["level"] + 1, len(self.INTERVALS) - 1)
        else:
            # 没做出来 → 重置到短间隔
            prob["level"] = 0
        
        interval = self.INTERVALS[prob["level"]]
        prob["next_review"] = datetime.now() + timedelta(days=interval)
    
    def get_due_problems(self) -> list:
        """获取今天需要复习的题目"""
        today = datetime.now()
        due = []
        for pid, info in self.problems.items():
            if info.get("next_review", today) <= today:
                due.append(pid)
        return due
    
    def get_study_plan(self, available_hours: float) -> dict:
        """根据可用时间生成学习计划"""
        due = self.get_due_problems()
        problems_per_hour = 2  # 保守估计
        
        total_slots = int(available_hours * problems_per_hour)
        review_slots = min(len(due), total_slots // 3)  # 1/3 时间复习
        new_slots = total_slots - review_slots           # 2/3 时间新题
        
        return {
            "复习题目": due[:review_slots],
            "新题数量": new_slots,
            "建议": f"今天做 {review_slots} 道复习 + {new_slots} 道新题",
        }

1.4 常见错误

错误 1：贪多嚼不烂

# ❌ "我每天刷 10 道题，一个月 300 道"
# 问题：一道题花 10 分钟，做完就忘。等于没做。

# ✅ "我每天认真做 2-3 道题，每道花 45 分钟，做完写总结"
# 效果：3 个月 200 道题，每道都真正掌握

错误 2：只刷不思考

# ❌ 做题流程：
# 看题 → 没思路 → 看题解 → "哦原来这样" → 下一题
# 
# 这不是学习，这是看电视。

# ✅ 做题流程：
# 看题 → 尝试 15 分钟 → 确实没思路 → 只看 hint（不看完整解法）
# → 再尝试 15 分钟 → 还是不行 → 看题解
# → 关掉题解自己重写 → 第二天再做一次

Level 2 · 它是怎么运行的

2.1 刻意练习的科学基础

为什么随机刷题效率低？

Ericsson 等人（1993, "The Role of Deliberate Practice in the Acquisition of Expert Performance"）的研究表明：简单重复不能带来进步。提升需要刻意练习（Deliberate Practice），其四个要素：

1. 明确目标： "我今天要掌握滑动窗口的变长窗口模式" vs "我今天随便做几道题"
2. 适当难度： 太简单不进步，太难太挫败。最佳：解出率 50-70% 的题
3. 即时反馈： 做完立刻看是否正确，对比最优解
4. 专注重复： 同类题连续做 5-8 道，形成模式

def deliberate_practice_session(target_pattern: str, duration_hours: float = 2):
    """刻意练习的一次训练单元"""
    
    # 1. 明确本次目标
    goal = f"掌握 {target_pattern} 的核心模板和 3 种变形"
    
    # 2. 选择适当难度的题目
    problems = select_problems(
        pattern=target_pattern,
        difficulty="Medium",  # 当前水平 -1 到 +1
        count=5
    )
    
    # 3. 做题 + 即时反馈
    for problem in problems:
        attempt = solve(problem, time_limit=45)
        
        # 即时反馈
        if attempt.is_correct():
            compare_with_optimal(attempt)  # 有更好的解法吗？
        else:
            identify_failure_point(attempt)  # 卡在哪一步？
        
        # 提取模式
        record_pattern_note(problem, target_pattern)
    
    # 4. 总结
    session_summary = {
        "目标模式": target_pattern,
        "做了几道": len(problems),
        "独立解出": count_solved_independently,
        "核心收获": "...",
        "下次需要加强": "...",
    }
    
    return session_summary

2.2 从"会做题"到"写出工程代码"

面试通过后，你的日常工作是写工程代码——它和 LeetCode 代码有本质区别：

代码风格转换示例

# ========== LeetCode 风格 ==========
def maxProfit(prices):
    dp = [[0]*2 for _ in range(len(prices))]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, len(prices)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    return dp[-1][0]


# ========== 工程风格 ==========
from typing import List
from dataclasses import dataclass


@dataclass
class TradingState:
    """某一天结束时的交易状态"""
    max_profit_without_stock: int  # 不持股时的最大利润
    max_profit_with_stock: int     # 持股时的最大利润


def calculate_max_profit(daily_prices: List[int]) -> int:
    """计算无限次交易的最大利润（不含手续费）。
    
    使用状态机 DP：每天有两个状态——持股和不持股。
    
    Args:
        daily_prices: 每天的股价列表，长度 >= 1，每个值 >= 0
    
    Returns:
        能获得的最大总利润
    
    Raises:
        ValueError: 如果 daily_prices 为空
    
    Examples:
        >>> calculate_max_profit([7, 1, 5, 3, 6, 4])
        7
        >>> calculate_max_profit([1, 2, 3, 4, 5])
        4
    
    Time: O(n), Space: O(1)
    """
    if not daily_prices:
        raise ValueError("daily_prices must not be empty")
    
    state = TradingState(
        max_profit_without_stock=0,
        max_profit_with_stock=-daily_prices[0]
    )
    
    for price in daily_prices[1:]:
        new_without = max(
            state.max_profit_without_stock,
            state.max_profit_with_stock + price  # 卖出
        )
        new_with = max(
            state.max_profit_with_stock,
            state.max_profit_without_stock - price  # 买入
        )
        state = TradingState(
            max_profit_without_stock=new_without,
            max_profit_with_stock=new_with
        )
    
    return state.max_profit_without_stock

可读性原则

# 原则 1：变量名传达意图
# ❌ 
n, m, k = len(grid), len(grid[0]), target
# ✅
num_rows, num_cols, target_sum = len(grid), len(grid[0]), target

# 原则 2：复杂条件提取为函数
# ❌
if node and node.left and node.left.val == node.val and node.right and node.right.val == node.val:
    pass
# ✅
def both_children_match(node):
    """检查节点的两个子节点值是否都等于节点自身的值"""
    if not node or not node.left or not node.right:
        return False
    return node.left.val == node.val == node.right.val

if both_children_match(node):
    pass

# 原则 3：用 early return 减少嵌套
# ❌
def process(data):
    if data:
        if validate(data):
            if transform(data):
                return result
    return None

# ✅
def process(data):
    if not data:
        return None
    if not validate(data):
        return None
    if not transform(data):
        return None
    return result

可测试性原则

# ❌ 不可测试：依赖全局状态
visited = set()

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor)


# ✅ 可测试：依赖注入
def dfs(node, visited: set = None) -> set:
    """DFS 遍历，返回所有访问过的节点
    
    Args:
        node: 起始节点
        visited: 已访问集合（可注入用于测试）
    
    Returns:
        所有访问过的节点集合
    """
    if visited is None:
        visited = set()
    
    if node in visited:
        return visited
    
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)
    
    return visited


# 测试
def test_dfs_simple_graph():
    """测试简单图的 DFS"""
    # Arrange
    a, b, c = Node("a"), Node("b"), Node("c")
    a.neighbors = [b, c]
    b.neighbors = [a]
    c.neighbors = [a]
    
    # Act
    result = dfs(a)
    
    # Assert
    assert result == {a, b, c}

def test_dfs_disconnected():
    """测试不连通图"""
    a, b = Node("a"), Node("b")
    # a 和 b 没有连接
    
    result = dfs(a)
    assert result == {a}
    assert b not in result

2.3 代码审查（Code Review）中的常见问题

入职后你的代码会被审查。以下是新人常犯的"算法竞赛遗留习惯"：

CODE_REVIEW_ISSUES = {
    "单字母变量": {
        "问题": "i, j, k, n, m 在 LeetCode 可以，生产代码不行",
        "例外": "循环变量 i 可以，但嵌套循环时外层用描述性名称",
    },
    "缺少类型注解": {
        "问题": "def solve(arr, k) — 什么类型？什么含义？",
        "修复": "def find_kth_largest(nums: list[int], k: int) -> int",
    },
    "魔术数字": {
        "问题": "if n > 1000000007",
        "修复": "MOD = 10**9 + 7; if n > MOD",
    },
    "缺少错误处理": {
        "问题": "假设输入一定合法",
        "修复": "添加参数验证和异常处理",
    },
    "过度优化可读性": {
        "问题": "用位运算代替简单除法（面试加分，生产扣分）",
        "修复": "除非性能关键路径，否则用清晰的写法",
    },
    "缺少文档": {
        "问题": "算法的时间/空间复杂度、为什么选这个算法",
        "修复": "docstring 说明算法选择的理由",
    },
}

2.4 面试代码与生产代码的桥梁

# 面试中写的代码（快速、简洁、证明你会）
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged


# 同样的算法，生产代码版本
from dataclasses import dataclass
from typing import List


@dataclass(frozen=True, order=True)
class Interval:
    """表示一个时间区间 [start, end]"""
    start: int
    end: int
    
    def __post_init__(self):
        if self.start > self.end:
            raise ValueError(f"Invalid interval: start ({self.start}) > end ({self.end})")
    
    def overlaps_or_adjacent(self, other: 'Interval') -> bool:
        """判断两个区间是否重叠或相邻"""
        return self.start <= other.end and other.start <= self.end
    
    def merge_with(self, other: 'Interval') -> 'Interval':
        """合并两个重叠的区间"""
        if not self.overlaps_or_adjacent(other):
            raise ValueError(f"Cannot merge non-overlapping intervals: {self}, {other}")
        return Interval(min(self.start, other.start), max(self.end, other.end))


def merge_overlapping_intervals(intervals: List[Interval]) -> List[Interval]:
    """合并所有重叠的时间区间。
    
    算法：排序后线性扫描合并（同面试解法）。
    
    Args:
        intervals: 待合并的区间列表
    
    Returns:
        合并后的区间列表（按 start 排序，无重叠）
    
    Time: O(n log n) 排序主导
    Space: O(n) 存储结果
    
    Examples:
        >>> merge_overlapping_intervals([Interval(1,3), Interval(2,6), Interval(8,10)])
        [Interval(start=1, end=6), Interval(start=8, end=10)]
    """
    if not intervals:
        return []
    
    sorted_intervals = sorted(intervals)  # dataclass order=True 按 start 排序
    merged = [sorted_intervals[0]]
    
    for current in sorted_intervals[1:]:
        last_merged = merged[-1]
        if last_merged.overlaps_or_adjacent(current):
            merged[-1] = last_merged.merge_with(current)
        else:
            merged.append(current)
    
    return merged

2.5 算法在日常开发中的应用场景

你不需要每天写排序算法，但算法思维无处不在：

DAILY_ALGORITHM_USAGE = {
    "前端性能优化": {
        "场景": "虚拟列表只渲染可见区域",
        "算法": "二分查找定位可见区间起止位置",
    },
    "后端限流": {
        "场景": "API 每秒最多 100 个请求",
        "算法": "滑动窗口/令牌桶",
    },
    "搜索建议": {
        "场景": "用户输入时实时显示建议词",
        "算法": "Trie + DFS 获取前缀匹配",
    },
    "日志分析": {
        "场景": "找出最近 1 小时访问最多的 10 个 IP",
        "算法": "哈希计数 + 最小堆 Top-K",
    },
    "任务调度": {
        "场景": "Cron 任务按优先级执行",
        "算法": "优先队列",
    },
    "数据去重": {
        "场景": "消息队列消费者幂等性",
        "算法": "布隆过滤器预判 + 数据库唯一约束兜底",
    },
    "缓存设计": {
        "场景": "热数据缓存淘汰",
        "算法": "LRU / LFU",
    },
    "配置匹配": {
        "场景": "路由规则匹配（/api/v1/users/:id）",
        "算法": "Trie + 通配符匹配",
    },
}

Level 3 · 规范怎么定义的

3.1 学习效率的科学研究

主动回忆（Active Recall）vs 被动复习（Passive Review）：

Karpicke & Roediger (2008, "The Critical Importance of Retrieval Practice for Learning", Science) 的实验：

• 组 A：反复阅读材料 4 次
• 组 B：阅读 1 次 + 尝试回忆 3 次
• 一周后测试：组 B 的记忆率是组 A 的 1.5 倍

对刷题的启示：

• 看题解 ≈ 被动复习 → 效率低
• 关掉题解自己重写 ≈ 主动回忆 → 效率高
• 隔天不看代码重做 ≈ 间隔回忆 → 效率最高

交错练习（Interleaving）vs 批量练习（Blocking）：

Rohrer & Taylor (2007) 的研究：

• 批量练习：AAABBBCCC（连续做同类题）
• 交错练习：ABCABCABC（混合做不同类型）
• 短期表现：批量更好（当天测试）
• 长期记忆：交错更好（一周后测试，高 43%）

def optimal_study_schedule(available_days: int, target_problems: int) -> dict:
    """基于认知科学的最优学习计划
    
    研究来源：
    - Ericsson (1993): 刻意练习每天最多 4 小时有效
    - Karpicke (2008): 主动回忆 > 被动复习
    - Rohrer (2007): 长期效果，交错 > 批量
    - Ebbinghaus (1885): 间隔重复抗遗忘
    """
    
    daily_effective_hours = 2.5  # 保守估计（含休息）
    problems_per_day = 3  # 高质量做题（含分析、重写）
    
    schedule = {
        "每日时间分配": {
            "新题": "1.5 小时（2-3 道，包含分析）",
            "复习": "0.5 小时（2-3 道 due 的旧题）",
            "总结": "0.5 小时（写笔记、更新模式库）",
        },
        "每周结构": {
            "周一到周五": "正常学习",
            "周六": "模拟面试（限时做 2 道题）",
            "周日": "周复习（重做本周错题）",
        },
        "进度追踪": {
            "入门→中级": f"约 {50 // problems_per_day} 天",
            "中级→高级": f"约 {100 // problems_per_day} 天",
            "总计": f"约 {target_problems // problems_per_day} 天",
        },
    }
    
    return schedule

3.2 200 题精选清单的设计原则

本章 1.2 节的 200 题清单基于以下原则设计：

原则 1：覆盖所有高频题型

# 每种题型至少 10 题，确保足够的重复次数
# 认知心理学：一个模式至少需要看到 7-10 次才能稳固
COVERAGE_REQUIREMENT = {
    "数组双指针": 20,  # 最高频
    "动态规划": 30,    # 最有深度
    "树": 20,          # 面试必考
    "图": 15,          # Medium-Hard
    "回溯": 10,        # 模板清晰
    "滑动窗口": 10,    # 模板清晰
    "链表": 10,        # 基础
    "栈队列": 10,      # 单调栈是难点
    "贪心": 10,        # 证明是难点
    "位运算数学": 10,  # 补充
    "设计": 15,        # 综合
}
# 总计：160 核心 + 40 补充 = 200

原则 2：难度渐进

每种题型的题目按照 Easy → Medium → Hard 排列。第一道一定是模板题（直接对应模式），最后几道是变形题（需要思考如何归约到已知模式）。

原则 3：频率优先

5 星题 = 几乎所有公司都会考（或其变形），必须做到"看到就知道怎么做"的程度。

3.3 不同目标的定制路线

面试导向（最短路径）

INTERVIEW_FOCUSED_PATH = {
    "总时间": "2-3 个月",
    "总题量": "100-150 题",
    "策略": "只做 4-5 星频率的题，跳过竞赛专用题型",
    "重点": {
        "必刷": ["双指针", "滑动窗口", "BFS/DFS", "DP 基础", "树", "设计"],
        "选刷": ["贪心", "图高级", "位运算"],
        "跳过": ["线段树", "后缀数组", "网络流", "数位 DP"],
    },
    "里程碑": {
        "第 1 月": "Easy 90%+ 解出率，Medium 50%",
        "第 2 月": "Medium 70%+ 解出率",
        "第 3 月": "Mock interview 通过率 > 60%",
    },
}

深度学习导向（本书读者）

DEEP_LEARNING_PATH = {
    "总时间": "6-12 个月",
    "总题量": "300+ 题",
    "策略": "跟随本书章节顺序，每章学完做对应题目",
    "特点": {
        "不跳过理论": "先读完章节再做题",
        "理解优先": "每道题要能解释'为什么用这个算法'",
        "工程导向": "每道题额外写单元测试",
    },
    "每章学习流程": [
        "1. 阅读本书对应章节（1-2 小时）",
        "2. 做章节对应的 5-8 道题（2-3 小时）",
        "3. 写总结笔记：这个算法的核心思想、适用条件、常见变形",
        "4. 一周后复习：不看笔记重做错题",
    ],
}

竞赛导向

COMPETITION_PATH = {
    "总时间": "12+ 个月",
    "平台": ["Codeforces", "AtCoder", "LeetCode Contest"],
    "阶段": {
        "基础期(3月)": "Codeforces Div.2 A-C 能稳定做出",
        "提高期(3月)": "Div.2 D / Div.1 A 能做出",
        "高手期(6月+)": "Div.1 B-C 有思路",
    },
    "竞赛特有训练": [
        "数论（模运算、质因数、欧拉函数）",
        "组合数学（卡特兰数、容斥原理）",
        "计算几何（凸包、最近点对）",
        "高级数据结构（可持久化、CDQ 分治）",
        "字符串（SAM、回文自动机）",
    ],
}

3.4 如何衡量自己的水平

SKILL_ASSESSMENT = {
    "入门": {
        "Easy 解出率": "> 80%",
        "平均用时": "< 20 分钟",
        "标志": "看到 Easy 题有明确的第一反应",
    },
    "中级": {
        "Medium 解出率": "> 70%（45分钟内）",
        "平均用时": "< 30 分钟",
        "标志": "能识别大多数题型，知道用什么算法",
    },
    "高级": {
        "Hard 解出率": "> 40%（60分钟内）",
        "标志": "能把陌生问题归约到已知问题",
        "系统设计": "能做 Level 2 深度（需要结合算法知识）",
    },
    "竞赛级": {
        "标志": "LeetCode 周赛前 100 / Codeforces 1800+",
        "特点": "见过足够多的模式变形，直觉强",
    },
}

3.5 学习工具推荐

RECOMMENDED_TOOLS = {
    "刷题平台": {
        "LeetCode": "面试题库最全，支持中英文",
        "Codeforces": "竞赛训练首选，难度标定准确",
        "AtCoder": "日本竞赛平台，题目质量极高",
    },
    "可视化": {
        "VisuAlgo": "数据结构和算法动画（新加坡国立大学）",
        "Algorithm Visualizer": "自定义代码可视化执行",
        "Python Tutor": "逐行展示 Python 执行过程",
    },
    "记录与复习": {
        "Anki": "通用间隔重复工具，可自制算法卡片",
        "Notion/Obsidian": "建立个人算法知识库",
        "Git repo": "所有题解存在私有 repo，方便搜索",
    },
    "模拟面试": {
        "Pramp": "免费配对模拟面试",
        "Interviewing.io": "与真实面试官练习",
        "录制自己": "录屏+录音，回放分析自己的表现",
    },
}

Level 4 · 边界与陷阱

4.1 常见学习误区

误区 1：只刷不思考（"题海战术"）

# 症状：
# - 做了 500 题但面试还是不过
# - 同一道题隔一个月再做又不会了
# - 看到新题第一反应是"这道题我没做过"而非"这道题像 XX 模式"

# 根因：
# 你积累的是"题目→答案"的映射（记忆）
# 而不是"特征→模式→模板"的映射（理解）

# 修复：
def proper_study_after_solving(problem, my_solution):
    """做完每道题的正确后续步骤"""
    
    # 1. 分类：这道题属于什么模式？
    pattern = classify(problem)
    
    # 2. 提取：这个模式的通用模板是什么？
    template = extract_template(pattern)
    
    # 3. 变形：这道题相比模板有什么变化？
    variations = identify_variations(problem, template)
    
    # 4. 连接：之前做过的哪些题也是这个模式？
    related = find_related_problems(pattern)
    
    # 5. 预测：如果面试官追问，可能怎么变？
    followups = predict_followups(problem)
    
    return {
        "模式": pattern,
        "模板": template,
        "变形点": variations,
        "同类题": related,
        "可能追问": followups,
    }

误区 2：贪多嚼不烂

# 症状：
# - 每天做 5-10 题，每道只花 15 分钟
# - 做完就标"已完成"，不复习
# - 追求"做过的题数"而非"掌握的模式数"

# 数学证明为什么这样低效：
# 假设每道题：
# - 不复习：7 天后记忆率 10%
# - 间隔复习 3 次：30 天后记忆率 80%
#
# 策略 A：每天 10 题，不复习
#   一个月做 300 题，记住 300 * 10% = 30 题
#
# 策略 B：每天 3 新题 + 2 复习题
#   一个月做 90 新题 + 60 次复习，记住 90 * 80% = 72 题
#
# 策略 B 的"有效题量"是 A 的 2.4 倍

# 修复：质量 > 数量
QUALITY_OVER_QUANTITY = {
    "每日新题上限": 3,
    "每道题最少时间": "30 分钟（含分析）",
    "复习频率": "1天、3天、7天、14天后各复习一次",
    "完成标准": "不看任何提示能在 20 分钟内写出正确代码",
}

误区 3：忽视基础

# 症状：
# - 直接刷 Hard 题，跳过 Easy/Medium
# - 不学理论直接做题（不知道 DP 的数学定义，只背转移方程）
# - 做出来了但不知道为什么，换个变形就不会了

# 类比：
# 这就像一个人想学高等数学，但跳过了算术和代数。
# 他可能能记住某些积分公式，但无法推导新的公式。

# 修复：
FOUNDATION_FIRST = {
    "正确顺序": [
        "1. 学习数据结构基础（本书 1-10 章）",
        "2. 做每种数据结构的 Easy 题（建立直觉）",
        "3. 学习算法基础（本书 11-20 章）",
        "4. 做 Medium 题（应用模式）",
        "5. 学习高级主题（本书 21-40 章）",
        "6. 做 Hard 题（组合多种模式）",
    ],
    "判断标准": "如果你不能在 5 分钟内向别人解释清楚某个算法的核心思想，"
                "说明你还没真正理解它。不要急着往前走。",
}

误区 4：不做模拟面试

# 症状：
# - 在 LeetCode 上做得很好，但面试总紧张
# - 不习惯边写边说
# - 时间管理差（花太久在前半部分）

# 修复：
MOCK_INTERVIEW_PROTOCOL = {
    "频率": "每周至少 1 次",
    "方式": [
        "找朋友互相 mock（最有效）",
        "使用 Pramp/Interviewing.io（次之）",
        "自己计时做题 + 录音回放（最低要求）",
    ],
    "关键练习点": [
        "开口说思路（不能沉默超过 30 秒）",
        "控制时间（15 分钟必须开始写码）",
        "主动测试（写完代码后手动 trace）",
        "处理卡住（请求提示而非沉默）",
    ],
}

4.2 持续学习建议

面试通过后不要停止学习：

POST_OFFER_LEARNING = {
    "入职前": {
        "系统设计": "读 DDIA（Designing Data-Intensive Applications）",
        "语言深入": "读语言规范/源码（如 CPython internals）",
        "项目准备": "了解新公司的技术栈",
    },
    "入职后 0-3 月": {
        "重点": "理解代码库架构、学习内部工具",
        "算法保持": "每周 1-2 道题防遗忘",
    },
    "入职后 3-12 月": {
        "重点": "深入某个方向（如分布式系统、ML 系统）",
        "拓展": "读论文、参加技术分享",
    },
    "长期": {
        "重点": "T 型人才 — 一个方向深入 + 广泛涉猎",
        "目标": "能设计系统、能带团队、能做技术决策",
    },
}

4.3 学习心态

成长型思维（Growth Mindset）：

Dweck (2006, "Mindset: The New Psychology of Success") 的研究表明：相信智力可以通过努力提高的人，比相信智力固定的人，在困难任务上表现更好。

MINDSET_PRINCIPLES = {
    "接受困难": "Hard 题做不出来是正常的，不代表你笨",
    "拥抱错误": "每个 bug 都是学习机会，不是失败",
    "过程导向": "关注'今天比昨天进步了什么'而非'我排名多少'",
    "长期主义": "算法能力是 3-6 个月建立的，不是 3 天",
    "对比自己": "和一个月前的自己比，不要和 LeetCode 大神比",
}

Plateau（平台期）的应对：

PLATEAU_STRATEGIES = {
    "症状": "做了 2 周感觉没有进步",
    "原因": [
        "题目难度没有递增（一直做同样难度）",
        "缺乏反馈（做完不分析错误）",
        "疲劳（每天刷题超过 3 小时）",
    ],
    "解决方案": [
        "换一种题型（打破单一模式的疲劳）",
        "增加难度（从 Medium 跳到 Hard）",
        "减少数量但增加深度（每道题写详细分析）",
        "休息 2-3 天（大脑需要巩固时间）",
        "换学习方式（看视频、读论文、给别人讲）",
    ],
}

4.4 从个人刷题到团队成长

如果你已经达到了高级水平，可以考虑帮助他人——这是巩固知识的最有效方式（Feynman Technique）：

TEACHING_AND_GROWING = {
    "组织学习小组": {
        "形式": "每周一次，2-3 人，每人讲一道题",
        "效果": "讲清楚一道题 > 做对十道题",
    },
    "写技术博客": {
        "内容": "不是写题解（网上已经有），而是写'我是如何想到这个方法的'",
        "效果": "强迫你组织思维、发现理解的盲点",
    },
    "做模拟面试官": {
        "形式": "给朋友出题、引导、打分",
        "效果": "站在面试官角度思考，理解什么是'好的回答'",
    },
    "贡献开源": {
        "形式": "给开源项目修 bug、写优化",
        "效果": "将算法能力转化为工程能力",
    },
}

4.5 本书的知识地图总结

回顾整本书 43 章的知识结构：

第一部分：基础数据结构（第 1-10 章）
├── 复杂度分析（第 1 章）— 一切的尺子
├── 数组与字符串（第 2 章）— 最基本的容器
├── 二分查找（第 3 章）— 有序性的利用
├── 链表（第 4 章）— 动态结构
├── 栈与队列（第 5 章）— 限制操作的容器
├── 跳表（第 6 章）— 概率化的有序结构
├── 并查集（第 7 章）— 集合的合并与查询
├── 哈希表（第 8 章）— O(1) 的代价
├── 布隆过滤器（第 9 章）— 概率化的集合
└── Trie（第 10 章）— 前缀的力量

第二部分：排序与搜索（第 11-18 章）
├── 排序算法（第 11-14 章）
├── 选择算法（第 15 章）
├── 外部排序（第 16 章）
├── 搜索算法（第 17-18 章）
└── ...

第三部分：树与图（第 19-24 章）
├── 二叉树（第 19 章）
├── BST 与平衡树（第 20-21 章）
├── 图遍历（第 22 章）
├── 最短路（第 23 章）
└── 最小生成树与高级图算法（第 24 章）

第四部分：算法设计范式（第 25-32 章）
├── 贪心（第 25 章）
├── 回溯（第 26 章）
├── 动态规划（第 27-30 章）
├── 位运算（第 31 章）
└── 数学算法（第 32 章）

第五部分：高级主题（第 33-40 章）
├── 线段树/树状数组（第 33 章）
├── 字符串算法（第 34 章）
├── 计算几何（第 35 章）
├── 随机化算法（第 36 章）
├── 近似算法（第 37 章）
├── 并行算法（第 38 章）
├── 算法的极限（第 39 章）— P vs NP
└── 实战项目（第 40 章）

第六部分：总结与应用（第 41-43 章）
├── 面试通关（第 41 章）— 题型分类与解题框架
├── 从算法到系统设计（第 42 章）— 桥接两个世界
└── 学习路线与刷题指南（第 43 章）— 你在这里

本章小结

全书完。 如果你从第 1 章读到了这里，恭喜——你已经建立了从基础数据结构到系统设计的完整知识链路。现在开始实践：选择适合你阶段的题目，按照本章的方法论，每天前进一小步。算法能力不是天赋，是积累。祝你面试顺利，工程卓越。