四、数据结构与算法

范围：数组链表、树结构、图结构、排序算法、算法思想、复杂度分析 知识点数量：285项 返回总目录

---

4.1 基础数据结构

4.1.1 数组与链表

• 415. 数组特性 - 掌握随机访问O(1)、固定大小、内存连续性
• 416. 动态数组实现 - 掌握扩容机制（1.5倍/2倍），理解均摊O(1)
• 417. 单向链表 - 掌握节点结构和遍历，理解哨兵节点
• 418. 双向链表 - 掌握前后指针和反向遍历，理解LinkedList实现
• 419. 循环链表 - 掌握约瑟夫问题应用，理解环检测
• 420. 链表操作（增删改查） - 掌握头插法、尾插法、中间插入
• 421. 快慢指针技巧 - 掌握环检测、中间节点、倒数第k个节点
• 422. 数组 vs 链表 - 理解适用场景对比，掌握选择策略
• 423. 二维数组 - 掌握矩阵操作、对角线遍历
• 424. 稀疏数组 - 掌握压缩存储，理解三元组表示
• 425. 链表反转 - 掌握迭代和递归两种实现
• 426. 链表排序 - 掌握归并排序链表实现
• 427. 链表合并 - 掌握合并K个有序链表

4.1.2 栈与队列

• 428. 栈实现与应用 - 掌握括号匹配、表达式求值、函数调用栈
• 429. 队列实现与应用 - 掌握BFS、任务调度、缓冲区
• 430. 循环队列 - 掌握数组实现和空满判断（浪费一个空间/size计数）
• 431. 双端队列（Deque） - 掌握ArrayDeque使用，理解滑动窗口
• 432. 优先级队列 - 掌握堆实现，理解Top K问题
• 433. 单调栈 - 掌握下一个更大元素问题，理解递减/递增栈
• 434. 单调队列 - 掌握滑动窗口最值，理解队首过期元素移除
• 435. 栈实现队列 - 掌握双栈模拟队列
• 436. 队列实现栈 - 掌握单队列模拟栈
• 437. 最小栈 - 掌握O(1)获取最小值
• 438. 有效括号序列 - 掌握多种括号匹配验证

4.1.3 哈希表

• 439. 哈希函数设计 - 掌握除留余数、MurmurHash、一致性哈希
• 440. 冲突解决（链地址法） - 掌握拉链法实现，理解链表转红黑树
• 441. 冲突解决（开放地址法） - 掌握线性/二次/双重探测
• 442. 负载因子与扩容 - 理解扩容时机（0.75），掌握rehash过程
• 443. 哈希表应用 - 掌握两数之和、重复检测、频率统计
• 444. LRU缓存实现 - 掌握HashMap+双向链表，理解O(1)操作
• 445. LFU缓存实现 - 掌握频率排序，理解双HashMap+双向链表
• 446. Bloom Filter - 掌握布隆过滤器原理，理解误判率
• 447. 一致性哈希 - 掌握虚拟节点，理解分布式缓存路由
• 448. 哈希碰撞攻击 - 理解DOS攻击，掌握防御策略

4.2 树结构

4.2.1 二叉树

• 449. 二叉树遍历（前中后序） - 掌握递归和迭代实现（栈）
• 450. 层序遍历 - 掌握BFS应用，理解层级输出
• 451. Morris遍历 - 掌握O(1)空间遍历，理解线索化
• 452. 二叉搜索树 - 掌握插入、删除、查找，理解中序有序
• 453. 平衡二叉树（AVL） - 掌握四种旋转（LL/RR/LR/RL）
• 454. 最近公共祖先 - 掌握树遍历应用，理解递归和迭代
• 455. 树的深度/直径 - 掌握递归计算，理解最长路径
• 456. 序列化与反序列化 - 掌握前序+中序重建，理解层序序列化
• 457. 二叉树镜像 - 掌握递归翻转
• 458. 完全二叉树判定 - 掌握层序遍历+空节点检测
• 459. 二叉树最大路径和 - 掌握后序遍历+全局变量
• 460. 验证BST - 掌握中序遍历验证、范围验证

4.2.2 红黑树

• 461. 红黑树性质 - 掌握5条性质和高度证明（2log(n+1)）
• 462. 红黑树插入 - 掌握case分类（叔节点颜色）和旋转
• 463. 红黑树删除 - 掌握删除节点和平衡调整
• 464. Java TreeMap实现 - 理解TreeMap底层原理，掌握导航方法
• 465. HashMap树化 - 掌握链表转红黑树阈值（8），退化阈值（6）
• 466. 左倾红黑树（LLRB） - 理解简化实现，掌握3种操作
• 467. 红黑树vs AVL - 理解权衡（插入性能vs查询性能）

4.2.3 高级树结构

• 468. B树与B+树 - 掌握多路搜索树和数据库索引，理解磁盘IO优化
• 469. Trie树（字典树） - 掌握前缀匹配，理解自动补全
• 470. 线段树 - 掌握区间查询和更新，理解lazy标记
• 471. 树状数组（BIT） - 掌握前缀和优化，理解lowbit运算
• 472. 并查集 - 掌握路径压缩和按秩合并，理解连通分量
• 473. 堆（二叉堆） - 掌握建堆O(n)和堆排序，理解优先级队列
• 474. 跳表 - 掌握Redis SortedSet底层，理解概率平衡
• 475. 字典树应用 - 掌握敏感词过滤、IP路由最长前缀匹配
• 476. B+树分裂合并 - 掌握节点分裂、兄弟借位
• 477. 线段树应用 - 掌握区间最值查询、区间求和
• 478. 堆应用 - 掌握Top K、中位数、任务调度
• 479. 哈夫曼树 - 掌握贪心构造，理解压缩编码

4.3 图结构

4.3.1 图表示与遍历

• 480. 邻接矩阵 - 掌握稠密图表示，理解空间复杂度O(V²)
• 481. 邻接表 - 掌握稀疏图表示，理解Vector/链表实现
• 482. 十字链表 - 掌握有向图存储，理解边表结构
• 483. DFS深度优先 - 掌握递归和栈实现，理解回溯
• 484. BFS广度优先 - 掌握队列实现，理解最短路径（无权图）
• 485. 拓扑排序 - 掌握Kahn算法（入度）和DFS（逆序）
• 486. 连通分量 - 掌握无向图连通性，理解并查集应用
• 487. 二分图判定 - 掌握染色法（BFS/DFS）
• 488. 图的环检测 - 掌握有向图/无向图环检测
• 489. 强连通分量 - 掌握Tarjan算法和Kosaraju算法
• 490. 欧拉回路 - 掌握一笔画问题，理解Hierholzer算法

4.3.2 最短路径

• 491. Dijkstra算法 - 掌握单源最短路径，理解优先队列优化O((V+E)logV)
• 492. Bellman-Ford算法 - 掌握负权边处理，理解负环检测
• 493. Floyd算法 - 掌握多源最短路径，理解动态规划O(V³)
• 494. SPFA算法 - 掌握队列优化Bellman-Ford，理解最坏情况
• 495. A*算法 - 掌握启发式搜索，理解h(n)估价函数
• 496. 差分约束系统 - 掌握最短路应用，理解不等式转换
• 497. Johnson算法 - 掌握全源最短路，理解重标号技巧
• 498. 最短路径变种 - 掌握第K短路、双向BFS

4.3.3 最小生成树与网络流

• 499. Prim算法 - 掌握贪心MST，理解优先队列优化
• 500. Kruskal算法 - 掌握并查集MST，理解边排序
• 501. 最大流（Ford-Fulkerson） - 掌握增广路，理解残留网络
• 502. Dinic算法 - 掌握分层图优化，理解BFS+DFS
• 503. 最小割 - 掌握最大流最小割定理，理解应用
• 504. 二分图匹配 - 掌握匈牙利算法，理解增广路
• 505. 最小费用最大流 - 掌握SPFA/Dijkstra优化
• 506. 网络流建模 - 掌握拆点、超级源汇、容量限制

4.4 排序算法

4.4.1 比较排序

• 507. 冒泡排序 - 掌握O(n²)交换排序，理解优化（提前终止）
• 508. 选择排序 - 掌握O(n²)选择最小，理解不稳定
• 509. 插入排序 - 掌握O(n²)逐步构建，理解基本有序时高效
• 510. 希尔排序 - 掌握增量序列优化，理解O(n^(3/2))
• 511. 归并排序 - 掌握分治O(nlogn)，理解稳定排序
• 512. 快速排序 - 掌握分区和基准选择，理解最坏O(n²)
• 513. 堆排序 - 掌握堆性质利用，理解原地排序
• 514. 排序稳定性 - 理解稳定与不稳定排序，掌握稳定性意义
• 515. 快排优化 - 掌握三数取中、小数组切换插入排序
• 516. 归并优化 - 掌握小数组切换插入、相邻有序跳过合并
• 517. 比较排序下界 - 理解决策树证明Ω(nlogn)

4.4.2 非比较排序

• 518. 计数排序 - 掌握小范围整数排序，理解O(n+k)
• 519. 基数排序 - 掌握多关键字排序，理解LSD/MSD
• 520. 桶排序 - 掌握均匀分布优化，理解O(n)期望时间
• 521. TimSort - 理解Java/Python实际使用，掌握自然归并
• 522. 外部排序 - 掌握大数据排序，理解多路归并
• 523. 排序算法选择 - 掌握场景适配，理解数据特征分析
• 524. 排序稳定性应用 - 理解多关键字排序需要稳定性

4.5 算法思想

4.5.1 递归与分治

• 525. 递归设计 - 掌握基准情况和递归式，理解递归树
• 526. 分治法 - 掌握大问题拆分，理解合并策略
• 527. 主定理 - 掌握复杂度分析，理解3种情况
• 528. 汉诺塔问题 - 掌握递归应用，理解2^n-1步
• 529. 归并排序实现 - 掌握分治排序，理解合并过程
• 530. 快速选择 - 掌握第k大元素，理解O(n)期望时间
• 531. 递归转迭代 - 掌握栈模拟递归，理解尾递归优化
• 532. 分治应用 - 掌握最近点对、大整数乘法（Karatsuba）
• 533. 递归记忆化 - 掌握缓存中间结果，理解自顶向下DP

4.5.2 动态规划

• 534. DP状态定义 - 掌握子问题表示，理解最优子结构
• 535. 状态转移方程 - 掌握递推关系，理解无后效性
• 536. 斐波那契优化 - 掌握记忆化搜索和递推，理解状态压缩
• 537. 背包问题 - 掌握01背包、完全背包、多重背包
• 538. 最长公共子序列 - 掌握DP表格，理解路径回溯
• 539. 最长递增子序列 - 掌握O(n²)和O(nlogn)优化（贪心+二分）
• 540. 编辑距离 - 掌握字符串DP，理解插入/删除/替换
• 541. 矩阵链乘法 - 掌握区间DP，理解括号化方案
• 542. DP空间优化 - 掌握状态压缩（滚动数组），理解空间优化技巧
• 543. 区间DP - 掌握区间合并，理解枚举分割点
• 544. 树形DP - 掌握树上状态转移，理解子树信息合并
• 545. 状态压缩DP - 掌握位运算表示状态，理解TSP问题
• 546. 数位DP - 掌握逐位枚举，理解记忆化搜索
• 547. 单调队列优化DP - 掌握滑动窗口优化状态转移
• 548. 斜率优化DP - 掌握凸包优化，理解决策单调性
• 549. DP与贪心区别 - 理解全局最优vs局部最优

4.5.3 贪心与回溯

• 550. 贪心选择性质 - 掌握局部最优推导全局最优
• 551. 活动选择问题 - 掌握贪心应用，理解最早结束时间
• 552. 霍夫曼编码 - 掌握贪心构造，理解前缀编码
• 553. 贪心适用性 - 掌握贪心与DP的区别，理解反例证明
• 554. 回溯框架 - 掌握选择-递归-撤销，理解状态树
• 555. N皇后问题 - 掌握回溯应用，理解位运算优化
• 556. 数独求解 - 掌握回溯优化，理解候选数剪枝
• 557. 全排列 - 掌握排列生成，理解去重处理
• 558. 子集枚举 - 掌握位掩码和回溯两种方法
• 559. 组合总和 - 掌握剪枝优化，理解去重策略
• 560. 回溯剪枝 - 掌握可行性剪枝和最优性剪枝

4.5.4 其他算法

• 561. 双指针技巧 - 掌握左右指针、快慢指针、同向双指针
• 562. 滑动窗口 - 掌握子串/子数组问题，理解窗口收缩
• 563. 位运算技巧 - 掌握异或、与、或、移位应用
• 564. 前缀和 - 掌握区间和查询，理解二维前缀和
• 565. 二分查找 - 掌握左闭右开/左闭右闭、边界处理
• 566. 摩尔投票法 - 掌握多数元素，理解抵消原理
• 567. KMP算法 - 掌握字符串匹配，理解next数组
• 568. Manacher算法 - 掌握最长回文子串，理解中心扩展优化
• 569. 三分查找 - 掌握单峰函数极值，理解凹凸性
• 570. 随机算法 - 掌握随机化快速排序、随机选择
• 571. 矩阵快速幂 - 掌握斐波那契O(logn)，理解矩阵乘法
• 572. 扩展欧几里得 - 掌握ax+by=gcd，理解逆元计算

4.6 算法复杂度

4.6.1 时间复杂度

• 573. 大O表示法 - 掌握渐进上界，理解忽略常数因子
• 574. 最好/最坏/平均复杂度 - 理解不同情况，掌握快排分析
• 575. 均摊复杂度 - 掌握动态数组分析，理解聚合/核算/势能法
• 576. 复杂度计算规则 - 掌握加法法则和乘法法则
• 577. 常见复杂度排序 - 理解O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)
• 578. 对数复杂度理解 - 掌握二分O(logn)、BST操作
• 579. 指数复杂度 - 理解2ⁿ、n!复杂度，掌握避免策略
• 580. 复杂度分析实战 - 掌握循环、递归、嵌套分析

4.6.2 空间复杂度

• 581. 额外空间分析 - 掌握原地算法，理解O(1)空间
• 582. 递归栈空间 - 掌握递归深度分析，理解树高
• 583. 空间换时间 - 掌握缓存优化，理解哈希表空间代价
• 584. 原地排序 - 掌握O(1)空间算法（快排、堆排、插排）
• 585. 复杂度权衡 - 掌握时空平衡，理解Trade-off决策
• 586. 辅助空间优化 - 掌握滚动数组、状态压缩

4.7 算法实战与刷题策略

4.7.1 刷题方法论

• 587. LeetCode刷题路线 - 掌握按难度、类型递进
• 588. 题目分类总结 - 掌握数组、链表、树、图等分类
• 589. 模板代码积累 - 掌握常用算法模板
• 590. 边界条件检查 - 掌握空输入、极端值、溢出处理
• 591. 测试用例设计 - 掌握正常、边界、异常用例
• 592. 代码优化思路 - 掌握暴力→优化→最优的递进

4.7.2 常见题型

• 593. 数组类题目 - 掌握两数之和、三数之和、旋转数组
• 594. 链表类题目 - 掌握反转、环检测、合并
• 595. 二叉树类题目 - 掌握遍历、路径、最近公共祖先
• 596. 字符串类题目 - 掌握回文、匹配、编辑距离
• 597. 动态规划类题目 - 掌握背包、子序列、路径问题
• 598. 图论类题目 - 掌握最短路径、拓扑排序、连通性
• 599. 设计类题目 - 掌握LRU、LFU、数据结构组合设计
• 600. 面试高频题 - 掌握Top 100高频题目

---

进度统计

• 领域：数据结构与算法
• 知识点总数：285项
• 已完成：0项
• 待完成：285项

实战项目建议

• 项目1：数据结构可视化 - 实现各种数据结构的可视化操作演示（树旋转、图遍历动画）
• 项目2：算法评测系统 - 实现支持多种语言的在线编程评测系统（OJ），包含判题、排行榜
• 项目3：表达式计算器 - 实现支持括号、函数、变量的表达式求值，包含中缀转后缀

常见面试问题

• HashMap的底层原理？JDK 8做了哪些优化？为什么链表长度>8转红黑树？
• 快排的最坏情况是什么？如何优化？
• 动态规划和贪心算法的区别？什么情况下贪心能得到最优解？
• 红黑树的5条性质？为什么选择红黑树而不是AVL树？
• 如何判断一个链表是否有环？如何找到环的入口？

推荐学习资源

• 书籍：《算法导论》《算法》《剑指Offer》《程序员代码面试指南》
• 网站：LeetCode、牛客网、Codeforces
• 课程：MIT 6.006、普林斯顿算法课

---

返回总目录