算法与数据结构算是开发的基础了，在学习思考的过程中还是能够体会到其中蕴含的乐趣的。在力扣上也有700多题了，简单做个总结。

算法部分

排序：

排序还是比较多的，列几个我熟悉的。如果是解题的话直接sort就行。

  • 插入、冒泡、选择 O(n^2)
  • 快排、堆排序、归并排序 O(nlogn)
  • 桶排序 O(n + k)

二分查找

二分查找是分治思想，操作一次时间复杂度 O(logn)。二分查找很容遇到边界的问题，我们可以通过红蓝分界法规避到很多边界问题。

  • 红蓝分界模版伪代码

    // 左边为蓝色区域，右边为红色区域
l = -1, r = N
while l + 1 != r
    m = (l + r) >> 1
    if isBlue(m)
        l = m
    else 
        r = m
return l or r

DFS、BFS

  • dfs：深度优先搜索
    • 可以递归或者栈模拟的方式去做搜索
  • bfs：广度优先搜索
    • 可以通过队列做层序遍历

回溯

典型的一个例子： n皇后

  • 回溯算法也是深度搜索。
  • 回溯算法是对树形或者图行结构执行一次深度优先遍历，在遍历的过程中尝试找到问题的解。
  • 当发现不满足条件的解时需要把状态重置。

动态规划（DP）

  1. 动态规划问题关键在于找出子问题，然后列出状态转移方程。

  2. 动态规划有自底向上和自顶向下的方式，自顶向下就是记忆化搜索，自低向上就是递推。

  3. 如果一开始没想到递推式，可以先通过记忆化搜索去解题。从递归到递推也是一个很好的思考动态规划问题的思路。
  4. 动态规划问题有很多类型，比如01背包、完全背包、状态dp、区间dp、状压dp、数位dp等。还是需要多思考练习的

贪心

  • 贪心算法其实没有特定套路，主要靠直觉和经验，就是【贪心的选择】主要是找局部最优解，并且无后效性。严格意义上是需要数学证明的。

位运算

主要是掌握住位运算的一些技巧。也可以用位运算做一些状态压缩。

滑动窗口、双指针

  • 一般通过在数组上通过同向移动的两个指针去解决一些问题。

字符串相关

  • KMP
    • 做字符串匹配，本质上也是一种dp的思路，这个需要多记忆一下，还是容易忘的。
  • 字典树
    • 前缀树，又称字典树。它是一棵 N 叉树。前缀树用于存储、查找字符串。

数据结构相关

数组、集合、字典先不说了

队列

  • 先进先出

栈

  • 先进后出

堆（优先队列）

可以通过堆解决一些topk问题，也可以堆做排序，Dijkstra算法也用到了堆做时间复杂度优化，也能通过堆做一些任务管理问题。

链表

  • 单向链表
  • 双向链表
    • 常见的应用比如说实现 LRU（双向链表 + 哈希表），像iOS里面的自动释放池也是双向链表

二叉树

比较复杂的像红黑树在数据结构也是比较常用的

  • 遍历
    • 前中后序遍历、层序遍历

图

图是链接的一种抽象关系。像链表，二叉树、树，其实都是图。

图论中的很多问题都可以通过dfs、bfs完成。

  1. 图的创建
    • 邻接矩阵、邻接表
  2. 最短路算法
    • 比较经典的Dijkstra 算法，其他的比如Bellman-Ford 算法、Floyd 算法
  3. 最小生成树算法
    • Prim 算法、Kruskal 算法
  4. 拓扑排序
    • 可以根据入度做拓扑排序。通过拓扑排序也可以找图中的环。

区间问题（线段树、树状数组）

我们可以通过线段树、树状数组处理一些区间变更问题。

  • 线段树
    • 比如说动态处理一些区间染色，区间计算等问题
  • 树状数组
    • 比如说动态处理一些区间计算、前缀和等问题

以上是做了一个简单的总结，学习算法和数据结构的过程中，还是有很多乐趣的，尤其是在思考的过程中。后续有时间再针对各个模块做一些详细总结。