LeetCode 刷题指南：从题型分类到面试策略的系统化路径

1. 概述与学习目标

1.1 什么是 LeetCode 刷题

LeetCode 刷题（LeetCode Grinding）指在 LeetCode 在线评测系统（Online Judge, OJ）上系统性地反复解答算法题目，以训练算法思维、备战技术面试或参与算法竞赛的学习实践。该实践脱胎于 1970 年代 ACM ICPC 校园竞赛文化，在 2015 年 LeetCode 平台创立后逐渐成为全球软件工程师面试准备的事实标准（de facto standard）。

刷题活动包含三层递进目标：

刷题并非简单”题海战术”。MIT 6.006《Introduction to Algorithms》课程负责人 Srini Devadas 在 2020 年公开课中强调：“Algorithms are not memorized—they are derived.”（算法不是被记忆的，而是被推导的）。同样，刷题的核心价值在于通过反复训练建立”问题—算法”的条件反射（pattern matching），而非死记题解。

1.2 刷题的工程与学术双重价值

刷题活动同时具备学术训练与工程准备双重价值：

LeetCode 刷题价值模型
                                刷题训练
                                    │
            ┌───────────────────────┼───────────────────────┐
            │                       │                       │
        学术训练                  工程准备                  竞赛训练
            │                       │                       │
   ┌────────┴────────┐      ┌───────┴───────┐        ┌──────┴──────┐
  形式化建模         复杂度   面试编码       工程映射   ICPC/Codeforces
  不变式证明         分析     白板沟通       系统设计   周赛/双周赛
  算法范式迁移       摊还     边界处理       性能调优   AtCoder ABC/ARC

学术训练维度：

• 形式化建模：将自然语言描述的问题转化为数学结构（图、树、序列、集合）
• 复杂度分析：量化算法的时间、空间、摊还代价
• 不变式证明：用循环不变式（loop invariant）证明算法正确性
• 算法范式迁移：识别分治、贪心、DP、回溯、分支限界的适用场景

工程准备维度：

• 面试编码：在 30-45 分钟内完成白板或在线编码
• 边界处理：空输入、单元素、极大输入、负数、溢出
• 性能调优：从暴力解到最优解的逐步优化
• 工程映射：LRU Cache → Redis、并查集 → K8s 网络、滑动窗口 → Prometheus

1.3 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：LeetCode 平台发展脉络、十大题型分类、三遍刷题法与四步解题法的步骤
2. 理解（Understand）：算法竞赛平台演进史（ACM ICPC 1970 → Google Code Jam 2003 → Codeforces 2009 → LeetCode 2015）、Hot 100/Top Interview 150/Grind 75/NeetCode 150 四大刷题清单的设计动机
3. 应用（Apply）：使用时间复杂度反推规则从 $n$ 的范围选择可行算法类别，使用八大解题模板（双指针、滑动窗口、二分、回溯、BFS/DFS、单调栈、前缀和、位运算）编写 Python/C++/Java 三语言代码
4. 分析（Analyze）：各解题模板的复杂度、正确性不变式、适用场景，掌握”暴力→记忆化→DP→状态压缩→位运算”的优化链路
5. 评估（Evaluate）：LeetCode/LintCode/HackerRank/CodeSignal/牛客网五大面试平台与 Codeforces/AtCoder/Topcoder 三大竞赛平台的优劣与适用场景
6. 对比（Compare）：FAANG（Google/Meta/Amazon/Microsoft/Apple）与国内大厂（字节跳动/腾讯/阿里巴巴/百度/美团）的面试风格、考察重点、评分标准
7. 创造（Create）：设计 LeetCode 题目到工业场景的映射方案，构建个人刷题追踪系统、算法学习路径推荐引擎

跨模块引用：刷题所需的算法理论基础知识参见 算法分析基础与学习路线，递归与回溯的深入讨论参见 递归与回溯。

2. 历史动机与演进

2.1 算法竞赛的起源：ACM ICPC（1970）

国际大学生程序设计竞赛（International Collegiate Programming Contest, ICPC）是算法竞赛的鼻祖，其历史可追溯至 1970 年德克萨斯 A&M 大学举办的首届竞赛（当时称 ACM-TCSCC Programming Contest）。1977 年该竞赛正式由 ACM 主办并更名为 ICPC，逐步发展为全球最大规模的大学生程序设计竞赛。

ICPC 的核心特征：

• 团队赛制：每队 3 人共用 1 台电脑，5 小时内求解 10-15 道算法题
• 多层级晋级：Local Contest → Regional Contest → World Finals
• 即时反馈：提交后系统立即返回 Accepted / Wrong Answer / Time Limit Exceeded 等结果
• 气球文化：每解出一题，志愿者会在该队桌上升起对应颜色的气球，作为可视化进度

ICPC 培养了大批顶尖算法工程师与计算机科学家，包括：

• Gennady Korotkevich（tourist）：6 次 ICPC 世界冠军（2013-2019），Codeforces 评分长期第一
• Makoto Soejima（wata）：日本 ICPC 传奇，多次世界决赛
• Bugra Kilic（learner）：土耳其裔美国选手，Facebook Hacker Cup 2014-2017 冠军

ICPC 的”实时评测+排名”模式直接催生了在线评测系统（OJ）的概念。1995 年西班牙 Valladolid 大学（UVa）上线了全球首个面向公众的 OJ，由 Miguel A. Revilla 维护，收录 3000+ 经典题目，至今仍是 ICPC 训练的核心平台。

2.2 Google Code Jam（2003-2023）

Google Code Jam 是 Google 主办的年度算法编程竞赛，2003 年首次举办，2023 年 4 月 Google 宣布停办，共举办 21 届。

Google Code Jam 的历史里程碑：

Google Code Jam 的特点：

• 个人赛：与 ICPC 团队赛不同，Code Jam 为个人赛
• 多轮晋级：Qualification Round → Round 1 (A/B/C) → Round 2 → Round 3 → World Finals
• 交互式题目：部分题目需下载输入文件、本地计算后上传输出
• 高奖金：World Finals 冠军奖金 $15,000，总奖金池$105,000

Code Jam 培养了多位传奇选手：

• Gennady Korotkevich（tourist）：6 次 Code Jam 冠军（2014, 2016-2020），史上最多
• Yuhao Li（bmerry）：中国选手，2008 年 Code Jam 亚军
• Ling Zhong（zhongzhu）：中国选手，多次进入 World Finals

Code Jam 的停办标志着算法竞赛黄金时代的一个转折点。Google 在停办声明中表示将精力转向其他形式的技术人才培养，但未明确替代方案。社区普遍认为这与 Google 裁员潮、AI 编程工具兴起有关。

2.3 Topcoder Open（2001）

Topcoder Open（TCO） 由 Topcoder 公司于 2001 年创办，是早期最具影响力的商业算法竞赛之一。Topcoder 公司由 Jack Hughes 1999 年创立，最初定位为”通过竞赛众包软件开发”的平台。

Topcoder 的核心创新：

• SRM（Single Round Match）：每周多次的 75 分钟在线算法竞赛
• Rating 系统：借鉴国际象棋 Elo 评分，红黄蓝绿四色段位
• 题目质量：以题目设计精巧著称，Topcoder problem setters 通常是顶级选手
• 金钱奖励：SRM 前几名有现金奖励，年度 TCO 总决赛奖金 $20,000+

Topcoder 培养了：

• tomek：Tomasz Czajka，3 次 TCO 冠军（2003, 2005, 2008）
• Petr：Petr Mitrichev，俄罗斯传奇，Google 工程师
• ACRush：楼天城，中国第一代竞赛选手代表，Facebook/Google 工程师

2010 年代后，随着 Codeforces 的崛起，Topcoder SRM 的参与度逐渐下降。2017 年 Topcoder 被收购后业务重心转向企业众包，SRM 频率从每周 1-2 次降至每月 1-2 次。但其 Rating 系统设计被 Codeforces、AtCoder 等后续平台广泛借鉴。

2.4 Meta Hacker Cup（2011-）

Meta Hacker Cup（原名 Facebook Hacker Cup）是 Meta 主办的年度算法竞赛，2011 年首次举办。

Hacker Cup 的特点：

• 年度单次赛事：每年 1 届，Qualification → Round 1/2/3 → Finals
• 线下决赛：World Finals 通常在 Meta 总部（Menlo Park）举办
• 高额奖金：冠军 $20,000，总奖金池超过 Google Code Jam
• 题目风格：偏向数学与组合博弈，与 Code Jam 风格互补

著名冠军：

• Gennady Korotkevich（tourist）：2014-2017 四连冠
• Bin Jin（binjin）：中国选手，2012 年亚军
• Egor Kulikov（Egor）：俄罗斯选手，2013 年冠军

Hacker Cup 至今仍在举办，是少数延续的全球性算法竞赛之一。

2.5 Codeforces（2009）

Codeforces 由莫斯科理工大学教授 Mikhail Mirzayanov 于 2009 年创立，是当今全球最活跃的算法竞赛平台。

Codeforces 的关键创新：

• 高频比赛：每周 2-4 场 Rated Contest，远超 Topcoder
• 评分系统：基于 Elo 改进，引入 volatility（波动率）参数
• 题目分级：A-H 难度递增，A 题适合入门，H 题接近 ICPC World Finals 水平
• Div 1/2/3/4 分组：根据 Rating 自动分流，新手不会被高难度题目打击
• Educational Rounds：每月 1-2 场教学赛，题目按知识点分类
• Gym：可上传 ICPC 历史题目进行团队训练

Codeforces 评分系统是算法竞赛界的”事实标准”：

著名 Legendary Grandmaster 包括：tourist、Petr、Benq、Um_nik、neal、Radewoosh、jiangly 等。其中 tourist 长期保持 Rating 第一（约 3800-4000），被视为”算法竞赛之神”。

Codeforces 培养了大量人才进入 FAANG：Google、Meta、Jane Street、 Hudson River Trading 等量化交易公司常年赞助 Codeforces，并直接从 Grandmaster+ 段位招聘。

2.6 AtCoder（2012）

AtCoder 由日本 AtCoder 公司（CEO Takuya Akatsu）于 2012 年创立，是亚洲第二大算法竞赛平台。

AtCoder 的特点：

• ABC/ARC/AGC 三档赛事：
  • ABC（AtCoder Beginner Contest）：每周日举办，A-F 六题，A-C 适合新手
  • ARC（AtCoder Regular Contest）：每月 1-2 次，难度介于 ABC 与 AGC 之间
  • AGC（AtCoder Grand Contest）：每年 4-6 次，最高难度，H 题接近 ICPC World Finals 水平
• 题目质量：以题目设计精巧、数学味浓郁著称
• 日本风格：题目描述简洁、测试数据严谨、评测稳定
• AtCoder Library（ACL）：官方提供的 C++ 算法库，含并查集、线段树、卷积等

AtCoder 评分系统：

AtCoder Red 段位选手约 100 人，含 tourist、benq、yosupo、nolez 等顶级选手。

2.7 LeetCode 的诞生（2015）

LeetCode 由 Winston Tang（唐炜森）2015 年在美国创立。Winston Tang 毕业于复旦大学计算机系，后赴美工作，曾在 Google、Uber 等公司任职。创立 LeetCode 的初衷源于其自身的面试准备经历：

“在准备 FAANG 面试时，我发现当时的在线评测平台（HackerRank、CodeWars）要么偏向竞赛风格、要么偏向语法练习，缺乏专门针对面试的题目集。LeetCode 的目标是覆盖面试高频考点，提供接近真实面试的题目与评测体验。” —— Winston Tang（2017 年采访）

LeetCode 的关键设计决策：

2.8 LeetCode 中国扩展（2018）

2018 年 4 月，领扣网络（上海）有限公司成立，标志着 LeetCode 正式进入中国市场。LeetCode China（leetcode.cn）作为独立运营的本地化平台，提供：

• 中文题目描述（部分题目）
• 中国大厂面试高频题专项（字节跳动、腾讯、阿里巴巴、百度、美团等公司标签）
• 剑指 Offer 题集（与何海涛《剑指 Offer》一书同步）
• 程序员面试金典题集（与 Gayle McDowell《CTCI》同步）
• 中文社区与题解
• 春招/秋招专项活动

LeetCode China 的本地化策略有效推动了中国开发者刷题文化的兴起。截至 2026 年，LeetCode China 注册用户超过 800 万，月活超过 100 万，成为中文开发者面试准备的首选平台。

2.9 在线评测平台演进时间线

timeline
    title 在线评测平台演进史
    1970 : ACM ICPC 首届竞赛 (Texas A&M)
    1977 : ICPC 正式由 ACM 主办
    1995 : UVa OJ 上线 (首个公开 OJ)
    2001 : Topcoder Open 创办 / SRM 模式兴起
    2003 : Google Code Jam 创办
    2009 : Codeforces 创立 (Mirzayanov)
    2011 : Facebook Hacker Cup 创办
    2012 : AtCoder 创立 (日本)
    2014 : HackerRank 转型面试导向
    2015 : LeetCode 创立 (Winston Tang)
    2018 : LeetCode 中国 (领扣网络) 成立
    2020 : Blind 75 刷题清单发布 (Yangshun Tay)
    2022 : NeetCode 150 发布 (Navdeep Singh)
    2023 : Google Code Jam 停办 (4 月)
    2026 : LeetCode 题库突破 3500 题

2.10 刷题文化的兴起

刷题文化的兴起与以下因素密切相关：

1. FAANG 面试标准化（2010 年代）

Google、Meta、Amazon 等公司自 2010 年代起将算法面试作为技术筛选的标准环节，原因包括：

• 客观可量化：算法题有明确的 Accepted/Wrong 答案
• 候选人规模：每年数百万简历，需要高效筛选
• 工程能力代理：算法能力被视为工程能力的代理指标

2. 在线评测平台普及

LeetCode、HackerRank、CodeSignal 等平台使任何人都能在浏览器中练习真实面试题，降低了面试准备门槛。

3. 社区内容生态

• Blind：匿名职场社交平台，FAANG 员工分享面试经验
• Reddit r/cscareerquestions：北美求职论坛
• 一亩三分地：北美华人求职论坛
• 牛客网：中国求职社区，含面经与题库
• 知乎”算法”话题：中文算法讨论

4. 高质量刷题清单

2.11 关键设计决策

在线评测平台演进中形成了一系列关键设计决策：

1. 即时反馈机制（UVa OJ 1995 首创）：提交后立即返回 Accepted/Wrong，比批改作业高效
2. 多语言支持（LeetCode 2015 普及）：降低语言门槛，聚焦算法本身
3. 题目分级（Codeforces Div 1/2/3 2009）：避免新手被高难题目打击
4. Rating 系统（Topcoder Elo 2001 → Codeforces 改进 2009 → AtCoder 2012）：量化能力成长，激发学习动力
5. 公司标签（LeetCode 2015）：精准定位目标公司面试题
6. UGC 题解（LeetCode 2015）：社区智慧积累，覆盖多解法
7. 周赛/双周赛（LeetCode 2016 周赛，2020 双周赛）：提供竞技训练
8. 题目分类清单（Blind 75 2018 → NeetCode 150 2022）：系统化刷题路径

2.12 趋势：从纯算法到综合评估（2020-）

2020 年后，技术面试出现以下趋势：

• 系统设计题占比上升：Senior+ 职位算法题减少，系统设计题增加
• 行为面试（Behavioral）强化：Amazon LP（Leadership Principles）模式被广泛模仿
• AI 编程工具兴起：GitHub Copilot、ChatGPT、Claude 等工具降低编码门槛，但算法思维价值反而上升
• 部分公司取消 LeetCode 式面试：2024 年 Snapchat 宣布取消 LeetCode 风格算法面试，转向”更实际的技术筛选”
• LeetCode Hard 题量下降：FAANG 面试中 Hard 题占比从 2015 年的 20% 降至 2025 年的 10% 以下

尽管存在争议，LeetCode 刷题仍是 2026 年 FAANG 与国内大厂面试准备的主流方式。其核心价值不在于题目本身，而在于通过系统化训练建立的算法思维与编码习惯。

3. 形式化定义与方法论

3.1 刷题过程的形式化定义

定义 3.1（刷题过程）：刷题过程可形式化为六元组 $\mathcal{L} = (P, S, A, \tau, \rho, \sigma)$，其中：

• $P = \{p_1, p_2, \ldots, p_n\}$ 为题目集合，每题 $p_i = (d_i, c_i, \text{tags}_i, \text{diff}_i)$ 含题面、约束、标签、难度
• $S$ 为解题者状态空间，$s \in S$ 表示解题者当前的知识图谱（已掌握题型、解题模板、错题集）
• $A$ 为算法动作空间，$a \in A$ 表示具体算法（如双指针、DP、回溯）
• $\tau: P \times S \to A$ 为题目到算法的映射策略
• $\rho: P \times A \to \{0, 1\}$ 为评测函数（0=Wrong，1=Accepted）
• $\sigma: S \times P \times A \to S$ 为状态更新函数（学习反馈）

目标：最大化 $\mathbb{E}\left[\frac{1}{|P_{\text{test}}|}\sum_{p \in P_{\text{test}}} \rho(p, \tau^*(p, s))\right]$，即在测试题集上的期望通过率。

3.2 时间复杂度反推：从约束到算法

定理 3.1（复杂度反推定理）：设现代 CPU 每秒执行 $C \approx 10^8$ 次基本运算，LeetCode 默认时间限制 $T = 2$ 秒，则对输入规模 $n$，可行算法的时间复杂度上界为

$T(n) \leq C \cdot T = 2 \times 10^8$

由此可反推：

证明：以 $n = 10^5$ 为例。若算法为 $O(n^2)$，则 $T(n) = 10^{10}$ 次运算，远超 $2 \times 10^8$ 上限，必 TLE。若算法为 $O(n \log n)$，则 $T(n) \approx 10^5 \times 17 \approx 1.7 \times 10^6$，远低于上限，可行。若算法为 $O(n)$，则 $T(n) = 10^5$，远低于上限。$\blacksquare$

推论 3.1（$n = 20$ 启发式）：当 $n \leq 20$ 时，$2^{20} = 1,048,576 \approx 10^6$，故 $O(2^n)$ 可行。这正是状态压缩 DP（bitmask DP）的常见信号。LeetCode 526（Beautiful Arrangement）、1125（Smallest Sufficient Team）、1655（Distribute Repeating Integers）均属此类。

推论 3.2（$n = 100$ 启发式）：当 $n \leq 100$ 时，$n^3 = 10^6$，故 $O(n^3)$ 可行。区间 DP（Interval DP）的 $O(n^3)$ 复杂度正符合此约束。LeetCode 312（Burst Balloons）、664（Strange Printer）、1000（Minimum Cost to Merge Stones）均属此类。

3.3 三遍刷题法

三遍刷题法（Three-Pass Problem Solving）是 LeetCode 中国社区 2017-2019 年间总结的系统化刷题方法论，对应 Bloom 分类法的 Remember→Apply→Analyze 三阶段。

第一遍：理解（Remember / Understand）

第二遍：应用（Apply）

第三遍：分析（Analyze / Evaluate）

3.4 四步解题法

四步解题法（Four-Step Problem Solving）源自 Gayle McDowell《Cracking the Coding Interview》第 6 版（2015）的”5-Step Process”，经社区简化为四步：

┌─────────────────────────────────────────────────────────────┐
│            四步解题法（5-25 分钟面试场景）                    │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Step 1: 审题（2-3 min）                                     │
│  ├── 复述题目（确认理解）                                    │
│  ├── 确认输入输出格式                                        │
│  ├── 询问约束条件（n 范围、数据类型、是否有负数）            │
│  └── 讨论边界情况（空输入、单元素、极大值）                  │
│                                                             │
│  Step 2: 建模（5-8 min）                                     │
│  ├── 先说暴力解（O(n^2) 或更高）                             │
│  ├── 分析瓶颈                                                │
│  ├── 提出优化思路（利用题目特性）                            │
│  └── 与面试官确认方向                                        │
│                                                             │
│  Step 3: 编码（15-20 min）                                   │
│  ├── 先写框架（函数签名、主循环）                            │
│  ├── 再填细节（边界处理、辅助函数）                          │
│  ├── 变量命名清晰（不用 a/b/c）                              │
│  └── 适当注释（复杂逻辑处）                                  │
│                                                             │
│  Step 4: 验证（5-10 min）                                    │
│  ├── 用示例手动模拟执行                                      │
│  ├── 检查边界条件                                            │
│  ├── 分析时间/空间复杂度                                     │
│  └── 讨论可能的优化与扩展                                    │
│                                                             │
└─────────────────────────────────────────────────────────────┘

3.5 算法选择决策树

flowchart TD
    A[题目] --> B{求最值?}
    B -->|是| C{子问题重叠?}
    B -->|否| D{求所有方案?}
    C -->|是| E[动态规划]
    C -->|否| F{贪心选择性质?}
    F -->|是| G[贪心]
    F -->|否| H[回溯/分支限界]
    D -->|是| H
    D -->|否| I{有序数据?}
    I -->|是| J[二分查找]
    I -->|否| K{最短路径/最少步数?}
    K -->|是| L[BFS / Dijkstra]
    K -->|否| M{区间/连续子数组?}
    M -->|是| N[滑动窗口 / 前缀和]
    M -->|否| O{下一个更大/更小?}
    O -->|是| P[单调栈]
    O -->|否| Q{连通性?}
    Q -->|是| R[并查集 / DFS]
    Q -->|否| S[双指针 / Hash]

3.6 优化链路：暴力→记忆化→DP→状态压缩→位运算

LeetCode Hard 题的优化路径通常遵循以下链路：

暴力解 O(2^n)
   ↓ 记忆化（Memoization）
记忆化搜索 O(n^2)
   ↓ 改为自底向上
迭代 DP O(n^2)
   ↓ 状态压缩（滚动数组）
压缩 DP O(n)
   ↓ 位运算优化（如状态压缩为 bitmask）
位运算 DP O(n * 2^k)

示例链路：LeetCode 198 House Robber

# 1. 暴力递归 O(2^n) - TLE
def rob_brute(nums):
    def dfs(i):
        if i >= len(nums):
            return 0
        return max(dfs(i+1), dfs(i+2) + nums[i])
    return dfs(0)

# 2. 记忆化 O(n) - AC
def rob_memo(nums):
    from functools import lru_cache
    @lru_cache(None)
    def dfs(i):
        if i >= len(nums):
            return 0
        return max(dfs(i+1), dfs(i+2) + nums[i])
    return dfs(0)

# 3. 迭代 DP O(n) - AC
def rob_dp(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

# 4. 状态压缩 O(n) O(1) - 最优解
def rob_optimal(nums):
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

4. 题型分类与解题模板

4.1 十大题型分类总表

4.2 双指针模板

4.2.1 对撞指针（Two-Pointer from Both Ends）

适用场景：有序数组、回文串、容器类问题。

不变式：left < right 期间收缩区间，每次至少移动一端。

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """对撞指针：有序数组两数之和
    不变式：若 nums[left] + nums[right] == target，则 (left, right) 是唯一解
    时间 O(n)，空间 O(1)
    """
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1  # 和太小，左端右移
        else:
            right -= 1  # 和太大，右端左移
    return []

#include <vector>
using namespace std;

// 对撞指针 C++ 实现
vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int s = nums[left] + nums[right];
        if (s == target) return {left, right};
        else if (s < target) left++;
        else right--;
    }
    return {};
}

// 对撞指针 Java 实现
public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

经典题目：

• LC-11 Container With Most Water：对撞指针，每次移动较短边
• LC-15 3Sum：排序 + 对撞指针，复杂度 $O(n^2)$
• LC-42 Trapping Rain Water：对撞指针，水桶效应
• LC-125 Valid Palindrome：左右字符比较

4.2.2 快慢指针（Fast-Slow Pointer）

适用场景：原地去重、环检测、链表中点。

def remove_duplicates(nums: list[int]) -> int:
    """快慢指针：原地去重
    不变式：nums[0..slow] 为去重后的数组
    时间 O(n)，空间 O(1)
    """
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

链表环检测（Floyd 判圈）：

def has_cycle(head) -> bool:
    """Floyd 判圈算法
    不变式：若有环，快指针必然追上慢指针
    时间 O(n)，空间 O(1)
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

4.3 滑动窗口模板

适用场景：连续子数组/子串的最值、计数问题。

框架（labuladong 滑动窗口模板）：

def sliding_window(s: str, t: str) -> list[int]:
    """滑动窗口通用模板
    不变式：window 始终维护 [left, right] 的字符计数
    时间 O(n)，空间 O(k)，k 为字符集大小
    """
    from collections import Counter
    need = Counter(t)
    window = Counter()
    left = 0
    valid = 0
    result = []

    for right, ch in enumerate(s):
        # 1. 扩大窗口
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            valid += 1

        # 2. 收缩窗口
        while valid == len(need):
            # 更新答案
            if right - left + 1 == len(t):
                result.append(left)
            left_ch = s[left]
            if left_ch in need and window[left_ch] == need[left_ch]:
                valid -= 1
            window[left_ch] -= 1
            left += 1

    return result

#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

// 最小覆盖子串 LC-76
string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    int left = 0, valid = 0, start = 0, minLen = INT_MAX;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            char d = s[left];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

import java.util.HashMap;
import java.util.Map;

// 最小覆盖子串 Java 实现
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int left = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++;
        }
        while (valid == need.size()) {
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            char d = s.charAt(left);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

经典题目：

• LC-3 Longest Substring Without Repeating Characters：最长无重复子串
• LC-76 Minimum Window Substring：最小覆盖子串（Hard）
• LC-438 Find All Anagrams in a String：找所有字母异位词
• LC-239 Sliding Window Maximum：滑动窗口最大值（Hard，需单调队列）

4.4 二分查找模板

4.4.1 三种二分模板

模板一：标准二分（找精确目标）

def binary_search(nums: list[int], target: int) -> int:
    """标准二分：找精确目标
    不变式：若 target 在 nums 中，则必在 [left, right] 区间内
    时间 O(log n)，空间 O(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

模板二：左边界（找第一个 >= target）

def find_left_bound(nums: list[int], target: int) -> int:
    """左边界二分：找第一个 >= target 的位置
    不变式：left 始终指向可能的答案位置
    时间 O(log n)，空间 O(1)
    """
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

模板三：右边界（找最后一个 <= target）

def find_right_bound(nums: list[int], target: int) -> int:
    """右边界二分：找最后一个 <= target 的位置
    时间 O(log n)，空间 O(1)
    """
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left - 1

4.4.2 旋转排序数组二分

def search_rotated(nums: list[int], target: int) -> int:
    """旋转排序数组搜索 LC-33
    关键：判断 mid 落在左半段还是右半段
    时间 O(log n)，空间 O(1)
    """
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 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

经典题目：

• LC-33 Search in Rotated Sorted Array：旋转数组搜索
• LC-34 Find First and Last Position：左右边界
• LC-69 Sqrt(x)：浮点/整数二分
• LC-153 Find Minimum in Rotated Sorted Array：旋转数组最小值
• LC-4 Median of Two Sorted Arrays：二分答案 Hard

4.5 回溯模板

def backtrack_template(nums: list[int]) -> list[list[int]]:
    """回溯通用模板
    核心思想：DFS + 选择/撤销选择
    时间 O(2^n * n)，空间 O(n)
    """
    result = []

    def backtrack(path: list[int], choices: list[int]):
        # 触发结束条件
        if len(path) == len(nums):
            result.append(path[:])
            return
        for choice in choices:
            # 剪枝
            if choice in path:
                continue
            # 做选择
            path.append(choice)
            backtrack(path, choices)
            # 撤销选择
            path.pop()

    backtrack([], nums)
    return result

组合总和（带起始位置避免重复）：

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """组合总和 LC-39
    关键：用 start 参数避免重复组合
    时间 O(2^n)，空间 O(n)
    """
    result = []

    def backtrack(start: int, path: list[int], remaining: int):
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i 而非 i+1，因为可重复使用
            path.pop()

    backtrack(0, [], target)
    return result

子集去重：

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """子集 II LC-90 含重复元素
    关键：排序 + 跳过同层相同元素
    时间 O(2^n * n)，空间 O(n)
    """
    nums.sort()
    result = []

    def backtrack(start: int, path: list[int]):
        result.append(path[:])
        for i in range(start, len(nums)):
            # 同层去重
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

#include <vector>
#include <functional>
using namespace std;

// 组合总和 C++ 实现
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> path;
    function<void(int, int)> backtrack = [&](int start, int remaining) {
        if (remaining == 0) { result.push_back(path); return; }
        if (remaining < 0) return;
        for (int i = start; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            backtrack(i, remaining - candidates[i]);
            path.pop_back();
        }
    };
    backtrack(0, target);
    return result;
}

经典题目：

• LC-46 Permutations：全排列
• LC-78 Subsets：子集
• LC-39 Combination Sum：组合总和
• LC-22 Generate Parentheses：括号生成
• LC-51 N-Queens：N 皇后 Hard
• LC-37 Sudoku Solver：数独求解 Hard

4.6 BFS / DFS 模板

4.6.1 BFS 模板（最短路径）

from collections import deque

def bfs_shortest_path(graph: dict, start: int, end: int) -> int:
    """BFS 求无权图最短路径
    不变式：队列中所有节点距 start 的距离单调递增
    时间 O(V + E)，空间 O(V)
    """
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

层序遍历：

def level_order(root) -> list[list[int]]:
    """二叉树层序遍历 LC-102
    时间 O(n)，空间 O(n)
    """
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            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

4.6.2 DFS 模板（连通性、拓扑排序）

def dfs_template(root):
    """二叉树 DFS 递归模板
    时间 O(n)，空间 O(h)，h 为树高
    """
    if not root:
        return 0  # base case
    left_result = dfs_template(root.left)
    right_result = dfs_template(root.right)
    return combine(left_result, right_result, root)

拓扑排序（Kahn 算法）：

from collections import deque, defaultdict

def topological_sort(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """拓扑排序 LC-210 Course Schedule II
    不变式：每次入队 0 入度节点，处理时其邻居入度 -1
    时间 O(V + E)，空间 O(V + E)
    """
    in_degree = [0] * num_courses
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == num_courses else []

经典题目：

• LC-200 Number of Islands：DFS/BFS 连通分量
• LC-127 Word Ladder：BFS 最短路径
• LC-207 Course Schedule：拓扑排序判环
• LC-210 Course Schedule II：拓扑排序输出
• LC-743 Network Delay Time：Dijkstra 最短路径

4.7 单调栈模板

适用场景：寻找”下一个更大/更小元素”。

def next_greater_element(nums: list[int]) -> list[int]:
    """单调栈：下一个更大元素 LC-496
    不变式：栈中元素单调递减（栈底到栈顶）
    时间 O(n)，空间 O(n)
    """
    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

#include <vector>
#include <stack>
using namespace std;

// 每日温度 LC-739
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> result(n, 0);
    stack<int> stk;  // 存索引
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
            result[stk.top()] = i - stk.top();
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

经典题目：

• LC-496 Next Greater Element I：下一个更大元素
• LC-739 Daily Temperatures：每日温度
• LC-84 Largest Rectangle in Histogram：柱状图最大矩形 Hard
• LC-42 Trapping Rain Water：接雨水 Hard（也可用对撞指针）
• LC-239 Sliding Window Maximum：滑动窗口最大值（单调队列）Hard

4.8 前缀和与差分

4.8.1 前缀和

class PrefixSum:
    """前缀和：O(1) 区间求和
    构造 O(n)，查询 O(1)
    """
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def range_sum(self, left: int, right: int) -> int:
        """返回 nums[left..right] 的和"""
        return self.prefix[right + 1] - self.prefix[left]

4.8.2 差分数组

class DifferenceArray:
    """差分数组：O(1) 区间修改
    构造 O(n)，区间修改 O(1)，还原 O(n)
    """
    def __init__(self, nums: list[int]):
        self.diff = [0] * len(nums)
        self.diff[0] = nums[0]
        for i in range(1, len(nums)):
            self.diff[i] = nums[i] - nums[i - 1]

    def range_add(self, left: int, right: int, val: int) -> None:
        """[left, right] 区间加 val"""
        self.diff[left] += val
        if right + 1 < len(self.diff):
            self.diff[right + 1] -= val

    def get_result(self) -> list[int]:
        result = [self.diff[0]]
        for i in range(1, len(self.diff)):
            result.append(result[-1] + self.diff[i])
        return result

经典题目：

• LC-303 Range Sum Query - Immutable：前缀和入门
• LC-304 Range Sum Query 2D - Immutable：二维前缀和
• LC-560 Subarray Sum Equals K：前缀和 + 哈希
• LC-1109 Corporate Flight Bookings：差分数组
• LC-1094 Car Pooling：差分数组应用

4.9 动态规划模板

4.9.1 DP 解题三要素

1. 状态定义：dp[i] 或 dp[i][j] 表示什么？
2. 转移方程：dp[i] 如何由更小的子问题得到？
3. 初始条件与边界：dp[0]、dp[1] 是什么？

4.9.2 一维 DP 模板

def climbing_stairs(n: int) -> int:
    """爬楼梯 LC-70
    状态：dp[i] = 爬到第 i 阶的方法数
    转移：dp[i] = dp[i-1] + dp[i-2]
    初始：dp[0] = 1, dp[1] = 1
    时间 O(n)，空间 O(1)
    """
    if n <= 2:
        return n
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

def house_robber(nums: list[int]) -> int:
    """打家劫舍 LC-198
    状态：dp[i] = 前 i 个房子能偷的最大金额
    转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    时间 O(n)，空间 O(1)
    """
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

4.9.3 二维 DP 模板

def longest_common_subsequence(text1: str, text2: str) -> int:
    """最长公共子序列 LC-1143
    状态：dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度
    转移：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])
    时间 O(mn)，空间 O(mn) 可压缩为 O(min(m,n))
    """
    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]

4.9.4 编辑距离（Hard）

def edit_distance(word1: str, word2: str) -> int:
    """编辑距离 LC-72 Hard
    状态：dp[i][j] = word1[:i] 转换为 word2[:j] 的最少操作数
    转移：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])  # 替换
    时间 O(mn)，空间 O(mn)
    """
    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]

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 编辑距离 C++ 实现
int editDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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];
}

经典 DP 题目：

• LC-70 Climbing Stairs：入门 DP
• LC-198 House Robber：一维 DP
• LC-300 Longest Increasing Subsequence：LIS（二分优化 $O(n \log n)$）
• LC-322 Coin Change：完全背包
• LC-72 Edit Distance：二维 DP Hard
• LC-1143 Longest Common Subsequence：LCS
• LC-139 Word Break：字符串 DP
• LC-312 Burst Balloons：区间 DP Hard

4.10 位运算技巧

def count_bits(n: int) -> list[int]:
    """比特位计数 LC-338
    利用 n & (n-1) 去掉最低位 1
    时间 O(n)，空间 O(n)
    """
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i & (i - 1)] + 1
    return result

经典题目：

• LC-136 Single Number：异或找单数
• LC-338 Counting Bits：比特位计数
• LC-461 Hamming Distance：汉明距离
• LC-78 Subsets：位运算枚举子集
• LC-526 Beautiful Arrangement：状态压缩 DP

5. 对比分析

5.1 在线评测平台对比

5.1.1 面试导向平台对比

LeetCode 的核心优势：

1. 题库覆盖完整：3500+ 题目覆盖所有面试高频考点，每题均有官方题解与社区题解
2. 公司标签精准：可按 Google/Meta/Amazon/字节/腾讯等公司筛选题目
3. 多语言一致：14 种语言支持，题目描述与测试用例在各语言间一致
4. 周赛/双周赛：每周日 10:30（北京时间）周赛，每周六 22:30 双周赛
5. LeetCode 75/Hot 100/Top Interview 150：官方系统化刷题清单

HackerRank 的差异：

• 偏向企业招聘场景：与 3000+ 企业合作，提供 HackerRank for Work
• 题目风格更多样：含 SQL、Shell、函数式编程、统计等非算法题
• 评测严格度略低：部分题目测试用例较弱
• 公司标签弱：缺少 FAANG 真实面试题标签

CodeSignal 的差异：

• 通用能力评估（GCA）模式：4 题 70 分钟，含 Quiz + Bug Fix + Coding
• 与 Asana、Dropbox、Reddit 等公司合作作为初筛工具
• 题目风格偏向工程化，与 LeetCode 算法风格略有差异
• 题库较小（800+）

牛客网的差异：

• 中国市场最大：含企业笔试真题（字节、腾讯、阿里秋招笔试）
• 笔试模拟：可参加企业官方笔试，体验真实招聘流程
• 面经社区丰富：含 FAANG/中国大厂面试经验分享
• 算法题质量参差：部分题目描述与测试用例不如 LeetCode 严谨

5.1.2 竞赛导向平台对比

Codeforces vs AtCoder：

Codeforces 评分段位对应能力：

• 1200 以下（Newbie）：刚入门，能做 A 题
• 1400-1599（Specialist）：能稳定做出 B-C 题
• 1600-1899（Expert）：能稳定做出 C-D 题
• 1900-2099（Candidate Master）：能稳定做出 D-E 题，相当于 LeetCode Hard
• 2100-2299（Master）：能做出 E-F 题，接近 ICPC 区域赛水平
• 2400-2599（Grandmaster）：能做出 F-G 题，ICPC World Finals 选手水平
• 2600+（International Grandmaster）：全球顶尖选手，Code Jam/Hacker Cup 常客

5.2 FAANG 与国内大厂面试风格对比

5.2.1 FAANG 面试风格

Google 面试特点：

• 题目偏原创：少有 LeetCode 原题，多为变形题
• 复杂度要求高：必须给出最优解，且证明最优
• 沟通占比高：思路讲解占面试时间 40%+
• 编码白板： onsite 通常用 Google Doc 或白板

Meta 面试特点：

• 速度优先：45 分钟内通常需完成 2 题
• Bug Free 要求：写完即可运行，要求无 bug
• 题目偏向中高频：双指针、BFS、树遍历为主
• 不要求最优解：可行解即可，但代码必须正确

Amazon 面试特点：

• Leadership Principles（LP）：16 条 LP 占面试评估 50%+
• 算法题相对简单：Medium 难度为主
• 系统设计权重高：Senior+ 几乎必有系统设计
• Bar Raiser 制度：跨部门面试官有否决权

5.2.2 国内大厂面试风格

字节跳动面试特点：

• 题目难度高：Hard 题占比高于 FAANG 平均
• 手撕代码：要求在白板或纸上完整写出
• 八股文密集：操作系统、网络、数据库深度提问
• 流程紧凑：通常 1 周内完成全部面试

腾讯面试特点：

• 基础优先：链表、树、排序等经典题型为主
• 变形题多：在标准题基础上修改条件
• 重视八股：操作系统、网络协议深度提问
• 部门差异大：WXG（微信）> IEG（互娱）> CSIG（云）

阿里巴巴面试特点：

• 场景题多：结合淘宝/支付宝业务场景
• 工程理解：要求理解分布式、中间件
• 交叉面：跨部门面试官评估
• HRBP 面权重高：价值观匹配重要

5.3 刷题清单对比

选择建议：

• 0-50 题（入门）：LeetCode 75 → Blind 75 → 剑指 Offer
• 50-150 题（进阶）：NeetCode 150 → Top Interview 150
• 150-300 题（精通）：Grind 300 → LeetCode Hot 100 → 公司标签专项
• 300+ 题（竞赛级）：Codeforces Div2/Div1 → AtCoder ABC/ARC → ICPC Gym

5.4 Python vs C++ vs Java 面试语言选择

选择建议：

• 面试新手：Python（编码快，思路优先）
• C++ 背景：C++（性能优势，竞赛季）
• Java 背景：Java（企业级，阿里/字节偏好）
• 多语言策略：Python 为主，C++ 为辅（应对 Hard 题）

6. 常见陷阱

6.1 陷阱一：二分查找边界处理错误

::: danger 错误示例：在写二分查找时，while left <= right 与 while left < right 混用，导致死循环或漏解。

# 错误：左边界二分使用 <= 导致死循环
def find_left_wrong(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:  # 错误：应为 left < right
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid  # 当 left == right 时进入死循环
    return left

错误原因：左边界二分中，right = mid 而非 right = mid - 1，当 left == right 时 mid == left == right，再次进入循环导致死循环。

修正方案：

def find_left_correct(nums, target):
    left, right = 0, len(nums)  # 注意 right = len(nums) 而非 len(nums) - 1
    while left < right:  # 不含等号
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

记忆口诀：

• 左边界：right = len(nums)，while left < right，right = mid
• 右边界：right = len(nums)，while left < right，left = mid + 1（nums[mid] <= target 时），返回 left - 1
• 精确匹配：right = len(nums) - 1，while left <= right，left = mid + 1 / right = mid - 1 :::

6.2 陷阱二：滑动窗口收缩条件错误

::: danger 错误示例：在最小覆盖子串问题中，收缩条件使用 while len(window) == len(need) 而非 valid == len(need)，导致漏解。

# 错误：用 window 字典大小判断而非 valid 计数
def min_window_wrong(s, t):
    from collections import Counter
    need = Counter(t)
    window = Counter()
    left = 0
    min_len = float('inf')
    for right, ch in enumerate(s):
        window[ch] += 1
        # 错误：window 包含 s 中所有字符，而 need 只含 t 中字符
        while len(window) == len(need):  # 永远不会相等，因为 window 会无限增长
            ...

错误原因：window 字典记录的是当前窗口所有字符的计数，会包含 need 中不存在的字符。len(window) == len(need) 在 s 含 t 中不存在字符时永远不成立。

修正方案：

def min_window_correct(s, t):
    from collections import Counter
    need = Counter(t)
    window = Counter()
    left = 0
    valid = 0  # 记录有多少字符的计数已满足 need
    min_len = float('inf')
    start = 0
    for right, ch in enumerate(s):
        if ch in need:
            window[ch] += 1
            if window[ch] == need[ch]:
                valid += 1
        while valid == len(need):  # 正确：用 valid 判断
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            left_ch = s[left]
            if left_ch in need:
                if window[left_ch] == need[left_ch]:
                    valid -= 1
                window[left_ch] -= 1
            left += 1
    return s[start:start + min_len] if min_len != float('inf') else ""

:::

6.3 陷阱三：动态规划初始条件错误

::: danger 错误示例：在编辑距离问题中，未初始化 dp[i][0] 与 dp[0][j]，导致结果错误。

# 错误：未初始化边界
def edit_distance_wrong(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 错误：未初始化 dp[i][0] = i 和 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]  # 永远偏小，因为 dp[i][0] 和 dp[0][j] 均为 0

错误原因：编辑距离的语义是 dp[i][j] = 将 word1[:i] 转为 word2[:j] 的最少操作数。当 j=0 时，需删除 i 个字符；当 i=0 时，需插入 j 个字符。未初始化意味着 dp[i][0] = 0，但实际应为 i。

修正方案：

def edit_distance_correct(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  # word1[:i] 转为空串需删除 i 次
    for j in range(n + 1):
        dp[0][j] = j  # 空串转为 word2[: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]

:::

6.4 陷阱四：回溯未做去重

::: danger 错误示例：在含重复元素的子集问题中，未排序+跳过同层相同元素，导致结果含重复子集。

# 错误：含重复元素未去重
def subsets_with_dup_wrong(nums):
    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  # nums=[1,2,2] 时返回 [[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]
                    # 含重复的 [1,2] 和 [2]

错误原因：当 nums = [1, 2, 2] 时，从索引 0 开始选 1，再从索引 1 开始选 2 得到 [1,2]；之后回溯到索引 1，跳过索引 1 的 2，从索引 2 开始选 2 又得到 [1,2]。同样，从索引 1 开始选 2 得 [2]，从索引 2 开始选 2 也得 [2]。

修正方案：

def subsets_with_dup_correct(nums):
    nums.sort()  # 排序使相同元素相邻
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            # 关键：i > start 时跳过同层相同元素
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

:::

6.5 陷阱五：整数溢出与边界处理

::: danger 错误示例：在两数之和或斐波那契问题中，未考虑负数、极大值或整数溢出。

# 错误：二分查找 mid 计算溢出
def binary_search_overflow(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2  # 错误：left + right 在 C++/Java 中可能溢出
        ...

错误原因：在 C++/Java 中，int 类型最大值为 $2^{31} - 1 \approx 2.1 \times 10^9$。当 left + right 超过此值时，会发生整数溢出，导致 mid 为负数。

修正方案：

# 修正：使用 left + (right - left) // 2 防溢出
def binary_search_safe(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 安全：right - left 必为非负
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

// C++ 中同样问题，需用 unsigned 或 left + (right - left) / 2
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

:::

6.6 陷阱六：图遍历未标记 visited

::: danger 错误示例：在 BFS/DFS 中未标记 visited，导致死循环或重复访问。

# 错误：BFS 未标记 visited
def bfs_wrong(graph, start):
    from collections import deque
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            queue.append(neighbor)  # 错误：未检查是否已访问，有环时死循环
    return result

错误原因：当图中含环时，节点 A 的邻居 B 已入队，B 处理时又会将 A 入队，形成无限循环。即使无环，每个节点也可能被多次访问，复杂度爆炸。

修正方案：

def bfs_correct(graph, start):
    from collections import deque
    visited = {start}
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # 入队时立即标记
                queue.append(neighbor)
    return result

注意：visited 应在入队时标记，而非出队时标记。否则同一节点可能被多次入队，浪费空间。 :::

6.7 陷阱七：Python 递归栈溢出

::: danger 错误示例：在深度大于 1000 的递归（如链表反转）中，触发 Python 默认递归深度限制。

# 错误：深度链表递归反转触发 RecursionError
def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)  # 深度 > 1000 时 RecursionError
    head.next.next = head
    head.next = None
    return new_head

错误原因：Python 默认递归深度限制为 1000（可通过 sys.setrecursionlimit 调整，但仍有上限）。LeetCode 链表题链长可达 $10^4$，必触发递归错误。

修正方案：

# 方案 1：改为迭代
def reverse_list_iterative(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

# 方案 2：提高递归限制（不推荐，可能栈溢出）
import sys
sys.setrecursionlimit(100000)

:::

7. 工程实践

7.1 LeetCode 题目到工业应用的映射

LeetCode 题目并非纯学术练习，许多题目直接映射到工业场景中的真实问题。下表列出典型映射：

7.2 LRU Cache 与 Redis 缓存淘汰

LC-146 LRU Cache 要求设计 $O(1)$ get 与 put 的 LRU 缓存。其工业级实现见于 Redis、Guava Cache、Caffeine 等项目。

Redis 的 LRU 实现：

Redis 采用近似 LRU（Approximated LRU）策略，原因：

1. 精确 LRU 内存开销大：需维护双向链表，每个 key 增加两个指针（16 字节）
2. Redis 单线程模型：链表操作需 O(1)，但全量 LRU 需频繁移动节点
3. 采样近似：随机采样 N 个 key（默认 5），淘汰其中最久未使用的

# LC-146 标准 LRU Cache 实现
class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    """LRU 缓存：哈希表 + 双向链表
    get/put 均摊 O(1)
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> DLinkedNode
        # 虚拟头尾节点，避免空指针判断
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node: DLinkedNode) -> None:
        """在头部之后插入节点（表示最近使用）"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: DLinkedNode) -> None:
        """删除指定节点"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node: DLinkedNode) -> None:
        """将节点移至头部"""
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self) -> DLinkedNode:
        """弹出尾部节点（最久未使用）"""
        node = self.tail.prev
        self._remove_node(node)
        return node

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if not node:
            return -1
        self._move_to_head(node)  # 访问即移至头部
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)
        if node:
            node.value = value
            self._move_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                tail = self._pop_tail()  # 淘汰最久未使用
                del self.cache[tail.key]
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            self._add_node(new_node)

摊还分析（基于 Sleator-Tarjan 1985 势能法）：

设势能函数 $\Phi(D) = 2 \cdot |\text{cache}|$，则：

• get 命中：实际代价 $c_i = 1$（哈希查找）+ 4（链表移动）= 5，势能变化 $\Delta\Phi = 0$，摊还代价 $\hat{c}_i = 5$
• put 淘汰：实际代价 $c_i = 1$（哈希查找）+ 4（链表操作）+ 1（哈希删除）= 6，势能变化 $\Delta\Phi = -2$，摊还代价 $\hat{c}_i = 4$

故 get/put 的摊还代价均为 $O(1)$。

7.3 并查集与 Kubernetes 网络策略

LC-547 Number of Provinces 与 LC-684 Redundant Connection 是并查集（Union-Find）的经典应用。在工业场景中，并查集用于：

• Kubernetes 网络策略：判断 Pod 是否在同一 NetworkPolicy 作用域
• Git merge：合并分支时检测循环依赖
• 图像处理：连通分量标记（Connected Component Labeling）
• 最小生成树：Kruskal 算法的核心数据结构

class UnionFind:
    """并查集：路径压缩 + 按秩合并
    find/union 均摊 O(α(n)) ≈ O(1)，α 为反阿克曼函数
    基于 Tarjan 1975 分析
    """

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 连通分量数

    def find(self, x: int) -> int:
        """路径压缩：查找根节点"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 递归压缩
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """按秩合并：返回是否成功合并（原本不同集合）"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 已在同一集合
        # 小树合并到大树
        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
        self.count -= 1
        return True


def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    """LC-684 冗余连接
    应用：K8s 网络策略循环依赖检测
    时间 O(E α(V))，空间 O(V)
    """
    n = len(edges)
    uf = UnionFind(n + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # 已在同一集合，此边为冗余
    return []

7.4 滑动窗口与 Prometheus 监控

LC-239 Sliding Window Maximum 的单调队列技术被广泛应用于流式数据处理：

• Prometheus Range Query：rate(http_requests_total[5m]) 计算 5 分钟窗口内的请求速率
• Flink Windowed Stream：滑动窗口聚合
• Kafka Streams：时间窗口 Join
• 股票交易：移动平均线、布林带

from collections import deque


class MonotonicQueue:
    """单调队列：支持 O(1) 求滑动窗口最大/最小值
    应用：Prometheus range query、股票移动平均
    """

    def __init__(self):
        self.queue = deque()  # 存索引，对应元素单调递减

    def push(self, nums: list[int], i: int) -> None:
        """入队：维护单调性"""
        while self.queue and nums[self.queue[-1]] <= nums[i]:
            self.queue.pop()
        self.queue.append(i)

    def pop(self, left: int) -> None:
        """出队：移除窗口外的元素"""
        if self.queue and self.queue[0] < left:
            self.queue.popleft()

    def max_index(self) -> int:
        return self.queue[0]


def sliding_window_max(nums: list[int], k: int) -> list[int]:
    """LC-239 滑动窗口最大值
    应用：Prometheus 5min rate 计算
    时间 O(n)，空间 O(k)
    """
    mq = MonotonicQueue()
    result = []
    for i in range(len(nums)):
        mq.push(nums, i)
        if i >= k - 1:
            mq.pop(i - k + 1)  # 窗口左边界
            result.append(nums[mq.max_index()])
    return result

Prometheus 实际实现：Prometheus 使用 chunk 编码 + delta-of-delta 压缩存储时序数据，range query 通过遍历 chunk + 适配窗口聚合实现，本质与单调队列思想类似但更复杂。

7.5 工业级代码风格要求

LeetCode 题解与工业代码存在显著差异。面试中应展示工业级代码风格：

1. 命名规范：

# 反例：单字母命名
def two_sum(a, t):
    s = {}
    for i, n in enumerate(a):
        if t - n in s:
            return [s[t - n], i]
        s[n] = i

# 正例：业务命名
def find_two_sum_indices(nums: list[int], target: int) -> list[int]:
    """在 nums 中找到和为 target 的两个元素的索引
    Args:
        nums: 整数数组
        target: 目标和
    Returns:
        两个索引的列表，若无解返回空列表
    """
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

2. 类型注解：Python 3.5+ 应使用 type hints。

3. 异常处理：

def binary_search(nums: list[int], target: int) -> int:
    """在有序数组中查找 target，返回索引或 -1"""
    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

4. 复杂度声明：函数文档中应注明时间/空间复杂度。

5. 测试用例：面试中应主动提出测试用例：

# 测试用例应覆盖：
# - 正常情况：nums=[2,7,11,15], target=9 → [0,1]
# - 边界情况：nums=[1], target=1 → []（单元素）
# - 重复元素：nums=[3,3], target=6 → [0,1]
# - 负数：nums=[-1,-2,-3], target=-5 → [1,2]
# - 极大值：nums=[2**31-1, 1], target=2**31 → []（溢出测试）

7.6 周赛/双周赛训练策略

LeetCode 周赛（每周日 10:30 北京时间）与双周赛（每周六 22:30）是重要的竞技训练场。

周赛策略：

Rating 提升：

• 周赛 Rating 1800+ 可视为入门完成
• 周赛 Rating 2200+ 可冲击 FAANG 算法面
• 周赛 Rating 2400+ 可考虑转型竞赛选手

8. 案例研究

8.1 案例一：Redis 缓存淘汰策略演进

背景：Redis 4.0 之前仅支持 LRU 与随机淘汰，4.0 引入 LFU（Least Frequently Used），5.0 增加删除策略配置。

LC-146 LRU Cache 的工业演进：

LeetCode 146 (哈希表+双向链表)
       ↓
Redis 2.x (近似 LRU，采样 N=5)
       ↓
Redis 4.0 (LFU，对数计数器 + 衰减)
       ↓
Redis 5.0 (lazy free + 删除策略配置)
       ↓
Redis 7.0 (多线程 IO + 更精细淘汰)

Redis LFU 实现（参考 LC-460）：

Redis 每个 key 用 24 bit 存储 LFU 信息：

• 16 bit：最后访问时间（分钟，约 194 天循环）
• 8 bit：访问计数器（对数计数器，0-255）

对数计数器公式：