作为非科班出身，总被《算法导论》整得头晕。18年春节期间加入《数据结构和算法之美》课程，作者王争推荐了这两本入门书，会学校图书馆借阅并从头到尾读了一遍，让自己不再总是担心在面试中被问及数据结构和算法的问题。两本书的最大优点是可视化讲解，我个人比较擅长可视化思考，故符合我的胃口。

「算法图解」知识点

  • 选择排序
  • 递归
  • 快速排序
  • 散列表
  • 广度优先搜索 $\to$ Dijkstra算法适用于有向无环图，且不能用于包含负权边的图（需用 Bellman-Ford 算法）
  • 贪婪算法
  • 动态规划
  • K最近邻算法
  • 树、反向索引、傅立叶变换、并行算法、MapReduce、布隆过滤器和HyperLogLog、SHA算法、局部敏感的散列算法、Diffie-Hellman密钥交换、线性规划（图算法的升级） $\cdots$

算法库与容器库——「STL源码剖析」

容器库：容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。容器管理为其元素分配的存储空间，并提供直接或间接地通过迭代器（拥有类似指针属性的对象）访问它们的函数。大多数容器拥有至少几个常见的成员函数，并共享功能。特定应用的最佳容器不仅依赖于提供的功能，还依赖于对于不同工作量的效率。

  • 顺序容器实现能按顺序访问的数据结构。
  • 关联容器实现能快速查找（ $O(\log n)$ 复杂度）的（红黑树）数据结构。
  • 无序关联容器提供能快速查找（均摊 $O(1)$ ，最坏情况 $O(n)$ 的复杂度）的无序（哈希）数据结构。
  • 容器适配器提供顺序容器的不同接口。

算法库：算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为 [first, last) ，其中 last 指代要查询或修改的最后元素的后一个元素。