java数据结构与算法第50讲（Java程序员必会之数据结构与算法全梳理）

java数据结构与算法第50讲（Java程序员必会之数据结构与算法全梳理）4、动态规划贪心算法（必学） 启发式搜索算法：A*寻路算法（了解） 地图着色算法、N 皇后问题、最优加工顺序 旅行商问题 这方便的知识都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。【拓展】2.图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。3、搜索与回溯算法

常见的数据结构链表

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

如果觉得本文对你有帮助，可以转发关注支持一下