资源

课程

Princeton

• Textbooks:
  • Algorithms, 4th Edition
  • An Introduction to the Analysis of Algorithms, 2nd Edition
• Courses:
  • Algorithms, Part 1
  • Algorithms, Part 2
  • Analysis of Algorithms
• Libraries:
  • Java Algorithms and Clients
  • kevin-wayne/algs4 on GitHub

MIT

• Textbook:
  • Introduction to Algorithms, Third Edition
• Courses:
  • Introduction to Algorithms taught by Prof. Erik Demaine and Prof. Srini Devadas in Fall 2011.
  • Design and Analysis of Algorithms taught by Prof. Erik Demaine and Prof. Srini Devadas and Prof. Nancy Lynch in Spring 2015.

网站

在线演示

• VisuAlgo: visualising data structures and algorithms through animation.

在线练习

• LeetCode: the world’s leading online programming learning platform.
  • 建议用 leetcode.vscode-leetcode 在本地刷题及备份。本地题库无法更新时，可先执行 rm ~/.lc/leetcode/cache/problems.json，再点击刷新按钮。
  • 获取实时统计信息：json 或 svg
• PAT (Programming Ability Test) and PTA (Programming Teaching Assistant).
• 牛客网

数组及基于数组的算法

数组的实现

长度固定的数组、长度可变的数组（向量）

通用排序

平方排序、Shell 排序、归并排序、快速排序

通用查找

顺序查找、二分查找、排列

并查集

队列 (Queues)

线性队列

链表、队列、栈、双向队列、随机队列

优先队列

二叉堆、Fibonacci 堆、van Emde Boas 树

散列 (Hashing)

散列函数

必要条件、基于余数的散列函数、基于乘法的散列函数、程序实现

冲突化解

分离链法、开地址法

全域散列

全域散列函数族、基于点乘的全域散列、基于余数的全域散列

完美散列

静态字典、二重散列

树 (Trees)

树的实现

二叉搜索树

平衡搜索树

AVL 树、红黑树、B-树

几何搜索树

Kd-树、区间树

图 (Graphs)

图的实现

邻接矩阵、邻接链表、邻接集合、隐式表示

广度优先搜索

递归实现、循环实现、应用

深度优先搜索

递归实现、邻接集合、应用（环路检测、拓扑排序、数独求解器）

最小展开树

Kruskal、Prim

单源最短路径

Dijkstra、Bellman–Ford

全源最短路径

矩阵乘幂类比、Floyd–Warshall、Johnson

最大流、最小割

Ford–Fulkerson、最大流–最小割定理

串 (Strings)

串的实现

基数排序

始于末位的基数排序、始于首位的基数排序、三路基数快速排序

后缀数组

字典树

R-路字典树、三元搜索字典树

子串搜索

Knuth–Morris–Pratt、Boyer–Moore、Rabin–Karp

正则表达式

匹配算法（NFA、动态规划）

数据压缩

复杂度

数学（理论）分析

科学（实验）测量

NP-完备性

常用策略

分而治之

动态规划

贪心选择