数据结构2

文章目录

• 1.什么是算法？
• 2.TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？
• 3.如何知道二叉树的深度？
• 4.介绍一下，堆排序的原理是什么？
• 5.数组和链表的区别
• 6.二分查找了解过吗？
• • 查找思路
  • 算法实现
  • 7.说下你熟悉的排序算法
  • 8.布隆过滤器了解过吗？
  • 9.一致性hash算法了解过吗？
  • 10.如何在一个1到100的整数数组中找到丢失的数字?
  • 11.请你讲讲LRU算法的实现原理？
  • 12.为什么要设计后缀表达式，有什么好处？
  • 13. 什么是B树?
  • 14.什么是B+树?
  • 15.谈一谈，id全局唯一且自增，如何实现？
  • 参考链接
  
  

算法简单来说就是解决问题的步骤。

在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。

一、算法的五个特征

①、有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。

②、确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

③、可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

④、有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

⑤、有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。

二、算法的设计原则

①、正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：

一、程序语法错误。

二、程序对于几组输入数据能够得出满足需要的结果。

三、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。

四、程序对于一切合法的输入数据都能得到满足要求的结果。

PS：通常以第 三 层意义的正确性作为衡量一个算法是否合格的标准。

②、可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。

③、健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

④、高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

前面三点 正确性，可读性和健壮性相信都好理解。对于第四点算法的执行效率和存储量，我们知道比较算法的时候，可能会说“A算法比B算法快两倍”之类的话，但实际上这种说法没有任何意义。因为当数据项个数发生变化时，A算法和B算法的效率比例也会发生变化，比如数据项增加了50%，可能A算法比B算法快三倍，但是如果数据项减少了50%，可能A算法和B算法速度一样。所以描述算法的速度必须要和数据项的个数联系起来。也就是“大O”表示法，它是一种算法复杂度的相对表示方式，这里我简单介绍一下，后面会根据具体的算法来描述。

相对(relative)：你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较2个算法所做的算术操作（一个做乘法，一个做加法）将会告诉你一些有意义的东西；

表示(representation)：大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如，排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式；

复杂度(complexity)：如果排序10,000个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。

然后我们在说说算法的存储量，包括：

程序本身所占空间；

输入数据所占空间；

辅助变量所占空间；

一个算法的效率越高越好，而存储量是越低越好。

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

实现二叉树的深度方式有两种，递归以及非递归。

①递归实现：

为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；

②非递归实现：

利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。

树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。

（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

1、数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

2、链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

查找思路

【a】待查找有序数组序列：1, 2, 3, 4, 5, 6, 7

起始： 定义start = 0 , end = 6, mid = (start + end ) / 2 = (0 + 6) / 2 = 3,arr[mid] = arr[3] = 4

【b】假设需要查找"2", 因为2

此时重新计算mid = (start +end ) / 2 = (0 + 2) / 2 = 1; arr[mid] = arr[1] = 2 ,继续将2与arr[mid] = arr[1] = 2进行比较，发现相等，成功找到数字"2"所在的位置。

【c】假设需要查找"7"，因为 7 > arr[mid] = arr[3] = 4,所以需要将start移动到mid右边一个位置，即start = mid + 1 = 4,此时重新计算mid = (start +end) / 2 = (4+ 6)/2 = 5, arr[mid] = arr[5] = 6, 因为7>arr[mid] = arr[5] = 6,所以还是需要将start移动到mid右边一个位置，即start = mid + 1 = 5 + 1 = 6, 此时重新计算mid = (start +end) / 2 = (6 + 6) / 2 = 6.arr[6] = 7, 此时arr[mid] = arr[6] = 7,刚好等于待查找数字7，说明成功找到数字"7"所在的位置.

【d】假设查找"0", 因为 0 end，即start 已经大于end结束位置，说明没有找到相应的元素0。

算法实现

public class BinarySearchUtils {

/**
* 根据指定值查找在数组中的位置
*
* @param arr 待查找有序数组
* @param value 指定值
* @return 返回值在数组中对应的下标位置
*/
public static int binarySearch(int[] arr, int value) {
//起始位置
int start = 0;
//结束位置
int end = arr.length - 1;

while (true) {
//计算中间位置下标
int mid = (start + end) / 2;
//中间值
int midValue = arr[mid];

if (value == midValue) {
return mid;
} else {
//待查找数值比中间值小,需要将end = mid - 1
if (midValue > value) {
end = mid - 1;
} else {
//待查找数值比中间值大,需要将start = mid + 1
start = mid + 1;
}
}

if (start > end) {
//start > end,说明未找到相应的元素,返回-1
return -1;
}
}
}

}


7.说下你熟悉的排序算法

详见：https://www.cnblogs.com/onepixel/articles/7674659.html

8.布隆过滤器了解过吗？

详见：https://www.cnblogs.com/liyulong1982/p/6013002.html

9.一致性hash算法了解过吗？

详见：https://mp.weixin.qq.com/s/bCH-aU8cKS3uT6PwRYNJtA

10.如何在一个1到100的整数数组中找到丢失的数字?

如果是丢了一个数字，用个遍历把这些数字累加求和，

然后用 （1 + 100）*100/2 减去这个累加的总和，就是少的那一个数.

如果是丢了一些数字，

方法一：

先 1-100 遍历 创建一个字典，key为1-100，值默认都为NO。

然后把那一些数字作为一个数组，判断是否包含每一个key，包含那key，则那key的值改为YES，

最后值为NO的数则为缺失的数字

方法二：

先排序,并创建一个用来装缺失数的空数组，排好序后遍历,最大的数用101减，其余用后一个值减去前一个值如果差值不是1而是为n，就把被减数分别加1到（n-1）得出的数保存下来就是缺少的数字

11.请你讲讲LRU算法的实现原理？

①LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，为虚拟页式存储管理服务。

②达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。 为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到 。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。

12.为什么要设计后缀表达式，有什么好处？

后缀表达式又叫逆波兰表达式，逆波兰记法不需要括号来标识操作符的优先级。

13. 什么是B树?

B树是一种多叉树，也叫多路搜索树，适合用于文件索引上，减少磁盘IO次数，子节点存储最大数成为B树的阶，图中为2-3树。

m阶B树特点：

非叶节点最多有m棵子树。
根节点最少有两棵子树，非根非叶节点最少有m/2棵子树。
非叶节点保存的关键字个数等于该节点子树个数-1。
非叶节点保存的关键字大小有序。
节点中每个关键字左子树的关键字都小于该该关键字，右子树的关键字都大于该该关键字。
所有叶节点都在同一层。
查找：

对节点关键字进行二分查找。
如果找不到，进入对应的子树进行二分查找，如此循环。

14.什么是B+树?

B树的变种，拥有B树的特点

独有特点：

节点中的关键字与子树数目相同。
关键字对应的子树节点都大于等于该关键字，子树包含该关键字自身。
所有关键字都出现在叶节点之中。
所有叶节点都有指向下一个叶节点的指针。
搜索：只在叶节点搜索。

叶子节点保存关键字和对应的数据，非叶节点只保存关键字和指向叶节点的指针，同等关键字数量的B树和B+树，B+树更小。

更适合做索引系统，原因：

由于叶节点有指针项链，B+树更适合做范围检索。
由于非叶节点只保存关键字和指向叶节点的指针，B+树可以容纳更多的关键字，树层数变小，磁盘查询次数更低。
B+树的查询效率比较稳定，查询所有关键字的路径相同。（MySQL索引就提供了B+树的实现方式）

15.谈一谈，id全局唯一且自增，如何实现？

SnowFlake雪花算法

雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：

snowflake id生成规则

1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。

41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。

10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。

12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

参考链接

https://zhuanlan.zhihu.com/p/150340528?from_voters_page=true

https://blog.csdn.net/Mr_BJL/article/details/88073694

https://blog.csdn.net/chenshiyang0806/article/details/90744039

https://blog.csdn.net/Weixiaohuai/article/details/83188174