数据结构与算法总纲
数据结构：
一维：基础：数组arry（string）、链表Link list 高级：栈（stack）、队列（Queue）、双端队列（deque）、集合（Set）、映射Map（hash or map）、 二维：基础：树（Tree）、图（Graph） 高级：二叉搜索树（binary search tree）：根节点大于左子树，小于右子树 特殊的二叉搜索树：红黑树（Red-Black Tree）、AVL、堆（Heap）、并查集（disjoin set）、字典树（Trie） 特殊：位运算：Bitwise,布隆过滤器BloomFilter 缓存：LUR cache
算法：
逻辑切换：if-else,switch -> branch 循环：for, while loop -> lteration 递归：Recursion（Divide & Conquer， Back trace） 搜索（Search）：深度优先搜索Depth first Search，广度优先搜索Breadth first seach 动态规划：Dynamic Programing 二分查找：Binary Search 贪心：Greedy 数学：Math、几何Geometry
数据结构
数组（Array）：
有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组
查：O（1）：由于其特性内存地址有序，能够任意的访问到数组中任何一个元素
增删：由于是连续的，所以若想修改须将新增的元素与原数组重新排序（一般为新建一个数组将）
元素末尾插入删除：O（1）
元素中任意位置插入删除：O（n）
数组的优点在于：构建非常简单 能在 O(1) 的时间里根据数组的下标（index）查询某个元素 而数组的缺点在于：构建时必须分配一段连续的空间 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数） 删除和添加某个元素时，同样需要耗费 O(n) 的时间 应用场景：如果要解决的问题里面需要很多添加和删除，数组可能并不适合；如果遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的查找，那么数组会比较合适。
链表（Linked list）：
存储单元非连续、非顺序的存储结构，元素更具链表中的指针衔接实现
查O（n）：由于其特性内存地址由指针衔接，能够任意修改的到中任何一个元素。内存地址无序
增删：O（1）：由指针衔接
链表的优点如下：链表能灵活地分配内存空间；能在 O(1) 时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。链表的缺点是：不像数组能通过下标迅速读取元素，每次都要从链表头开始一个一个读取；查询第 k 个元素需要 O(k) 时间。应用场景：如果要解决的问题里面需要很多快速查询，链表可能并不适合；如果遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适。而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。
跳表（Skip Table）：
特殊的链表，只能使用于元素有序的情况；维护成本较高
对标（可取代）：平衡树、二分查找 插入/删除/搜索 都是O(log n) 的结构
简单优化：添加头尾指针
查：O（log n）
增删：O（1），由于必须是有序
栈（Stack）
特点：栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的元素，只能够向栈的顶部压⼊数据，也只能从栈的顶部弹出数据。实现：利用一个单链表来实现栈的数据结构。而且，因为都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。应用场景：在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。
队列（Queue）
特点：和栈不同，队列的最大特点是先进先出（FIFO），就好像按顺序排队一样。对于队列的数据来说，只允许在队尾查看和添加数据，在队头查看和删除数据。实现：可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，而双链表的尾指针在队尾查看和添加数据。应用场景：直观来看，当需要按照一定的顺序来处理数据，而该数据的数据量在不断地变化的时候，则需要队列来帮助解题
双端队列（Deque）
特点：双端队列和普通队列最大的不同在于，在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。实现：与队列相似，可以利用一个双链表实现双端队列。应用场景：双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。
优先队列（Priority Queue）
特点 能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。应用场景 从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。1. 向上筛选（sift up / bubble up） 当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。时间复杂度：由于二叉堆是一棵完全二叉树，并假设堆的大小为 k，因此整个过程其实就是沿着树的高度往上爬，所以只需要 O(logk) 的时间。2. 向下筛选（sift down / bubble down） 当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。
树（Tree）
树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。正因为树有这样的性质，大部分关于树的面试题都与递归有关 树的形状：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree） 树的遍历 1. 前序遍历（Preorder Traversal） 方法：先访问根节点，然后访问左子树，最后访问右子树。在访问左、右子树的时候，同样，先访问子树的根节点，再访问子树根节点的左子树和右子树，这是一个不断递归的过程。2. 中序遍历（Inorder Traversal） 方法：先访问左子树，然后访问根节点，最后访问右子树，在访问左、右子树的时候，同样，先访问子树的左边，再访问子树的根节点，最后再访问子树的右边。3. 后序遍历（Postorder Traversal） 方法：先访问左子树，然后访问右子树，最后访问根节点。
图（Graph）
基本知识点 阶（Order）、度：出度（Out-Degree）、入度（In-Degree） 树（Tree）、森林（Forest）、环（Loop） 有向图（Directed Graph）、无向图（Undirected Graph）、完全有向图、完全无向图 连通图（Connected Graph）、连通分量（Connected Component） 存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List） 图的算法：。图的遍历：深度优先、广度优先 环的检测：有向图、无向图 拓扑排序 实例：最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树 图的着色、旅行商问题等 重点: 图的存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List） 图的遍历：深度优先、广度优先 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图 拓扑排序 联合-查找算法（Union-Find） 最短路径：Dijkstra、Bellman-Ford
学习三步骤：
预习:基础知识点预习与查看
课堂互动：思考问题、解决问题
课后作业：
LeetCode 300+的积累
Chunk it up：切碎知识点 庖丁解牛+脉络连接 Deliberate Practicaing 刻意练习 过遍数：五遍刷题 练习弱项、专项练习 Feedback 反馈：即时反馈：主动寻求反馈：自己去找——看高手怎么写、操作的 被动反馈：高手点评
切题四件套：
Clarification：理解题意（目标、限制）
Possible solutions:想多种解法，寻求最优解
Compare：（Time/Space） optimal：（加强）
Coding：（多写）
Test cases：测试
刷题五部曲
过遍数、敢于放手、敢于死记硬背、善于看高手的代码，不要死磕！！！五分钟想不出来直接看题解
第一遍：
读题+思考（5min）
如果不知道怎么做的话：直接看解法（多解法、比较优劣）
背诵、默写好解法（理解）
第二遍：（第一遍完成后）
马上自己写 -> LeetCode提交
多种解法比较、体会 -> 优化
第三遍：（一天后）
不同解法熟练程度- > 专项训练
第四遍：（一周以后）
反复练习相同、相类似的题目
第五遍：
面试前一周恢复性训练
