算法与数据结构总览

一、知识体系总览

1.1 学习路径

第1阶段 基础数据结构     → 数组、链表、栈、队列
第2阶段 树与图           → 二叉树、遍历、图算法
第3阶段 基础算法         → 排序、二分、递归
第4阶段 高级算法        → 动态规划、回溯、分治
第5阶段 面试实战         → 手撕代码、系统设计

1.2 核心知识点思维导图

                        算法与数据结构
                              │
        ┌─────────┬───────────┼───────────┬─────────┐
        ▼         ▼           ▼           ▼         ▼
     数组链表    二叉树      排序算法     动态规划    手撕代码
        │         │           │           │         │
   • 双指针    • 遍历       • 快速排序   • 状态定义   • LRU缓存
   • 快慢指针  • 重建       • 归并排序   • 转移方程   • 线程池
   • 环形检测  • 最近祖先   • 堆排序     • 背包问题   • 限流器
   • 区间合并  • BST        • Top K      • 编辑距离   • ID生成

1.3 面试重点总结

题型	考察频率	难度	核心能力
双指针/滑动窗口	★★★★★	中	边界处理
二叉树遍历	★★★★★	中	递归思维
动态规划	★★★★★	高	抽象建模
回溯算法	★★★★☆	高	状态枚举
排序与二分	★★★★☆	中	有序思维
图论算法	★★★☆☆	高	拓扑思维

二、常见时间复杂度

复杂度	名称	典型场景
O(1)	常数时间	数组按索引访问、哈希表查找
O(log n)	对数时间	二分查找、平衡二叉搜索树
O(n)	线性时间	遍历数组/链表、线性搜索
O(n log n)	线性对数时间	快速排序、归并排序、堆排序
O(n²)	平方时间	冒泡排序、双重循环、矩阵乘法
O(2ⁿ)	指数时间	递归穷举、子集枚举
O(n!)	阶乘时间	全排列、TSP问题

三、面试考察全景

📊 数组与链表

数组遍历；链表反转；双指针；快慢指针；环形链表检测。

🌲 二叉树

遍历方式；重建二叉树；最近公共祖先；二叉搜索树；层序遍历。

🔢 排序算法

快速排序；归并排序；堆排序；Top K 问题；二分查找。

🧮 动态规划

斐波那契；最长子序列；背包问题；编辑距离；打家劫舍。

💻 手撕代码

LRU 缓存；阻塞队列；生产者消费者；线程池；分布式 ID。

四、备战建议

第1天  数组与链表     → 双指针、快慢指针
第2天  二叉树         → 遍历、重建、递归
第3天  排序算法       → 手写快排、归并
第4天  动态规划       → 状态定义、转移方程
第5天  手撕代码       → LRU、线程池、限流

五、核心技巧总结

技巧	适用场景	关键点
双指针	有序数组、链表	边界条件、指针移动
快慢指针	环形检测、中点查找	速度差异、相遇条件
滑动窗口	子串问题、连续子数组	窗口大小、收缩时机
二分查找	有序数据搜索	边界处理、循环条件
递归	树遍历、分治	终止条件、返回值
动态规划	最优子结构	状态定义、转移方程