数据结构与算法 - 7天面试/机试冲刺¶
目标：7天快速复习核心数据结构与高频算法，以应对技术面试和在线机试 适用：有编程基础的程序员，需要在短时间内恢复算法手感 语言：Java（企业级面试常用，强类型更规范）
🎯 策略总览¶
面试算法考察重点（按频率排序）：
1. 数组/字符串（必考） → 双指针、滑动窗口、前缀和
2. 哈希表（必考） → 两数之和、分组、计数
3. 链表（高频） → 反转、环检测、合并
4. 二叉树（高频） → 遍历、递归、层序BFS
5. 动态规划（中高频） → 背包、子序列、路径
6. 排序/搜索（中频） → 二分查找、快排、归并
7. 栈/队列（中频） → 单调栈、BFS
8. 图（中低频） → DFS/BFS、拓扑排序
9. 贪心（中频） → 区间调度、跳跃游戏
10. 回溯（中频） → 排列组合、子集
数据结构的本质：为什么需要它？¶
【核心思想】数据结构 = 数据的组织方式，目的是让操作更高效
看到一道题或一个业务需求，不要先想「用数组还是哈希表」，而要先问：问题属于哪一类？ 下面是从 industry + 面试里常用的一套抽象分类。
问题的抽象分类（先认「要什么」，再选结构 + 算法）¶
可以从 四个正交维度 给问题贴标签；同一道题往往同时属于多个维度。
维度 1：目标类型（你要的输出是什么？）¶
| 类型 | 在问什么 | 典型问法 | 例子 |
|---|---|---|---|
| 判定 | 是否满足某性质 | 有没有、能不能、是否合法 | 链表有没有环？括号是否匹配？ |
| 检索 | 找到具体对象 | 找下标、找节点、找路径 | 两数之和、BST 查 key |
| 计数 / 聚合 | 有多少、总和、频次 | count、sum、频率 TopK | 子数组和为 K 的个数 |
| 匹配 / 关联 | 两个集合如何对应 | 配对、JOIN、对齐 | 对账、合并有序流、异位词分组 |
| 排序 | 按规则排列 | sort、第 K 大 | 快排、TopK 堆 |
| 优化 | 最优值（最大/最小/最长/最短） | max/min/longest/shortest | 最长无重复子串、盛水、最短路 |
| 枚举 / 构造 | 列出所有解或构造方案 | 所有排列、所有路径、填棋盘 | 全排列、N 皇后、子集 |
| 变换 | 在原数据上改形态 | 去重、反转、合并、压缩 | 删除重复项、合并 K 个链表 |
| 可达 / 依赖 | 连通、顺序、能否完成 | 路径、拓扑、依赖链 | 课程表、岛屿数量 |
用法：先读题填一行——「这是 优化 + 检索」还是「枚举 + 判定」——再往下选工具。
维度 2：数据关系（对象之间是什么结构？）¶
| 关系 | 含义 | 优先想到的结构 |
|---|---|---|
| 线性序列 | 有前后顺序，下标 0…n-1 | 数组、链表、字符串 |
| 键值 / 映射 | 按 key 查 value，或分组 | 哈希表 |
| 层次 | 父子孙、左子右子 | 树、堆 |
| 网络 | 多对多、可成环 | 图 |
| 集合 | 只关心在不在、频次 | 哈希集合、位图 |
| 区间 / 有序 | 范围查询、有序性 | BST、线段树（进阶）、排序+二分 |
维尔特公式：程序 = 数据结构 + 算法 —— 这一维回答「数据长什么样」，决定容器选型。
维度 3：核心操作（最费时间的动作是什么？）¶
Donald Knuth 等早期教材常按 对数据的操作 分类问题：
| 操作 | 含义 | 谁擅长 |
|---|---|---|
| Access 按位置访问 | arr[i] |
数组 O(1) |
| Search 按值查找 | 是否存在、在哪 | 哈希 O(1)；无序数组 O(n)；BST O(log n) |
| Insert / Delete 增删 | 中间插入、删除 | 链表 O(1)；数组 O(n) |
| Sort 排序 | 全序或部分序 | 比较排序 O(n log n)；计数排序等特殊 |
| Min / Max 极值 | 当前最大最小 | 堆 O(1) 取顶；单调栈/队列维护 |
用法：计费对账若 按主键 JOIN → 核心是 Search + 匹配；ETL 去重 → 变换 + 线性扫描。
维度 4：求解策略（算法范式，和数据结构正交）¶
| 策略 | 适用信号 | 与暴力的关系 |
|---|---|---|
| 暴力 / 模拟 | n 小、实现对照 | 基线 |
| 双指针 | 有序、单调、原地、连续区间 | 去掉内层循环 |
| 滑动窗口 | 连续子串/子数组 + 窗口统计 | 去掉重复统计 |
| 前缀和 / 差分 | 多次区间和、区间修改 | 预处理换查询 |
| 二分 | 有序、或答案单调可猜 | 每次砍一半 |
| 分治 | 可拆成独立子问题再合并 | 归并、快排 |
| 贪心 | 局部最优能证全局最优 | 比 DP 快、范围窄 |
| 动态规划 | 重叠子问题 + 最优子结构 | 记忆化 |
| 回溯 | 要 所有 解、可剪枝 | 决策树 DFS |
| BFS / DFS | 图/树上的遍历、最短路层数 | 结构驱动 |
四维 → 一道题的填表练习¶
例：LC 167 两数之和 II（有序数组）
| 维度 | 标签 |
|---|---|
| 目标 | 检索（找一对下标） |
| 关系 | 线性序列 + 有序 |
| 操作 | Search / 匹配 |
| 策略 | 对撞双指针（或哈希，但有序用双指针 O(n)） |
例：日批计费对账（SQL）
| 维度 | 标签 |
|---|---|
| 目标 | 匹配 + 判定（找出差异行） |
| 关系 | 键值 + 表 |
| 操作 | Search + JOIN |
| 策略 | 引擎内 Hash Join / Merge Join（见 双指针 §二） |
例：LC 3 最长无重复子串
| 维度 | 标签 |
|---|---|
| 目标 | 优化（最长长度） |
| 关系 | 线性序列（字符串） |
| 操作 | Scan + 窗口内计数 |
| 策略 | 滑动窗口 + 哈希 |
快速决策：从题面关键词到套路¶
题里出现 … → 先想 …
─────────────────────────────────────────
「连续子数组/子串」「最长/最短」 → 滑动窗口 / 前缀和
「有序」「两数之和」「合并」 → 双指针 / 二分
「所有排列/组合/路径」 → 回溯 / DFS
「重叠子问题」「最优」 → DP / 贪心
「最短路径（边权 1）」「层数」 → BFS
「依赖顺序」「能否完成」 → 拓扑排序（图）
「第 K 大」「实时最值」 → 堆
「O(1) 查某 key」 → 哈希表
「按层/递归结构」 → 树 + DFS/BFS
和数据结构条目的对应关系¶
下面 8 种结构，可以看成在 维度 2（关系）+ 维度 3（操作） 上的最优解封装：
1. 数组（Array）
为什么需要：连续内存存储，支持 O(1) 随机访问
适用场景：频繁按索引访问、数据量固定
劣势：插入/删除需要移动元素 O(n)
对比链表：数组快在访问，慢在修改；链表相反
2. 链表（Linked List）
为什么需要：解决数组插入/删除慢的问题
适用场景：频繁插入/删除、数据量动态变化
劣势：不支持随机访问，查找 O(n)
对比数组：链表快在修改，慢在访问
3. 哈希表（Hash Table）
为什么需要：把查找从 O(n) 降到 O(1)
适用场景：快速查找、去重、计数、映射关系
劣势：无序、空间开销大、哈希冲突
对比数组：用空间换时间，查找快但不支持范围查询
4. 栈（Stack）
为什么需要：LIFO（后进先出），匹配"撤销/回退"场景
适用场景：括号匹配、函数调用、表达式求值、单调性维护
对比队列：栈是"后进先出"，队列是"先进先出"
5. 队列（Queue）
为什么需要：FIFO（先进先出），匹配"排队"场景
适用场景：BFS、任务调度、生产者消费者
对比栈：队列保证顺序处理，栈保证最近处理
6. 二叉树（Binary Tree）
为什么需要：解决线性结构查找慢的问题，O(log n) 查找
适用场景：层次关系、范围查询、排序（BST）
对比哈希表：树支持范围查询和有序遍历，哈希表不支持
7. 图（Graph）
为什么需要：表达多对多关系（不是简单的层级）
适用场景：社交网络、路径规划、依赖关系
对比树：图可以有环、可以有多个父节点
8. 堆（Heap）
为什么需要：快速获取最大/最小值 O(1)，插入/删除 O(log n)
适用场景：TopK 问题、优先队列、调度
对比数组：数组找最值 O(n)，堆 O(1)
算法设计的本质：为什么这样抽象？¶
【核心思想】算法 = 解决问题的步骤，目的是在有限资源下最优求解
1. 双指针
为什么有效：把 O(n²) 暴力枚举降到 O(n)
本质：利用单调性或有序性，避免重复计算
对比暴力：暴力是"所有组合都试"，双指针是"有方向地逼近"
2. 滑动窗口
为什么有效：避免重复遍历子数组/子串
本质：窗口滑动时，复用之前的计算结果
对比暴力：暴力每次重新计算窗口，滑动窗口增量更新
3. 二分查找
为什么有效：每次排除一半，O(log n) 而不是 O(n)
本质：利用有序性，"猜大小"快速定位
前提：必须有序或具有单调性
4. 分治（Divide & Conquer）
为什么有效：大问题拆成小问题，递归解决后合并
本质：化繁为简，小问题更容易解决
典型：归并排序、快速排序、二叉树遍历
5. 动态规划（DP）
为什么有效：避免重复计算子问题（记忆化）
本质：空间换时间，存储中间结果
对比贪心：DP 考虑所有可能，贪心只看眼前最优
对比回溯：DP 有重叠子问题，回溯是枚举所有解
6. 贪心（Greedy）
为什么有效：每一步选局部最优，最终得到全局最优
本质：问题具有"贪心选择性质"和"最优子结构"
对比 DP：贪心不回溯，效率更高，但适用范围更窄
7. 回溯（Backtracking）
为什么有效：系统地枚举所有可能解
本质：决策树的 DFS，走不通就撤销选择
对比暴力：回溯有剪枝，暴力是完全枚举
8. BFS vs DFS
BFS 为什么有效：按层遍历，找最短路径
DFS 为什么有效：递归深入，找连通性/所有解
对比：BFS 用队列（空间大），DFS 用栈/递归（空间小）
头晕脑胀还想学时：低电量模式¶
原则：不是「今天学多少」，而是「今天别把自己学废，且留下一点正反馈」。
| 状态 | 建议 |
|---|---|
| 还能坐住、但转不动 | 只复习 1 个已懂的概念（如双指针 = 两个下标有方向地动），不写新题 |
| 略晕但想碰代码 | 做 1 道 Easy 做过的题（如 LC 26 去重），要求：能口述每一步 即可 |
| 很晕 | 停。散步 10 分钟、喝水、闭眼；明天 20 分钟再战 |
| 焦虑「进度落后」 | 7 天冲刺是 弹性表，不是 KPI；少学 1 天 ≠ 失败 |
今天 20 分钟套餐（任选其一，做完就停）：
A. 复习模式（零压力）
→ 打开 [双指针.md](./双指针.md)，只读「场景 1 财务对账」那张逐步表
→ 合上文档，用自己的话讲一遍：和太大动哪边？
B. 手感模式（轻量）
→ LeetCode 167 或 26，**看过题解也行**，手写一遍，不对就对着改
→ 成功运行 1 次 = 今日胜利
C. 整理模式（不动脑）
→ 在纸上画 `[2,7,11,15]`，标 left/right 走 3 步
→ 画完拍照/夹进笔记 = 今日胜利
不要同时在做的几件事：
- 不要新开 DP、图、回溯等 新专题
- 不要一次刷 5 题
- 不要硬啃「问题的四维分类」——那是 清醒日 用的地图，不是疲劳日任务
- 不要和别人比进度
想学的念头留着，本身就是好事。 疲劳时 保火种（一点理解 + 一点手感）比 烧光（硬撑 3 小时然后一周不想碰）划算。
如何克制「深挖、钻牛角尖」的欲望？¶
不是消灭好奇心，而是给好奇心 停车位 + 熄火键。
钻牛角尖 = 问题已经 够用，你还在为 不属于当前目标 的细节付无限时间（例：为面试二分，却连读三周明清数学史）。
先分清：两种「想深入」¶
| 类型 | 感觉 | 该不该跟 |
|---|---|---|
| 主线深入 | 直接提高 今天目标（AC、讲清模板、上线对账） | ✅ 跟，但设 时间盒 |
| 支线沉迷 | 很爽，但与 本周目标无关（证明推广、历史考据、源码每一行） | ⏸ 记入 停车场，改天专门开 |
克制 ≠ 不学深；克制 = 深在对的题、在对的日子。
五条硬规则（建议写进笔记首页或便签）¶
1. 开场 30 秒：只写一句「今日胜利条件」
❌ 「今天学数学」
✅ 「今天能口述：为何二分是 O(log n)，并手写 LC 704」
✅ 「今天 DDIA：只读完 Ch.3 哈希索引小结，能画一张图」
没有胜利条件 → 大脑默认胜利 = 「搞懂一切」 → 必钻牛角。
2. 够用止损线（Good enough）—— 提前写好
| 主题 | 够用（停） | 牛角尖（停手信号） |
|---|---|---|
| 对数 | 能说清 log = 减半次数；会估 n, log n, n², 2ⁿ 量级 | 推全泰勒展开、复变函数 |
| 双指针 | 会判场景 + 写 LC 167/11 之一 | 证明最优性、读遍所有变体论文 |
| DDIA | 懂动机 + 一张图 + 能讲给同事 | 每脚注、每篇引用论文 |
| 中国数学史 | 知道「有 + 为何课本像没有」 | 乾嘉学派全套考证 |
| B+ 树 | 面试 + 和哈希索引对比 | InnoDB 每一页字节布局 |
出现「停手信号」行 → 立刻把问题扔进 停车场，今日算赢。
3. 时间盒 + 闹钟
- 主线学习：25～45 分钟 一块，闹钟响 必须停（写 3 句小结即可）。
- 允许 每周 1 次「深挖下午茶」（90～120 分钟）：只处理停车场里 挑过优先级 的 1 条——乐趣在这里释放，不占每日。
4. 停车场（Parking lot）—— 满足求知欲但不当场付账
本子或文档一角，格式固定：
[日期] 问题（一句话） | 为何好奇 | 何时处理（周末/面试后/永不）
例：四库禁毁具体书目清单 | 接明清数学 | 面试后 optional
写进去 = 大脑收到「没丢」，冲动会明显下降。
5. 两问刹车片（想再查资料前必问）
- 「这能让我下周多做对一道题 / 多讲清一次需求吗？」 —— 否 → 停车场。
- 「若现在停，我会不会连当前这层都讲不清？」 —— 否 → 停；是 → 再 15 分钟 时间盒。
心理层：为什么你会想钻？¶
| 原因 | 更健康做法 |
|---|---|
| 深挖带来 确定感（世界可理解） | 用 小胜利 代替大圆满：今天只完成胜利条件 |
| 怕 浅 = 假懂 | 浅的标准改成 能复述 + 能写最小代码；深留到停车场 |
| 逃避 硬题/面试焦虑 | 读历史、读证明像学习 → 其实是 舒适区；先 1 道 Easy/复习 |
| 信息过载后想 一次搞懂 | 接受 分层：第 1 层数量感，第 4 层符号；见 数学基础·乐趣与感知 |
和 DDIA / 数学史 / 面试的配平¶
当前主目标（示例） 允许深的范围 默认停车场
─────────────────────────────────────────────────────────────
7 天算法冲刺 模板 + 15 题清单内 证明、变体全集
DDIA 6h 冲刺 框架文档勾选章节 全书脚注、论文
数学基础复习 §3.1 指数对数 + 1 题 明清史、四库细节
历史与乐趣：当 调味料（每次 ≤10 分钟故事），不当 主菜——除非你把「科学史」本身设为当月主目标。
钻了怎么办（温和撤退，不自责）¶
- 别否定好奇心——记一句：「这条有价值，但不在今日合同里。」
- 用 3 句话 封存当前收获，写入停车场。
- 做一个 5 分钟「回归主线」（画双指针图 / 读冲刺表下一行）。
- 今天到此为止也算胜利——止损是技能，不是失败。
今日若只想练「刹车」¶
1. 写今日胜利条件（一句话）
2. 学 25 分钟，闹钟响 → 停
3. 若还想继续 → 只能写进停车场，或改约「周末深挖」
4. 用 5 分钟做一件主线小事（复习 LC 26 或 DDIA 一张图）
一句话：克制深挖 = 胜利条件 + 够用止损 + 时间盒 + 停车场 + 两问刹车；好奇心上周末，平时 保主线、留火种。
相关：数学基础·数学的乐趣 · 低电量模式
每日时间安排（建议6-8小时/天）¶
09:00-12:00 3小时 知识点复习 + 模板背诵
14:00-17:00 3小时 LeetCode刷题（按专题）
20:00-22:00 2小时 模拟机试 / 错题回顾
📅 Day 1：数组 + 双指针 + 滑动窗口¶
专题深读：数组：历史渊源、业务场景与模板 | 双指针：具体场景与推演
核心知识点¶
为什么需要这些技巧？¶
数组的本质困境（Array's Fundamental Dilemma）： - 优势（Advantages）：连续内存（Contiguous Memory）、O(1) 随机访问（Random Access）、缓存友好（Cache-friendly） - 劣势（Disadvantages）：插入/删除需要移动元素 O(n)、大小固定（Fixed Size） - 核心问题（Core Problem）：如何在数组上高效地查找、匹配、统计？
双指针的设计动机（Two Pointers Design Motivation）：
- 问题背景（Problem Context）：
- 示例问题：在有序数组 [2, 7, 11, 15] 中找到两个数，使它们的和等于 target = 9
- 暴力法的问题（Brute-force Problem）：需要枚举所有组合 (2,7), (2,11), (2,15), (7,11), (7,15), (11,15)，时间复杂度 O(n²)
- 核心痛点：没有利用"数组已排序"这个关键信息，做了大量无用比较
- 双指针的突破（Two Pointers Breakthrough）：
- 核心思路：利用有序性（Sorted Property），两个指针从两端向中间逼近
- 工作原理：
初始：left=0(值2), right=3(值15), sum=17 > 9, 说明 right 太大，right-- 第二步：left=0(值2), right=2(值11), sum=13 > 9, 说明 right 太大，right-- 第三步：left=0(值2), right=1(值7), sum=9 == 9, 找到答案！ -
为什么有效（Why it Works）：
- 如果 nums[left] + nums[right] < target，说明当前和太小，必须增大，只能 left++（因为 right 已经是当前最大的）
- 如果 nums[left] + nums[right] > target，说明当前和太大，必须减小，只能 right--（因为 left 已经是当前最小的）
- 每次移动都能排除一行或一列的组合，不会遗漏
-
优势对比（Advantages Comparison）：
- 时间复杂度：暴力法 O(n²) → 双指针 O(n)，提升 n 倍
- 空间复杂度：都是 O(1)，不需要额外空间
-
关键差异：双指针利用了"单调性"（Monotonicity），暴力法是盲目枚举
-
适用前提（Prerequisites）：
- 数组必须有序（Sorted），或者具有单调性（Monotonicity）
- 如果是无序数组，需要先排序 O(n log n)，总体还是优于暴力法 O(n²)
滑动窗口的设计动机（Sliding Window Design Motivation）：
- 问题背景（Problem Context）：
- 示例问题：在字符串 "abcabcbb" 中找到最长无重复字符的子串
- 暴力法的问题（Brute-force Problem）：
从每个起点开始枚举所有可能的子串：
起点0: "a", "ab", "abc", "abca"(重复!), "abcab"(重复!)...
起点1: "b", "bc", "bca", "bcab"(重复!)...
需要 O(n²) 个子串检查，每次检查是否重复需要 O(n)
总时间复杂度 O(n³) 或优化后 O(n²)
- 滑动窗口的突破（Sliding Window Breakthrough）：
- 核心思路：窗口扩大时记录状态（State Tracking），缩小时复用之前的计算结果
- 工作原理：
初始：window="a", maxLen=1 扩大：window="ab", maxLen=2 扩大：window="abc", maxLen=3 遇到重复'a'：缩小窗口直到移除第一个'a'，window="bca" 继续扩大：window="bcab"(重复!) → 缩小 → window="cab" 最终找到最长子串 "abc"，长度3 -
为什么有效（Why it Works）：
- 每个元素最多进出窗口一次，避免了重复检查
- 利用哈希表记录窗口内字符的出现次数，O(1) 判断是否重复
- 时间复杂度从 O(n²) 降到 O(n)
-
优势对比（Advantages Comparison）：
- 时间复杂度：暴力法 O(n²) → 滑动窗口 O(n)，提升 n 倍
- 状态复用：窗口移动时只需更新变化的部分，不需要重新计算
- 适用场景（Use Cases）：
- 连续子数组/子串问题（Subarray/Substring Problems）
- 需要维护窗口内状态（最大值、和、无重复等）
- 典型的"找最长/最短连续子数组"问题
前缀和的设计动机（Prefix Sum Design Motivation）：
- 问题背景（Problem Context）：
- 示例问题：给定数组 [1, 2, 3, 4, 5]，频繁查询区间和，如 sum[1,3], sum[0,4], sum[2,4]...
- 暴力法的问题（Brute-force Problem）：
查询 sum[1,3]（即 nums[1]+nums[2]+nums[3]）：
每次都需要遍历：2+3+4 = 9，时间复杂度 O(n)
如果有 m 次查询，总时间复杂度 O(m*n)
- 前缀和的突破（Prefix Sum Breakthrough）：
- 核心思路：预处理一次 O(n)（Preprocessing），之后每次查询 O(1)
- 工作原理：
原数组：[1, 2, 3, 4, 5] 前缀和：[0, 1, 3, 6, 10, 15] // prefix[i] 表示前 i 个元素的和 查询 sum[1,3] = prefix[4] - prefix[1] = 10 - 1 = 9 ✅ O(1) 查询 sum[0,4] = prefix[5] - prefix[0] = 15 - 0 = 15 ✅ O(1) 查询 sum[2,4] = prefix[5] - prefix[2] = 15 - 3 = 12 ✅ O(1) -
为什么有效（Why it Works）：
- 数学原理：sum[i,j] = prefix[j+1] - prefix[i]
- 用空间换时间（Space-Time Tradeoff）：多用 O(n) 空间存储前缀和，换取查询从 O(n) 降到 O(1)
- 预处理只需一次，之后任意次查询都是 O(1)
-
优势对比（Advantages Comparison）：
- 单次查询：暴力法 O(n) vs 前缀和 O(1)，提升 n 倍
- 多次查询：如果有 m 次查询，暴力法 O(m*n) vs 前缀和 O(n+m)，提升巨大
- 空间代价：前缀和需要额外 O(n) 空间，但在多次查询场景下完全值得
- 典型应用：二维前缀和（矩阵区域和查询）、差分数组（区间更新问题）
// ============ 双指针模板 ============
// 1. 对撞指针（有序数组）
public int[] twoPointerOpposite(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int currSum = nums[left] + nums[right];
if (currSum == target) {
return new int[]{left, right};
} else if (currSum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
// 2. 快慢指针（原地操作）
public int removeDuplicates(int[] nums) {
"""LC 26. 删除有序数组中的重复项"""
if (nums == null || nums.length == 0) {
return 0;
}
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
// ============ 滑动窗口模板 ============
public int slidingWindow(String s) {
"""通用滑动窗口框架"""
Map<Character, Integer> window = new HashMap<>();
int left = 0;
int result = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 2. 收缩窗口（条件不满足时）
while (windowNeedsShrink(window)) {
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
if (window.get(d) == 0) {
window.remove(d);
}
left++;
}
// 3. 更新结果
result = Math.max(result, right - left + 1);
}
return result;
}
// ============ 前缀和模板 ============
public int[] prefixSum(int[] nums) {
"""前缀和：快速求区间和"""
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// 区间 [i, j] 的和 = prefix[j+1] - prefix[i]
return prefix;
}
必刷题目（15题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 1 | 两数之和 | Easy | 哈希 | ⭐⭐⭐ |
| 15 | 三数之和 | Medium | 排序+对撞指针 | ⭐⭐⭐ |
| 26 | 删除有序数组重复项 | Easy | 快慢指针 | ⭐⭐ |
| 11 | 盛最多水的容器 | Medium | 对撞指针 | ⭐⭐⭐ |
| 3 | 无重复字符最长子串 | Medium | 滑动窗口 | ⭐⭐⭐ |
| 76 | 最小覆盖子串 | Hard | 滑动窗口 | ⭐⭐⭐ |
| 53 | 最大子数组和 | Medium | 前缀和/Kadane | ⭐⭐⭐ |
| 560 | 和为K的子数组 | Medium | 前缀和+哈希 | ⭐⭐⭐ |
| 239 | 滑动窗口最大值 | Hard | 单调队列 | ⭐⭐ |
| 42 | 接雨水 | Hard | 双指针/单调栈 | ⭐⭐⭐ |
| 88 | 合并两个有序数组 | Easy | 逆向双指针 | ⭐⭐ |
| 283 | 移动零 | Easy | 快慢指针 | ⭐⭐ |
| 438 | 找到字符串中所有字母异位词 | Medium | 滑动窗口 | ⭐⭐ |
| 54 | 螺旋矩阵 | Medium | 模拟/边界 | ⭐⭐ |
| 48 | 旋转图像 | Medium | 转置+翻转 | ⭐⭐ |
📅 Day 2：哈希表 + 链表¶
核心知识点¶
为什么需要这些数据结构？¶
哈希表的设计动机（Hash Table Design Motivation）： - 数组/链表的困境（Dilemma of Array/Linked List）：查找需要 O(n) 遍历，数据量大时无法接受 - 哈希表的突破（Hash Table Breakthrough）：通过哈希函数（Hash Function）直接计算存储位置，查找降到 O(1) - 为什么有效（Why it Works）：key → hash(code) → index，跳过了比较过程 - 代价（Trade-offs）：空间开销大（Space Overhead）、哈希冲突需要处理（Hash Collision）、无序存储（Unordered） - 对比数组（vs Array）：用空间换时间（Space-Time Tradeoff），查找快但不支持范围查询（Range Query） - 对比二叉搜索树（vs BST）：哈希表 O(1) 但无序，BST O(log n) 但支持范围查询和有序遍历（Ordered Traversal）
链表的设计动机（Linked List Design Motivation）： - 数组的困境（Array's Dilemma）：插入/删除需要移动后续所有元素 O(n) - 链表的突破（Linked List Breakthrough）：通过指针（Pointer）连接，插入/删除只需修改指针 O(1) - 为什么有效（Why it Works）：不需要连续内存，动态分配节点（Dynamic Memory Allocation） - 代价（Trade-offs）：不支持随机访问（No Random Access）、查找需要 O(n)、缓存不友好（Cache Miss 高） - 对比数组（vs Array）：链表快在修改，慢在访问；数组相反
快慢指针的巧妙之处（Fast-Slow Pointer Technique）： - 检测环的原理：如果链表有环，快指针一定会追上慢指针（类似操场跑步） - 找中点的原理：快指针走两步，慢指针走一步，快指针到尾时慢指针刚好在中点 - 为什么不用计数：不知道链表长度，无法提前知道中点位置
// ============ 哈希表常见用法 ============
import java.util.*;
// 1. 计数统计
public List<List<String>> groupAnagrams(String[] strs) {
"""LC 49. 字母异位词分组"""
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
// 2. 两数之和模式（一边遍历一边查）
public int[] twoSum(int[] nums, int target) {
"""LC 1. 两数之和"""
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
return new int[]{};
}
// ============ 链表核心操作 ============
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
// 1. 反转链表（必背）
public ListNode reverseList(ListNode head) {
"""LC 206. 反转链表"""
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
// 2. 检测环（快慢指针）
public boolean hasCycle(ListNode head) {
"""LC 141. 环形链表"""
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
// 3. 找环的入口
public ListNode detectCycle(ListNode head) {
"""LC 142. 环形链表 II"""
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 找入口：从head和相遇点同时出发
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
// 4. 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
"""LC 21. 合并两个有序链表"""
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
// 5. 找链表中间节点
public ListNode findMiddle(ListNode head) {
"""LC 876. 链表的中间结点"""
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
必刷题目（15题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 1 | 两数之和 | Easy | 哈希 | ⭐⭐⭐ |
| 49 | 字母异位词分组 | Medium | 哈希分组 | ⭐⭐⭐ |
| 128 | 最长连续序列 | Medium | 哈希集合 | ⭐⭐⭐ |
| 146 | LRU缓存 | Medium | 哈希+双向链表 | ⭐⭐⭐ |
| 206 | 反转链表 | Easy | 迭代/递归 | ⭐⭐⭐ |
| 21 | 合并两个有序链表 | Easy | 虚拟头节点 | ⭐⭐⭐ |
| 141 | 环形链表 | Easy | 快慢指针 | ⭐⭐⭐ |
| 142 | 环形链表 II | Medium | 快慢指针 | ⭐⭐ |
| 19 | 删除链表倒数第N个节点 | Medium | 快慢指针 | ⭐⭐⭐ |
| 160 | 相交链表 | Easy | 双指针 | ⭐⭐ |
| 23 | 合并K个升序链表 | Hard | 分治/堆 | ⭐⭐⭐ |
| 25 | K个一组翻转链表 | Hard | 分段反转 | ⭐⭐ |
| 138 | 随机链表的复制 | Medium | 哈希映射 | ⭐⭐ |
| 234 | 回文链表 | Easy | 快慢+反转 | ⭐⭐ |
| 2 | 两数相加 | Medium | 模拟进位 | ⭐⭐⭐ |
📅 Day 3：二叉树 + 递归¶
专题深读：树：二叉树、BST 与 B+ 树（遍历、递归、B-Tree 与 DDIA 对照）
核心知识点¶
为什么需要树结构？¶
线性结构的困境（Linear Structure's Dilemma）： - 数组/链表查找需要 O(n)，数据量大时效率低 - 无法自然表达层次关系（Hierarchical Relationship，如文件系统、组织架构）
二叉树的突破（Binary Tree Breakthrough）： - 查找优化（Search Optimization）：二叉搜索树（BST, Binary Search Tree）查找只需 O(log n)，每次排除一半 - 层次表达（Hierarchical Expression）：天然适合表达父子关系（Parent-Child Relationship）、层级结构 - 为什么有效（Why it Works）：将线性搜索转为对数级搜索（Logarithmic Search），类似二分查找的思想
递归的本质（Essence of Recursion）： - 为什么树用递归（Why Trees Use Recursion）：树是自相似结构（Self-similar Structure），子树也是树，天然适合递归 - 递归三要素（Three Elements of Recursion）： 1. 终止条件（Base Case）：节点为空时返回 2. 递归关系（Recursive Relation）：当前节点如何处理 3. 返回值（Return Value）：返回什么信息给父节点
遍历方式的选择（Traversal Strategy Selection）： - 前序（Preorder）：根→左→右，适合复制树、序列化（Serialization） - 中序（Inorder）：左→根→右，BST 中序遍历得到有序序列（In-order Sequence） - 后序（Postorder）：左→右→根，适合删除树、计算子树信息 - 层序（Level-order/BFS）：按层遍历，适合找最短路径、层级处理
递归框架的三种模式（Three Recursive Patterns）： 1. 自顶向下（Top-down）：从根节点传递参数到叶子节点，如计算深度 2. 自底向上（Bottom-up）：从叶子节点收集信息到根节点，如计算直径 3. 判断型（Validation）：判断是否满足条件，如验证 BST
// ============ 二叉树遍历模板 ============
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 1. 前序遍历（根-左-右）
public List<Integer> preorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.add(root.val);
result.addAll(preorder(root.left));
result.addAll(preorder(root.right));
return result;
}
// 2. 中序遍历（左-根-右）— BST有序
public List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.addAll(inorder(root.left));
result.add(root.val);
result.addAll(inorder(root.right));
return result;
}
// 3. 后序遍历（左-右-根）
public List<Integer> postorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.addAll(postorder(root.left));
result.addAll(postorder(root.right));
result.add(root.val);
return result;
}
// 4. 层序遍历（BFS）— 超高频
public List<List<Integer>> levelOrder(TreeNode root) {
"""LC 102. 二叉树的层序遍历"""
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
// ============ 二叉树递归思维框架 ============
// 框架1：自顶向下（传参）
public int maxDepth(TreeNode root) {
"""LC 104. 二叉树的最大深度"""
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// 框架2：自底向上（收集信息）
public int diameterOfBinaryTree(TreeNode root) {
"""LC 543. 二叉树的直径"""
int[] ans = new int[1];
depth(root, ans);
return ans[0];
}
private int depth(TreeNode node, int[] ans) {
if (node == null) return 0;
int left = depth(node.left, ans);
int right = depth(node.right, ans);
ans[0] = Math.max(ans[0], left + right);
return Math.max(left, right) + 1;
}
// 框架3：判断是否满足条件
public boolean isValidBST(TreeNode root) {
"""LC 98. 验证二叉搜索树"""
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, long lo, long hi) {
if (node == null) return true;
if (node.val <= lo || node.val >= hi) return false;
return isValidBST(node.left, lo, node.val) &&
isValidBST(node.right, node.val, hi);
}
必刷题目（15题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 102 | 二叉树的层序遍历 | Medium | BFS | ⭐⭐⭐ |
| 104 | 二叉树的最大深度 | Easy | 递归 | ⭐⭐⭐ |
| 226 | 翻转二叉树 | Easy | 递归 | ⭐⭐⭐ |
| 101 | 对称二叉树 | Easy | 递归 | ⭐⭐ |
| 543 | 二叉树的直径 | Easy | 后序遍历 | ⭐⭐⭐ |
| 236 | 二叉树最近公共祖先 | Medium | 递归 | ⭐⭐⭐ |
| 98 | 验证二叉搜索树 | Medium | 中序/边界 | ⭐⭐⭐ |
| 114 | 二叉树展开为链表 | Medium | 前序遍历 | ⭐⭐ |
| 105 | 前序+中序构造二叉树 | Medium | 递归+哈希 | ⭐⭐⭐ |
| 124 | 二叉树中的最大路径和 | Hard | 后序遍历 | ⭐⭐⭐ |
| 199 | 二叉树的右视图 | Medium | BFS/DFS | ⭐⭐ |
| 230 | BST第K小的元素 | Medium | 中序遍历 | ⭐⭐ |
| 297 | 二叉树的序列化与反序列化 | Hard | BFS/DFS | ⭐⭐ |
| 112 | 路径总和 | Easy | 递归 | ⭐⭐ |
| 437 | 路径总和 III | Medium | 前缀和+递归 | ⭐⭐ |
📅 Day 4：动态规划（重点突破）¶
核心知识点¶
为什么需要动态规划？¶
递归的困境（Recursion's Dilemma）： - 朴素递归会重复计算相同的子问题，导致指数级时间复杂度 O(2^n) - 例如斐波那契数列：fib(n) = fib(n-1) + fib(n-2)，fib(n-2) 被计算了两次
动态规划的突破（Dynamic Programming Breakthrough）： - 核心思想（Core Idea）：用空间换时间（Space-Time Tradeoff），存储已经计算过的子问题结果（记忆化 Memoization） - 为什么有效（Why it Works）：避免重复计算，将指数级降到多项式级 O(n²) 或 O(n) - 适用条件（Applicable Conditions）： 1. 重叠子问题（Overlapping Subproblems）：子问题会被重复计算 2. 最优子结构（Optimal Substructure）：问题的最优解包含子问题的最优解
DP vs 其他方法（DP vs Other Approaches）： - vs 贪心（vs Greedy）：贪心只看眼前最优，不回溯；DP 考虑所有可能，保证全局最优 - vs 回溯（vs Backtracking）：回溯枚举所有解，DP 只存储最优解；回溯适合找所有解，DP 适合找最优解 - vs 分治（vs Divide and Conquer）：分治的子问题不重叠（如归并排序），DP 的子问题重叠
DP 解题五步法（Five-Step DP Methodology）： 1. 定义状态（Define State）：dp[i] 表示什么？（最关键的一步） 2. 推导转移方程（Derive Transition Equation）：dp[i] 由哪些状态推出？（状态之间的关系） 3. 确定初始化（Determine Initialization）：base case 是什么？（边界条件 Boundary Condition） 4. 确定遍历顺序（Determine Traversal Order）：从小到大还是从大到小？（依赖关系决定） 5. 举例验证（Verify with Examples）：手动推导几个例子，验证方程正确性
常见 DP 模型（Common DP Models）： - 线性 DP（Linear DP）：状态在一维数组上转移，如爬楼梯、打家劫舍 - 二维 DP（2D DP）：状态在二维表格上转移，如 LCS、编辑距离 - 背包问题（Knapsack Problem）：在容量限制下最大化价值，如 0-1 背包、完全背包 - 区间 DP（Interval DP）：状态表示区间的最优解，如矩阵链乘、最长回文子串 - 树形 DP（Tree DP）：在树结构上转移，如树的最大独立集
// ============ DP 思考框架 ============
// 1. 定义状态（dp[i] 表示什么）
// 2. 推导转移方程（dp[i] 由哪些状态推出）
// 3. 确定初始化（base case）
// 4. 确定遍历顺序
// 5. 举例验证
// ============ 经典模型 ============
// 模型1：线性DP — 打家劫舍
public int rob(int[] nums) {
"""LC 198. 打家劫舍"""
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
// 模型2：子序列 — 最长递增子序列
public int lengthOfLIS(int[] nums) {
"""LC 300. 最长递增子序列"""
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1); // dp[i]: 以nums[i]结尾的LIS长度
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = 0;
for (int len : dp) max = Math.max(max, len);
return max;
}
// 模型3：二维DP — 最长公共子序列
public int longestCommonSubsequence(String text1, String text2) {
"""LC 1143. 最长公共子序列"""
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i-1) == text2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
// 模型4：背包问题
public boolean canPartition(int[] nums) {
"""LC 416. 分割等和子集（0-1背包）"""
int total = 0;
for (int num : nums) total += num;
if (total % 2 != 0) return false;
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) { // 逆序！
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
// 模型5：路径问题
public int minPathSum(int[][] grid) {
"""LC 64. 最小路径和"""
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
// 模型6：字符串DP — 编辑距离
public int minDistance(String word1, String word2) {
"""LC 72. 编辑距离"""
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
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.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j],
Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[m][n];
}
必刷题目（15题）¶
| # | 题目 | 难度 | 模型 | 优先级 |
|---|---|---|---|---|
| 70 | 爬楼梯 | Easy | 线性DP | ⭐⭐⭐ |
| 198 | 打家劫舍 | Medium | 线性DP | ⭐⭐⭐ |
| 322 | 零钱兑换 | Medium | 完全背包 | ⭐⭐⭐ |
| 300 | 最长递增子序列 | Medium | 子序列 | ⭐⭐⭐ |
| 1143 | 最长公共子序列 | Medium | 二维DP | ⭐⭐⭐ |
| 72 | 编辑距离 | Medium | 字符串DP | ⭐⭐⭐ |
| 64 | 最小路径和 | Medium | 路径DP | ⭐⭐⭐ |
| 62 | 不同路径 | Medium | 路径DP | ⭐⭐ |
| 416 | 分割等和子集 | Medium | 0-1背包 | ⭐⭐⭐ |
| 152 | 乘积最大子数组 | Medium | 线性DP | ⭐⭐ |
| 139 | 单词拆分 | Medium | 线性DP | ⭐⭐⭐ |
| 5 | 最长回文子串 | Medium | 中心扩展/DP | ⭐⭐⭐ |
| 279 | 完全平方数 | Medium | 完全背包 | ⭐⭐ |
| 32 | 最长有效括号 | Hard | 栈/DP | ⭐⭐ |
| 10 | 正则表达式匹配 | Hard | 二维DP | ⭐⭐ |
📅 Day 5：二分查找 + 排序 + 栈/队列¶
核心知识点¶
为什么需要这些算法和数据结构？¶
二分查找的设计动机（Binary Search Design Motivation）： - 线性查找的困境（Linear Search's Dilemma）：在有序数组中查找需要 O(n)，效率低 - 二分的突破（Binary Search Breakthrough）：每次排除一半，O(log n) 时间复杂度 - 为什么有效（Why it Works）：利用有序性，通过比较中间元素决定搜索方向 - 适用前提（Prerequisites）：必须有序或具有单调性（Monotonicity） - 对比哈希表（vs Hash Table）：二分 O(log n) 但不需要额外空间，哈希表 O(1) 但需要 O(n) 空间
排序算法的选择（Sorting Algorithm Selection）： - 快速排序（Quick Sort）：平均 O(n log n)，原地排序（In-place），但不稳定（Unstable），最坏 O(n²) - 归并排序（Merge Sort）：稳定 O(n log n)，但需要 O(n) 额外空间 - 堆排序（Heap Sort）：O(n log n)，原地排序，适合 TopK 问题 - 为什么不用冒泡/选择（Why Not Bubble/Selection Sort）：O(n²) 只适合小数据量
栈的设计动机（Stack Design Motivation）： - LIFO 特性（LIFO Property）：后进先出（Last In First Out），匹配"撤销/回退"场景 - 为什么括号匹配用栈（Why Stack for Parentheses Matching）：最近打开的括号应该最先关闭 - 单调栈的巧妙（Monotonic Stack）：维护一个单调递增/递减的栈，快速找到左边/右边第一个更大/更小的元素
队列的设计动机（Queue Design Motivation）： - FIFO 特性（FIFO Property）：先进先出（First In First Out），匹配"排队"场景 - 为什么 BFS 用队列（Why Queue for BFS）：需要按层遍历，先访问的节点先扩展
// ============ 二分查找模板 ============
// 模板1：标准二分（找target）
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 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;
}
// 模板2：找左边界（第一个 >= target 的位置）
public int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// 模板3：搜索旋转排序数组
public int searchRotated(int[] nums, int target) {
"""LC 33. 搜索旋转排序数组"""
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 左半段有序
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 右半段有序
else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// ============ 排序核心 ============
// 快速排序（手写）
public void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int pivot = nums[left + (right - left) / 2];
int i = left, j = right;
while (i <= j) {
while (nums[i] < pivot) i++;
while (nums[j] > pivot) j--;
if (i <= j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
quickSort(nums, left, j);
quickSort(nums, i, right);
}
// TopK问题 — 堆
public int findKthLargest(int[] nums, int k) {
"""LC 215. 数组中的第K个最大元素"""
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
// ============ 栈的应用 ============
// 单调栈模板
public int[] dailyTemperatures(int[] temperatures) {
"""LC 739. 每日温度"""
int n = temperatures.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>(); // 存索引，栈底到栈顶递减
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
result[prev] = i - prev;
}
stack.push(i);
}
return result;
}
// 有效括号
public boolean isValid(String s) {
"""LC 20. 有效的括号"""
Stack<Character> stack = new Stack<>();
Map<Character, Character> mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put(']', '[');
mapping.put('}', '{');
for (char c : s.toCharArray()) {
if (mapping.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != mapping.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
必刷题目（15题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 33 | 搜索旋转排序数组 | Medium | 二分 | ⭐⭐⭐ |
| 34 | 排序数组中查找元素 | Medium | 二分 | ⭐⭐⭐ |
| 153 | 旋转数组最小值 | Medium | 二分 | ⭐⭐ |
| 4 | 两个正序数组中位数 | Hard | 二分 | ⭐⭐ |
| 215 | 第K个最大元素 | Medium | 堆/快选 | ⭐⭐⭐ |
| 347 | 前K个高频元素 | Medium | 堆+哈希 | ⭐⭐⭐ |
| 912 | 排序数组 | Medium | 快排/归并 | ⭐⭐⭐ |
| 56 | 合并区间 | Medium | 排序 | ⭐⭐⭐ |
| 20 | 有效的括号 | Easy | 栈 | ⭐⭐⭐ |
| 155 | 最小栈 | Medium | 辅助栈 | ⭐⭐⭐ |
| 739 | 每日温度 | Medium | 单调栈 | ⭐⭐⭐ |
| 84 | 柱状图最大矩形 | Hard | 单调栈 | ⭐⭐ |
| 394 | 字符串解码 | Medium | 栈 | ⭐⭐⭐ |
| 232 | 用栈实现队列 | Easy | 双栈 | ⭐⭐ |
| 150 | 逆波兰表达式求值 | Medium | 栈 | ⭐⭐ |
📅 Day 6：图 + BFS/DFS + 回溯 + 贪心¶
核心知识点¶
为什么需要图算法和这些搜索策略？¶
图的设计动机（Graph Design Motivation）： - 树和数组的困境（Dilemma of Trees and Arrays）：只能表达层级或线性关系，无法表达多对多关系（Many-to-Many Relationship） - 图的突破（Graph Breakthrough）：节点之间可以任意连接，适合社交网络（Social Network）、路径规划（Path Planning）、依赖关系（Dependency） - 为什么需要图算法（Why Graph Algorithms）：现实世界的问题大多是图问题（路由、推荐、知识图谱）
BFS vs DFS 的选择（BFS vs DFS Selection）： - BFS（广度优先搜索，Breadth-First Search）： - 为什么有效（Why it Works）：按层遍历（Level-by-Level Traversal），先找到的路径一定最短 - 适用场景（Use Cases）：最短路径（Shortest Path）、层级遍历、连通分量（Connected Component） - 代价（Trade-offs）：需要队列，空间复杂度 O(n)
- DFS（深度优先搜索，Depth-First Search）：
- 为什么有效（Why it Works）：递归深入，适合探索所有可能
- 适用场景（Use Cases）：连通性检测（Connectivity Detection）、拓扑排序（Topological Sort）、回溯搜索
- 代价（Trade-offs）：递归深度大时可能栈溢出（Stack Overflow），空间复杂度 O(h) h 为树高
回溯的设计动机（Backtracking Design Motivation）： - 暴力法的困境（Brute-force Dilemma）：枚举所有解是 O(n!) 或 O(2^n)，无法接受 - 回溯的突破（Backtracking Breakthrough）：系统地枚举 + 剪枝（Pruning），提前排除不可能的分支 - 为什么有效（Why it Works）：决策树的 DFS，走不通就撤销选择（Backtrack） - 三要素（Three Elements）： 1. 路径（Path）：已经做的选择 2. 选择列表（Choices）：当前可以做的选择 3. 结束条件（Base Case）：路径达到要求
贪心的设计动机（Greedy Design Motivation）： - DP 的困境（DP's Dilemma）：需要考虑所有可能，时间复杂度高 - 贪心的突破（Greedy Breakthrough）：每一步选局部最优（Local Optimum），如果问题具有贪心选择性质，就能得到全局最优（Global Optimum） - 为什么有效（Why it Works）：问题具有"贪心选择性质"（Greedy Choice Property）和"最优子结构" - vs DP（vs Dynamic Programming）：贪心不回溯，效率更高 O(n)，但适用范围更窄；需要证明贪心策略的正确性
// ============ 图遍历 ============
import java.util.*;
// BFS 模板（最短路径/层级遍历）
public void bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
// DFS 模板（连通性/路径搜索）
public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
visited.add(node);
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
// 岛屿问题（网格DFS经典）
public int numIslands(char[][] grid) {
"""LC 200. 岛屿数量"""
if (grid == null || grid.length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
return;
}
grid[i][j] = '0'; // 标记已访问
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
// ============ 回溯模板 ============
// 全排列
public List<List<Integer>> permute(int[] nums) {
"""LC 46. 全排列"""
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), used, result);
return result;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, path, used, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
// 子集
public List<List<Integer>> subsets(int[] nums) {
"""LC 78. 子集"""
List<List<Integer>> result = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrackSubsets(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrackSubsets(nums, i + 1, path, result);
path.remove(path.size() - 1);
}
}
// ============ 贪心模板 ============
public int jump(int[] nums) {
"""LC 45. 跳跃游戏 II"""
int n = nums.length;
int jumps = 0;
int curEnd = 0;
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = farthest;
}
}
return jumps;
}
必刷题目（15题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 200 | 岛屿数量 | Medium | DFS/BFS | ⭐⭐⭐ |
| 994 | 腐烂的橘子 | Medium | 多源BFS | ⭐⭐⭐ |
| 207 | 课程表 | Medium | 拓扑排序 | ⭐⭐⭐ |
| 46 | 全排列 | Medium | 回溯 | ⭐⭐⭐ |
| 78 | 子集 | Medium | 回溯 | ⭐⭐⭐ |
| 39 | 组合总和 | Medium | 回溯 | ⭐⭐⭐ |
| 22 | 括号生成 | Medium | 回溯 | ⭐⭐⭐ |
| 79 | 单词搜索 | Medium | DFS回溯 | ⭐⭐ |
| 51 | N皇后 | Hard | 回溯 | ⭐⭐ |
| 55 | 跳跃游戏 | Medium | 贪心 | ⭐⭐⭐ |
| 45 | 跳跃游戏 II | Medium | 贪心 | ⭐⭐ |
| 121 | 买卖股票最佳时机 | Easy | 贪心/DP | ⭐⭐⭐ |
| 763 | 划分字母区间 | Medium | 贪心 | ⭐⭐ |
| 31 | 下一个排列 | Medium | 贪心模拟 | ⭐⭐⭐ |
| 169 | 多数元素 | Easy | 投票法 | ⭐⭐ |
📅 Day 7：综合模拟 + 高频面试手撕代码¶
机试模拟策略¶
为什么这些题目是高频考点？¶
LRU 缓存（LRU Cache - Least Recently Used）： - 为什么常考（Why Frequently Asked）：综合考察哈希表 + 双向链表（Doubly Linked List），体现"空间换时间"的设计思想 - 设计动机（Design Motivation）：缓存需要 O(1) 查找（哈希表）和 O(1) 淘汰最近最少使用（双向链表） - LinkedHashMap 的巧妙（LinkedHashMap's Elegance）：Java 标准库已经封装好，但面试官希望你理解底层实现（Underlying Implementation）
用两个栈实现队列（Implement Queue using Stacks）： - 为什么常考（Why Frequently Asked）：考察对栈和队列特性的理解，以及数据结构的组合能力（Composition） - 设计动机（Design Motivation）：一个栈负责入队（Push Stack），一个栈负责出队（Pop Stack），出队栈空时才从入队栈转移 - 均摊复杂度（Amortized Complexity）：虽然 peek 可能是 O(n)，但均摊下来是 O(1)
手写排序算法（Implement Sorting Algorithm）： - 为什么常考（Why Frequently Asked）：考察对算法本质的理解，而不仅仅是调用 API - 快排 vs 归并（Quick Sort vs Merge Sort）：快排原地但不稳定，归并稳定但需要额外空间 - 面试重点（Interview Focus）：能否说清楚时间复杂度（Time Complexity）、空间复杂度（Space Complexity）、稳定性（Stability）、适用场景（Use Cases）
// ============ 机试应试技巧 ============
"""
1. 时间分配（假设3题/2小时）：
- 第1题（Easy/Medium）：20分钟
- 第2题（Medium）：40分钟
- 第3题（Medium/Hard）：60分钟
2. 做题流程：
a. 读题 → 找到关键约束（数据范围决定时间复杂度）
b. 想解法 → 先暴力，再优化
c. 写代码 → 先写框架，再填细节
d. 测试 → 先过样例，再想边界
3. 数据范围与复杂度对照表：
n ≤ 10 → O(n!) 回溯
n ≤ 20 → O(2^n) 状压DP/回溯
n ≤ 100 → O(n^3) 三重循环
n ≤ 1000 → O(n^2) 双重循环/DP
n ≤ 10^5 → O(nlogn) 排序/二分/堆
n ≤ 10^6 → O(n) 双指针/哈希/前缀和
n ≤ 10^9 → O(logn) 二分/数学
"""
// ============ 面试手撕高频题 Top 5 ============
// 1. LRU缓存（面试最爱考）
class LRUCache {
"""LC 146. LRU缓存"""
private LinkedHashMap<Integer, Integer> cache;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
// 2. 用两个栈实现队列
class MyQueue {
"""LC 232"""
private Stack<Integer> inStack;
private Stack<Integer> outStack;
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
peek();
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
}
// 3. 手写快排
public void quickSortImpl(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left + (right - left) / 2];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
quickSortImpl(arr, left, j);
quickSortImpl(arr, i, right);
}
// 4. 手写归并排序
public int[] mergeSort(int[] arr) {
if (arr.length <= 1) return arr;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
private int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) result[k++] = left[i++];
while (j < right.length) result[k++] = right[j++];
return result;
}
// 5. 手写二叉搜索树
class BST {
private TreeNode root;
public void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) return new TreeNode(val);
if (val < node.val) {
node.left = insert(node.left, val);
} else {
node.right = insert(node.right, val);
}
return node;
}
public boolean search(int val) {
return search(root, val);
}
private boolean search(TreeNode node, int val) {
if (node == null) return false;
if (val == node.val) return true;
return val < node.val ? search(node.left, val) : search(node.right, val);
}
}
今日模拟任务¶
上午（3小时）：限时模拟
□ 在 LeetCode 上随机选3题（1 Easy + 1 Medium + 1 Hard）
□ 计时2小时完成
□ 复盘总结
下午（3小时）：手撕代码练习
□ 不看任何参考，手写以上10个高频题
□ 用纸笔写一遍（模拟白板面试）
□ 对照检查错误
晚上（2小时）：错题回顾
□ 整理本周所有做错的题
□ 重做错题（不看答案）
□ 总结易错点
🧠 面试中的算法问答技巧¶
沟通框架（UMPIRE法）¶
U - Understand：确认题意，问清楚输入输出和边界
M - Match：匹配到已知的算法模式
P - Plan：描述你的解题思路
I - Implement：编码实现
R - Review：检查代码正确性
E - Evaluate：分析时间/空间复杂度
常见追问及回答¶
Q: "这个解法的时间复杂度是多少？"
→ 提前算好，回答要快速自信
Q: "能优化吗？"
→ 空间换时间（哈希表、缓存）
→ 更好的算法（暴力→双指针→二分）
Q: "如果数据量很大呢？"
→ 外部排序、分治、流式处理、MapReduce
Q: "有什么边界情况？"
→ 空输入、单元素、全相同、溢出、负数
📊 LeetCode 高频100题清单（按出现频率排序）¶
Tier 1 — 必须会（面试出现率 > 50%）¶
1, 3, 15, 20, 21, 53, 56, 70, 76,
102, 121, 141, 146, 200, 206, 215,
236, 300, 322, 394, 560
Tier 2 — 应该会（面试出现率 30-50%）¶
2, 5, 11, 19, 22, 33, 34, 39, 42,
46, 48, 49, 55, 62, 64, 72, 78, 79,
84, 88, 98, 104, 105, 124, 128, 139,
142, 152, 155, 160, 169, 198, 226,
234, 238, 239, 283, 297, 347, 416,
437, 438, 543, 739, 763, 912, 994
Tier 3 — 锦上添花（面试出现率 15-30%）¶
4, 10, 23, 25, 31, 32, 41, 45, 51,
54, 75, 114, 148, 150, 153, 199, 207,
208, 230, 232, 240, 279, 287
⏰ 每日 Checklist¶
□ 复习当天专题的知识点和模板（1小时）
□ 完成当天必刷题目中的 ⭐⭐⭐ 题（至少8题）
□ 限时做题：Medium 控制在 20 分钟内
□ 总结当天的解题模式和易错点
□ 睡前回顾：闭眼过一遍今天的解题思路
💡 最后提醒¶
- 先刷 Tier 1：时间紧迫，先保证高频题滚瓜烂熟
- 背模板：双指针、滑动窗口、BFS/DFS、回溯、DP转移 — 这些模板必须肌肉记忆
- 手写代码：面试时不能查IDE，在纸上写一遍比在电脑上刷10遍更有效
- 注意复杂度：每道题做完立即口述时间/空间复杂度
- 模拟面试环境：最后2天用限时模式，3题/90分钟
7天足够让你恢复算法手感，拿下面试！冲！