1 README¶
tag-placeholder file is in Chinese
算法虐我千百遍,我待算法如初恋
这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。
0.1 学习方法¶
- 把所有经典算法写一遍
- 看算法有关源码
- 加入算法学习社区,相互鼓励学习 (加我 vx:tiger-ran, 备注入群理由, 拉你入群)
- 看经典书籍
- 刷题
0.2 基本数据结构和算法¶
这些算法全部自己敲一遍:
1 链表¶
- 链表
- 双向链表
2 数组¶
数组和链表结构是基础结构,散列表、栈、队列、堆、树、图等等各种数据结构都基于数组和链表结构实现。
3 队列¶
- 队列
- 堆栈
4 哈希表 HashTable¶
- 散列函数
- 碰撞解决
5 字符串算法¶
- 子串查找 字符串常见题目参考这里
- BF 算法
- KMP 算法
- BM 算法
- 正则表达式
- 数据压缩
- 排序
6 树¶
- 二叉树 快速排序 就是个二叉树的前序遍历,归并排序就是个二叉树的后序遍历
- 二叉查找树BST 有序的二叉树,中序遍历结果是递增的
- 平衡二叉树 AVL树 绝对平衡二叉树;
- 红黑树 弱平衡二叉树;使用广泛
- B树
- B+树 mysql 索引使用 B+ 树 的数据结构
- 字典树trie 字典树也叫前缀树,单词查找树
- 二叉堆
- 伸展树
- 后缀树
- 斐波那契堆 (Fibonacci Heap)
- 最优二叉树 (赫夫曼树)
7 图的算法¶
- 图的存储结构和基本操作(建立,遍历,删除节点,添加节点)
- 最小生成树
- 拓扑排序
- 关键路径
- 最短路径: Floyd,Dijkstra,bellman-ford,spfa
8 排序算法¶
交换排序算法
- 冒泡排序
- 插入排序
- 选择排序
- 希尔排序
- 快排
- 归并排序
- 堆排序
线性排序算法
- 桶排序
9 查找算法¶
- 哈希表: O(1) hashtable实现参考这里
- 有序表查找:二分查找
- 顺序表查找:顺序查找, 复杂度 O(N)
- 分块查找: 块内无序,块之间有序;可以先二分查找定位到块,然后再到
块
中顺序查找 - 动态查找: 二叉排序树,AVL 树,B- ,B+(这里之所以叫
动态查找表
,是因为表结构是查找的过程中动态生成的)
10 算法设计思想¶
11 面试算法题目¶
这是一个算法题目合集,题目是我从网络和书籍之中整理而来,部分题目已经做了思路整理。问题分类包括:
- 字符串
- 堆和栈
- 链表
- 数值问题
- 数组和数列问题
- 矩阵问题
- 二叉树
- 图
- 海量数据处理
- 智力思维训练
- 系统设计
还有部分来自算法网站和书籍:
- 九度 OJ
- leetcode
- 剑指 offer
12 海量数据处理¶
- Hash 映射/分而治之
- Bitmap
- Bloom filter(布隆过滤器)
- Trie 树
- 数据库索引
- 倒排索引 (Inverted Index)
- 双层桶划分
- 外排序
- simhash 算法
- 分布处理之 Mapreduce
13 开源项目中的算法¶
- YYCache
- cocos2d-objc
- bitcoin
- geohash
- kafka
- nginx
- zookeeper
- ...
14 15 个经典基础算法¶
- KMP 字符串匹配算法
- Hash
- 快速排序
- 快速选择 SELECT
- 红黑树 (一种弱/自平衡的
二叉查找树
) - BFS/DFS (广度/深度优先遍历)
A*
寻路算法: 求解最短路径- Dijkstra:最短路径算法
SPFA(Shortest Path Faster Algorithm)
单元最短路径算法- 启发式搜索
- 遗传算法
GA
- DP (动态规划 dynamic programming)
- 图像特征提取之
SIFT
算法 , 广泛的应用于图像识别,图像检索,3D 重建等 CV 的各种领域 - 傅立叶变换
15 推荐阅读¶
15.1 刷题必备¶
- 《剑指 offer》
- 《编程之美》
- 《编程之法: 面试和算法心得》
- 《算法谜题》 都是思维题
15.2 基础¶
- 《编程珠玑》Programming Pearls
- 《编程珠玑 (续)》
- 《数据结构与算法分析》
- 《Algorithms》 这本近千页的书只有 6 章,其中四章分别是排序,查找,图,字符串,足见介绍细致
15.3 算法设计¶
- 《算法设计与分析基础》
- 《算法引论》 告诉你如何创造算法 断货
- 《Algorithm Design Manual》算法设计手册 红皮书
- 《算法导论》 是一本对算法介绍比较全面的经典书籍
- 《Algorithms on Strings,Trees and Sequences》
- 《Advanced Data Structures》 各种诡异高级的数据结构和算法 如元胞自动机、斐波纳契堆、线段树 600 块
15.4 延伸阅读¶
- 《深入理解计算机系统》
- 《TCP/IP 详解三卷》
- 《UNIX 网络编程二卷》
- 《UNIX 环境高级编程:第 2 版》
- 《The practice of programming》 Brian Kernighan 和 Rob Pike
- 《writing efficient programs》 优化
- 《The science of programming》 证明代码段的正确性 800 块一本
16 参考链接和学习网站¶
16.1 July 博客¶
- 《数学建模十大经典算法》
- 《数据挖掘领域十大经典算法》
- 《十道海量数据处理面试题》
- 《数字图像处理领域的二十四个经典算法》
- 《精选微软等公司经典的算法面试 100 题》
- The-Art-Of-Programming-By-July
- 微软面试100题
- 程序员编程艺术
16.2 基本算法演示¶
http://sjjg.js.zwu.edu.cn/SFXX/sf1/sfys.html http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
16.3 编程网站¶
16.4 网课¶
高级数据结构和算法 北大教授张铭老师在 coursera 上的课程。完成这门课之时,你将掌握多维数组、广义表、Trie 树、AVL 树、伸展树等高级数据结构,并结合内排序、外排序、检索、索引有关的算法,高效地解决现实生活中一些比较复杂的应用问题。当然 coursera 上也还有很多其它算法方面的视频课程。
算法设计与分析 Design and Analysis of Algorithms 由北大教授 Wanling Qu 在 coursera 讲授的一门算法课程。首先介绍一些与算法有关的基础知识,然后阐述经典的算法设计思想和分析技术,主要涉及的算法设计技术是:分治策略、动态规划、贪心法、回溯与分支限界等。每个视频都配有相应的讲义(pdf 文件)以便阅读和复习。
16.5 其它¶
OI Wiki 主要内容是 OI/ACM-ICPC 编程竞赛 (competitive programming) 相关的知识整理, 包括基础知识、常见题型、解题思路以及常用工具等内容。
labuladong 的算法小抄 作者整理了很多的解题套路框架,看完获益良多