数据结构
数组
概念：用一组连续的内存空间来存储一组具有相同类型的数据；线性表：数组、链表、队列、栈等；非线性表：二叉树、堆、图等；
链表
分类：单链表（增加虚拟头结点方便逻辑统一）、双向链表（增加虚拟尾结点方便遍历）、循环双向链表；
操作：链表反转（增加头结点、就地反转、递归实现）、寻找中间节点（快慢指针实现）；
栈
概念：先进后出的数据结构；常用操作：入栈和出栈；实现包括：顺序栈（数组实现）、链栈（链表实现）；应用：括号匹配等；
队列
概念：先进先出的数据结构；常用属性：队头队尾、入队出队；可通过数组和链表实现；有双向队列、循环队列；
哈希表
概念：由关键码的值决定数据的存储地址，查找速度O(1)与元素个数无关；关键码的转换就是哈希函数；哈希方法：直接线性函数定址、除留余数、乘余取整、数字分析、平方取中、折叠法、随机数；
哈希冲突：关键码集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上；冲突不能避免，只能减少；通过好的哈希函数使数据均匀分布；常用方法：开放定址（有冲突时就寻找下一个空的哈希地址）、拉链地址法、、再哈希法（双哈希函数法）、建立一个公共溢出区；
树
树的概念：n个节点互不相交的有限集，只有1个根节点；结点的度（结点拥有的子树数目）、结点关系（孩子结点、双亲结点、兄弟结点）、结点层次（根节点为第一层，依次类推）、树的深度/高度（最大层次）；
二叉树分类：结点度不大于2，左右子树有序不能颠倒；斜树（所有结点只有左子树或右子树）、满二叉树（所有结点都存在左右子树，并且所有叶子都在同一层上）、完全二叉树（结点位置同满二叉树，比满二叉树少几个叶节点，从左向右放子节点）、平衡二叉树（左右子树高度差的绝对值不超过1，并且左右子树也是平衡树）、二叉搜索树BST（所有节点比他的左子节点大，比他的右子节点小）、 红黑树（同时具有搜索树和平衡树的属性）；
二叉树存储：采用数组顺序存储：结点的存储位置就是数组的下标索引，按满二叉树存储，没有结点的位置留空，会浪费空间；链表存储：数据，左右指针；
二叉树遍历：根据根节点遍历顺序区分，左是指递归把所有左结点遍历完再右；前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层次遍历（按层次遍历）；
二叉搜索树：节点查询、构造和删除性能，与树的高度相关，如果能够更平衡则能够显著降低时间复杂度；构造和删除优于线性表，查询性能近似；
B树：平衡多路查找树，相比二叉树有多条搜索路径，数据有序，降低树的高度（将“瘦高”的树变得“矮胖”）；可以显著减少定位记录时所经历的中间过程，从而加快存取速度；用于数据库索引，磁盘存储等；阶：结点最大的子结点数；非叶子节点包括多个数据和指向儿子的指针；所有叶子结点都在同一层次，即具有相同的深度，并且不带信息；
B+树：B树的变体，非叶子节点数据只是索引，不存数据，数据都存储在叶子结点（所有叶子结点的数据组合起来就是完整的数据，B树的数据存储在每一个结点中）；
红黑树：根节点、叶节点下面两个虚无的节点和未填写的节点、红节点的左右子节点是黑的，对于每个节点，从该节点到叶节点的所有路径包含相同数目的黑节点；自平衡通过左旋、右旋、变色实现；
堆：是一棵完全二叉树，大顶堆：树及子树的根节点大于子节点；小顶堆：树及子树的根节点小于子节点；
图
概念：包括顶点（数据节点）和边（连接顶点的线）；无向图（边没有方向性，认为是特殊有向图，2条相反的边）、有向图（边有方向性）；权（边上的数值）；一般通过邻接矩阵实现；连通图（无向图中，任意两个顶点都有路径相通）、强连通图（有向图中，任意两个顶点都有路径相通）、生成树（一个连通子图，包含所有n个顶点和n-1条边）、最小生成树（所有生成树中，所有边的代价和最小）；
线段树
概念：也叫区间树，是一个完全二叉树，在各个节点保存一条线段（即区间）；可以高效地询问和修改一个数列中某个区间的信息，数列中数的个数必须固定才能使用；构造方法：让根节点表示区间[0,N-1]，即所有N个数所组成的一个区间，然后，把区间分成两半，分别由左右子树表示；
树状数组
树状数组：用数组来模拟树形结构，可以解决大部分基于区间上的更新以及求和问题；树状数组可以解决的问题都可以用线段树解决;
并查集
概念：用树来表示集合，树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表；包括合并、查找2个操作；主要用于处理一些不相交集合的合并问题，如求连通子图、求最小生成树的Kruskal算法和求最近公共祖先等；
算法
双指针
快慢指针：主要解决链表中的问题，一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后；应用：判定链表中是否含有环、已知链表中含有环，返回这个环的起始位置、寻找链表的中点（快指针一次进两步，慢指针一次进一步，当快指针到达链表尽头时慢指针就处于链表的中间位置）、寻找链表的倒数第k个元素；
左右指针：主要解决数组字符串问题，在数组中实际是指两个索引值，一般初始化为left = 0, right=nums.length-1；应用：二分查找、反转数组、滑动窗口；
滑动窗口
概念：滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。
递归
概念：自己调用自己，3个步骤：明确函数要做什么、明确递归的结束条件、找到函数的等价关系式；递归可以从上往下，也可以从下往上的写法；应用：斐波那契数列、反转链表；
分治
概念：分而治之，大问题能够拆成相似的小问题，而后将小问题的每个解合成为大问题的解；大问题如何拆，小问题如何合并是关键；
回溯
概念：回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点；回溯法属于深度优先搜索，由于是全局搜索，复杂度相对高；应用：八皇后、01背包、数独；
贪心
概念：在对问题进行求解时，在每一步选择中都采取最好或者最优的选择，从而希望能够导致结果是最好或者最优的算法；贪婪算法所得到的结果往往不是最优的结果，但是都是相对近似最优解的结果；没有固定的算法解决框架，关键是贪婪策略的选择，根据不同的问题选择不同的策略；应用：区间调度、背包；
动态规划
概念：适用问题满足3个性质：最优化原理(问题的最优解所包含的子问题的解也是最优的)、无后效性（状态以后的过程不会影响以前的状态，只与当前状态有关）、有重叠子问题（子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到）；一般步骤：划分问题阶段、确定状态及状态变量、确定状态转移方程、寻找边界条件；
广度优先搜索
概念：广度优先搜索顾名思义就是要广阔，不断通过搜索自己旁边的节点，旁边的节点构成一个队列，只有把自己旁边的节点遍历完之后，才会遍历旁边旁边的节点；
深度优先搜索
概念：深度优先搜索顾名思义就是要有深度，首先把自己存起来，然后随机找一个自己的邻接节点，在以这个邻接节点为起始节点去搜索图中与之相邻的节点，一直搜索下去，递归下去；如果这个点没有邻接点，则返回上一个节点继续这个节点的其他节点搜索；如果这个节点的邻接点都已经搜索完，那么需要返回上一个节点继续搜索；
拓扑排序
概念：是对有向图的顶点排成一个线性序列；拓扑排序序列不一定唯一；规则：每个顶点出现一次，不能成环，顶点的顺序满足图上边指向的顺序；实现：通过每个顶点的出度（该顶点指向其他顶点的边数）入度（其他顶点指向该顶点的边数）实现，从入度为0的顶点开始，不断去掉该顶点再重新计算入度再取出入度为0的顶点实现；
排序算法
概念：内排序（所有排序操作都在内存中完成）、外排序（把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行）；比较排序（元素次序依赖他们之间的比较：快速排序、归并排序、堆排序、冒泡排序）、非比较排序（通过确定每个元素之前，应该有多少个元素来排序：计数排序、基数排序、桶排序）；
冒泡排序：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来；走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成；这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端；复杂度：O(n)~O(n2);
选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕；比较稳定，适用于规模小，不需要额外的内存；复杂度：O(n2);
插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间；复杂度：O(n~O(n2);
希尔排序：是简单插入排序经过改进之后的一个更高效的版本；先按照步长把整个数组分组，对每组使用直接插入排序算法排序，随着步长逐渐减少，每组包含的元素越来越多，当步长减至1时，整个文件恰被分成一组，算法便终止；复杂度：O(nlog2n)；
归并排序：采用分治法，将已有序的子序列合并，得到完全有序的序列（把长度为n的输入序列分成两个长度为n/2的子序列，再分别归并排序，再合并）；复杂度：O(nlogn)；
快速排序：采用分治法，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序（从数组中挑出一个元素作为基准，比他大的和比他小的分为两个部分）；复杂度：O(nlogn)~O(n2);
堆排序：利用堆这种数据结构实现；复杂度：O(logn);
计数排序：使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置（需要先找出待排序的数组中最大和最小的元素）；复杂度：O(n+k);
桶排序：计数排序的升级版，利用了函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（可以递归或用其他排序）；复杂度：O(n+k)~O(n2);
基数排序：对每一位进行排序（如23分2和3两位排序），从最低位开始排序（先取得数组中的最大数，并取得位数），类似桶排序，根据键值的每位数字来分配桶；复杂度：O(nk);
最短路径
概念：从图中某一顶点到达另一顶点的路径可能不止一条，找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小；迪杰斯特拉算法：按路径长度递增的次序一步一步并入来求取，以起始点为中心向外层层拓展（广度优先搜索思想），直到拓展到终点为止，是贪心算法的一个应用；弗洛伊德算法：动态规划算法；
最小生成树
概念：包含所有顶点和n-1条边，且所有边权值最小；克鲁斯卡尔算法：加边法，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里；普利姆算法：加点法，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点；
总结
