作者:来知晓
公众号:来知晓
刷题交流QQ群:444172041

前言


本文把各分散的刷题博客总结,归纳整理成体系,汇总于此,刷题在精不在多,需能理解本质,做到举一反三,一通百通。欢迎盆友们讨论交流。

高频解题框架


对算法套路的特点进行总结,如下表:

算法套路 应用场景 相关数据结构 备注
DFS深搜 本质是前序、中序、后序遍历的各种改编 递归/迭代
BFS广搜 本质是层序遍历的各种改编 队列 迭代
滑动窗口 应用场景多为字符串子串子序列,本质是暴力解法两层for循环的优化,动态调整left/right边界 字符串 双指针技巧
二分法 应用场景为查找指定值或者左右边界,要求输入有序 数组/字符串 时间复杂度logN
区间问题 todo 数组

对高级数据结构的特点进行总结,如下表:

数据结构套路 应用场景 本质 备注
优先队列/最大堆 求前k个最大(最小)的问题 数组/树
Hash 用在高频率的字符串/数值的查找中 散列 O(1)
二叉树 结合DFS/BFS以及树的性质来操作,具有极强灵活性

优先队列相关题目:
373. 查找和最小的K对数字

下面是算法套路和数据结构套路的实战总结,将各博客汇总分类如下,水平有限,欢迎拍砖。

算法套路


DFS深搜

todo

BFS广搜

todo

滑动窗口/滑窗

todo

二分法总结

区间问题

todo

数据结构套路


主要是一些高级数据结构的直接应用。

  • 链表
  • 优先队列
  • Hash
  • 二叉树

必备工程技巧


  • 动态申请二维数组
  • 排序:调用qsort快排函数给一维数组、二维数组、字符串等排序