看到 Github 的 trend 上面有个迅速攀升的 repo，一看是讲如何面对算法和如何解决算法的。刚好在家闲来无事，学习一下。
https://github.com/labuladong/fucking-algorithm
能看到真的说人话的教程真的很幸运，不要放弃这种学习透彻的机会。
学习数据结构和算法的框架思维
作者首先讲了，本 repo 的目的就是给数据结构和算法做一个框架性的认识。
从整体到细节，自顶向下，从抽象到具体的框架思维是通用的。
一、数据结构的存储方式
数据结构在最底层的存储方式只有两种：数组（顺序存储） 和 链表（链式存储）。
至于说其他的数据类型，比如树，图，堆，队列等等，都只是“上层建筑”，其最底层的结构基础还是数组和链表。因为这些多样化的数据结构，究其源头，都只是在链表和数组上面的特殊操作，只是API不同而已。
- ”队列“，”栈“这两种数据结构既可以使用链表也可以使用数组实现，用数组实现，就要考虑扩容缩容的问题，用链表实现，就得更多的内存空间来存储节点指针。
- ”图“的两种方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，且可以使用邻接矩阵运算解决某些问题，但是如果图比较稀疏的话会浪费空间。邻接表就比较节省空间，但是很多操作的效率上面不如邻接矩阵。
- ”散列表“，就是使用散列函数将键映射到大数组之中，而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单但是需要额外的空间存储指针。线性探查法就需要数组特性，以便连续寻址，但是操作稍微复杂一些。
- ”树“，用数组实现就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单。用链表实现就是比较常见的“树”，因为不一定是完全二叉树，所以不适合用数组存储。为此，在“链表树“的结构之上，又延伸出各种巧妙的设计，比如二叉搜索树，AVL树，红黑树，区间树，B树等，来应对不同的问题。
举个例子，对于Redis来说，其提供列表，字符串，集合等等几种常用的数据结构，但是对于每种数据结构，其底层的存储方式都至少是两种，以便根据存储数据的实际情况选择合适的存储方式。
综上所述，数据结构种类很多，甚至可以发明自己的数据结构。但是底层存储，无非是数组或者链表，二者的优缺点对比如下：
- 数组可以随机访问，且相对节约存储空间（无需存储额外的指针），但是正因为是连续存储，其空间最好一次性分够，所以说如果数组要扩容，必须重新分配一块额外的更大空间，再把数据全部复制过去，时间复杂度O(N)。而且想在数组的中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度O(N)。
- 链表因为元素不连续，所以不存在数组的扩容问题。只要知道某个元素的前驱和后驱，操作指针即可删除或者插入元素，时间复杂度为O(1)。但是也正是因为存储空间不连续，所以无法根据一个索引来算出其元素的地址，也就是不可以随机访问。而且每个元素要存储其前后的元素地址，会占用更多的存储空间。
二、数据结构的基本操作
作者将整个数据结构的操作分为两个方面进行描述：线性/非线性，递归/遍历。
对于任何的数据结构，其基本操作都是CRUD，也就是遍历+ 访问。
那么遍历+访问的方式就是分为两种：线性的和非线性的。
线性的就是以 for while 为代表，而非线性就是以递归为代表。下面几种框架是具体的形式：
数组遍历框架，线性迭代：
void traverse(int[] arr){
for(int i =0;i<arr.length;i++){
//Iterate visit arr
}
}
链表遍历框架，兼具迭代和递归结构，下面代码之中将二者都提供：
class ListNode {
int val;
ListNode next;
}
//迭代访问
void traverseList(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
//Iterator visit LinkedList
}
}
//递归访问
void traverseList(ListNode head) {
traverseList(head.next);
}
二叉树遍历框架：典型的非线性递归遍历结构：
class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
void traverseTree(TreeNode root){
traverseTree(root.left);
traverseTree(root.right);
}
在递归遍历结构之中，大家都是相似的。从二叉树扩展到多叉树也是一样的步骤：
class TreeNode{
int val;
TreeNode[] child;
}
void traverseTree(TreeNode root){
for(TreeNode treeNode:root.child){
traverseTree(treeNode);
}
}
从多叉树扩展到图的遍历也是一样的步骤，因为图就是几棵树的结合体。如果防止出现坏图的情况，只要使用一个布尔数组做标记就可以了。
三、算法刷题指南
先刷二叉树
