learn and think

这里的内容是我学习算法过程的一些记录。

内容

• algorithm 4 实现
• grokking-the-coding-interview

基本数据结构和算法

链表

• 链表
• 双向链表

哈希表/散列表 (Hash Table)

• 散列函数
• 碰撞解决

字符串算法

• 排序
• 查找
  • BF算法
  • KMP算法
  • BM算法
• 正则表达式
• 数据压缩

树

• 二叉树
• 二叉查找树
• 伸展树(splay tree 分裂树)
• 平衡二叉树AVL
• 红黑树
• B树,B+,B*
• R树
• Trie树(前缀树)
• 后缀树
• 最优二叉树(赫夫曼树)
• 二叉堆 （大根堆，小根堆）
• 二项树
• 二项堆
• 斐波那契堆(Fibonacci Heap)

图的算法

• 图的存储结构和基本操作（建立，遍历，删除节点，添加节点）
• 最小生成树
• 拓扑排序
• 关键路径
• 最短路径: Floyd,Dijkstra,bellman-ford,spfa

排序算法

交换排序算法

• 冒泡排序
• 插入排序
• 选择排序
• 希尔排序
• 快排
• 归并排序
• 堆排序

线性排序算法

• 桶排序

查找算法

• 顺序表查找：顺序查找
• 有序表查找：二分查找
• 分块查找： 块内无序，块之间有序；可以先二分查找定位到块，然后再到块中顺序查找
• 动态查找: 二叉排序树，AVL树，B- ，B+ （这里之所以叫 动态查找表，是因为表结构是查找的过程中动态生成的）
• 哈希表： O(1)

15个经典基础算法

• Hash
• 快速排序
• 快递选择SELECT
• BFS/DFS （广度/深度优先遍历）
• 红黑树 （一种自平衡的二叉查找树）
• KMP 字符串匹配算法
• DP (动态规划 dynamic programming)
• A*寻路算法： 求解最短路径
• Dijkstra：最短路径算法 （八卦下：Dijkstra是荷兰的计算机科学家,提出”信号量和PV原语“,"解决哲学家就餐问题",”死锁“也是它提出来的）
• 遗传算法
• 启发式搜索
• 图像特征提取之SIFT算法
• 傅立叶变换
• SPFA(shortest path faster algorithm) 单元最短路径算法

海量数据处理

• Hash映射/分而治之
• Bitmap
• Bloom filter(布隆过滤器)
• Trie树
• 数据库索引
• 倒排索引(Inverted Index)
• 双层桶划分
• 外排序
• simhash算法
• 分布处理之Mapreduce