常见的数据结构

链表

LinkedHashSet LinkedList 底层数据结构由链表和哈希表组成。
数据的添加和删除都较为方便，就是访问比较耗费时间。

数组

ArrayList 访问数据十分简单，而添加和删除数据比较耗工夫

堆

  • 堆是一种图的树形结构，被用于实现“优先队列",优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出
  • 堆的特点：
    ①堆中的每个结点最多有两个子结点②子结点必定大于父结点③把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端④如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）

 

栈 （LIFO）

队列 (FIFO)

哈希表 HashSet

  • TreeSet底层数据结构是红黑树
  • 哈希函数（Hash）计算key,哈希值除以数组的长度5，求得其余数。这个余数就是key的编号及位置
  • 如果发生哈希冲突，就使用链表进行存储（链地址法）给数组设定合适的空间非常重要
    除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通过多次使用哈希函数或“线性探测法”等方法计算候补地址。

二叉树

  • 特点：
    ①第一个是每个结点的值均大于其左子树上任意一个结点的值②是每个结点的值均小于其右子树上任意一个结点的值③二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。④二叉查找树的最大结点要从顶端开始，往其右下的末端寻找添加数据的时候 与顶端数据比较 如果比他小就往左移，左边没有节点了就把插入的数据作为新节点添加到左下方，大于他则往右移（左小右大）

删除数据的时候 如果节点没有子节点 直接删 如果有一个 删了后子节点补上，如果有两个，删掉后从左子树中中找最大的补上

比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。

常见的算法整理

排序

  • 冒泡排序
    冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”冒泡排序的时间复杂度为O（n2）
  • 选择排序
    选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。
  • 插入排序
    插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上时间复杂度和冒泡排序的一样，都为O（n2）。
  • 堆排序
    首先堆中存储所有的数据，并按降序来构建堆，然后从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。堆排序的时间复杂度为O（nlogn）。
  • 归并排序
    归并排序算***把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。运行时间复杂度为O（nlogn）
  • 快速排序
    快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别。解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。整体的时间复杂度为O（nlogn）。

数组查找

  • 线性查找
    线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为O（n）。
  • 二分查找（略）

图的搜索

  • 广度优先搜索
    广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索
  • 深度优先搜索
    深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。
  • 贝尔曼-福特算法（略）
    贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法
  • 狄克斯特拉算法（略）
  • A*算法（略）

安全算法

  • 共享密钥加密
  • 公开密钥加密
  • 混合加密
  • 迪菲-赫尔曼交换

其他算法

  • k-means 算法
  • 欧几里得算法
  • 素性测试
  • 网页排名
  • 汉诺塔

【拓展】

  1. 图的表示：邻接矩阵和邻接表
    遍历算法：深度搜索和广度搜索(必学)最短路径算法：Floyd，Dijkstra（必学）最小生成树算法：Prim，Kruskal（必学）实际常用算法：关键路径、拓扑排序（原理与应用）二分图匹配：配对、匈牙利算法（原理与应用）拓展：中心性算法、社区发现算法（原理与应用）

2.图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。

3、搜索与回溯算法

贪心算法（必学）
启发式搜索算法：A*寻路算法（了解）
地图着色算法、N 皇后问题、最优加工顺序
旅行商问题

这方便的知识都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。

4、动态规划

树形DP：01背包问题
线性DP：最长公共子序列、最长公共子串
区间DP：矩阵最大值（和以及积）
数位DP：数字游戏
状态压缩DP：旅行商

我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，在leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的***多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。

5、字符匹配算法

正则表达式
模式匹配：KMP、Boyer-Moore

6、流相关算法

最大流：最短增广路、Dinic 算法
最大流最小割：最大收益问题、方格取数问题
最小费用最大流：最小费用路、消遣

作者：爱吃早餐的程序员

原文链接：https://my.oschina.net/u/4847277/blog/4740287?_from=gitee_search

如果觉得本文对你有帮助，可以点赞关注支持一下，也可以点进我主页关注我公众号，上面有更多技术干货文章以及相关资料共享，大家一起学习进步！