P8 · 计算机基础补强（W31-40）

目标：补齐算法 / 操作系统 / 计算机网络，能应付面试基本能力题 验收：力扣中等题 30 分钟内能解出思路

一、本阶段核心知识点

A. 算法与数据结构（优先级最高）

1. 时间 / 空间复杂度

• O(1) / O(log n) / O(n) / O(n log n) / O(n²) / O(2ⁿ)
• 最好 / 最坏 / 平均 / 均摊复杂度

2. 必刷数据结构

• 数组（前缀和、双指针、滑动窗口）
• 链表（反转、环、合并、LRU）
• 栈 / 队列（单调栈、优先级队列）
• 哈希表（HashMap 原理、布隆过滤器、一致性 hash）
• 树（二叉树、二叉搜索树、平衡树 AVL/红黑树、堆、字典树、并查集）
• 图（表示：BFS / DFS / 拓扑排序 / 最短路：Dijkstra / Floyd）
• 位图、跳表

3. 必刷算法

• 排序：快排、归并、堆排、希尔、计数 / 桶 / 基数
• 搜索：二分（变体很多）、BFS / DFS、回溯、剪枝
• 动态规划：背包、区间、子序列、状态机 DP、状压 DP
• 贪心：区间调度、跳跃游戏
• 分治：归并、最近点对、大数乘法

4. LeetCode 刷题节奏（200 题）

Week 31-32：链表 / 栈 / 队列 / 哈希（Easy + Medium 各 5）= 40 题
Week 33-34：树 / 二叉搜索树 / BFS / DFS = 40 题
Week 35-36：二分 / 排序 / 双指针 / 滑动窗口 = 40 题
Week 37-38：动态规划 / 贪心 / 回溯 = 50 题
Week 39-40：图（中等 + Hard 10 题）+ 系统设计 = 30 题

• 每题计时：Easy ≤ 10min / Medium ≤ 25min / Hard ≤ 40min
• 用笔记模板沉淀（题目 + 思路 + 复杂度 + 反思）
• LeetCode Hot 100 + 剑指 Offer + 字节 Top 100

B. 操作系统

1. 进程与线程

• 进程 vs 线程（资源、切换、并发）
• 进程状态：新建 / 就绪 / 运行 / 阻塞 / 终止
• 线程模型：N:1 / 1:1 / M:N
• Java 线程与 OS 线程（1:1 映射）

2. 进程间通信（IPC）

• 管道 / 命名管道
• 信号量 / 共享内存 / 消息队列
• Socket / Unix Domain Socket

3. 线程同步

• 互斥锁 / 自旋锁 / 读写锁
• 生产者消费者模型
• 哲学家就餐问题

4. 死锁

• 4 个必要条件：互斥 / 占有并等待 / 不可剥夺 / 循环等待
• 避免：破坏 4 条件之一
• 银行家算法
• 排查：jstack 查找死锁线程

5. 内存管理

• 虚拟内存、页表、TLB
• 页面置换算法：LRU / LFU / FIFO / Clock
• 段页式存储
• 内存映射（mmap）
• 抖动（Thrashing）

6. 文件系统

• 文件结构：inode / FAT / NTFS
• 文件描述符、VFS
• Page Cache、Buffer Cache

7. IO 多路复用（与 P1 内容呼应）

• select / poll / epoll（LT / ET）
• Reactor vs Proactor

C. 计算机网络

1. 网络分层模型

• OSI 7 层：物理 → 数据链路 → 网络 → 传输 → 会话 → 表示 → 应用
• TCP/IP 4 层：链路 → 网络 → 传输 → 应用
• 各层协议对照

2. 传输层 TCP（必背）

• 三次握手、四次挥手（面试必考）
• 状态机：LISTEN / SYN_SENT / SYN_RCVD / ESTABLISHED / FIN_WAIT_1/2 / TIME_WAIT / CLOSE_WAIT / LAST_ACK
• 可靠性：ACK、超时重传、快速重传、SACK
• 流量控制：滑动窗口
• 拥塞控制：慢启动 / 拥塞避免 / 快重传 / 快恢复
• 粘包 / 半包、TCP_NODELAY

3. 传输层 UDP

• 特点：无连接、不可靠、快速
• 应用场景：DNS、视频直播、游戏

4. 应用层

• HTTP 1.0 / 1.1 / 2.0 / 3.0（QUIC）
• HTTP 报文、首部字段、状态码
• HTTPS：TLS 1.2 / 1.3 握手、对称 / 非对称加密、证书
• DNS 解析流程：递归 / 迭代
• Cookie / Session / Token / JWT

5. 网络安全

• XSS / CSRF / SQL 注入 / SSRF / 同源策略 / CORS
• HTTPS 防中间人、防劫持

D. 设计模式（Java 后端面试高频）

1. 创建型

• 单例（7 种写法）
• 工厂、抽象工厂
• 建造者、原型

2. 结构型

• 代理（静态 / JDK / CGLIB）
• 装饰器
• 适配器、桥接
• 外观、组合、享元

3. 行为型

• 模板方法
• 策略 + 责任链
• 观察者 + 发布订阅
• 状态、命令、备忘录

4. Spring 源码中的模式

• IoC：工厂 + 单例
• AOP：代理 + 责任链
• 事务：模板方法 + 策略
• ApplicationEvent：观察者

二、任务清单（可勾选打卡）

Week 31-32 · 算法入门

• LeetCode 链表 20 题（含 LRU、链表反转、合并）
• LeetCode 哈希表 20 题（含三数之和、四数之和、有效字母异位词）
• 用「专题笔记模板」沉淀每题（题目 + 思路 + 复杂度 + 反思）

Week 33-34 · 算法树与搜索

• LeetCode 二叉树 40 题（BFS / DFS / 路径和）
• 手写 AVL 红黑树插入删除（用伪代码）
• LeetCode 二分 20 题（含搜索旋转数组）

Week 35-36 · 算法进阶

• LeetCode 双指针 + 滑动窗口 30 题
• LeetCode 排序 10 题（含快排、归并实现）
• 完成《剑指 Offer》至少 50 题

Week 37-38 · 动态规划

• LeetCode DP 60 题（背包 / 子序列 / 区间 / 状态机）
• 总结 DP 5 类题型模板

Week 39-40 · 系统设计与图

• LeetCode 图 20 题（拓扑排序、最短路、并查集）
• 完成 5 道系统设计题：
• 短 URL 生成器
• 秒杀系统
• Feed 流（推 / 拉模式）
• 分布式限流
• 分布式锁

Week 36-40 · 操作系统与网络（并行刷）

• 阅读《操作系统概念》第 4-9 章
• 阅读《计算机网络：自顶向下方法》第 1-3 章
• 整理 OS 笔记：进程、线程、死锁、内存
• 整理网络笔记：TCP 三握四挥、HTTP/HTTPS、DNS

长期 · 设计模式

• 总结设计模式 23 种，配 Java 示例
• 在 P1-P5 的 demo 中找 5 个真实使用案例

三、阶段验收标准

✅ 能独立完成： - 力扣 Medium 题 30 分钟内能做出来 - 完整画出 TCP 三握四挥状态机 - 完整画出进程状态转换图 - 设计模式说出 10+ 种，并能在 Spring 源码中找到应用 - 系统设计题能在 30 分钟内给出可落地方案

四、产出物

• notes/algorithm/ 分专题刷题笔记 200 题
• notes/os.md 操作系统笔记
• notes/network.md 计算机网络笔记
• notes/design-patterns.md 设计模式笔记
• notes/system-design.md 系统设计 5 题

五、面试高频问题预告

1. TCP 怎么保证可靠传输？粘包怎么解决？
2. 输入 URL 到页面显示全过程（必问）？
3. 进程 / 线程 / 协程区别？什么时候用？
4. 死锁怎么排查？怎么避免？
5. HTTPS 握手过程？怎么防中间人？
6. LRUCache 怎么实现？（必写代码题）
7. 限流算法有哪些？怎么选？