# 数据结构&算法 ## 数据结构面试整理 主要是对常规数据结构的整理，需要补充红黑树、B+树、布隆过滤器、跳表 数组：使用一块连续的内存空间来存储，提供随机访问特性 链表：从属于线性表，但是离散的存储在内存空间当中的，在插入和删除操作上的复杂度为O（1），但是在查找节点或者访问指定位置的复杂度为O（n），对比数组，可以更充分的利用计算机的内存资源，但是空间利用率较低 可以通过节点之间持有的引用关系分为：单链表、循环链表（在单链表的基础上加上了last——>head）、双向链表（持有前后节点的引用）、双向循环链表（在双向链表的基础上连接了首尾）、 数组和链表的对比： 1、数组支持随机访问 2、数组对CPU的缓存机制更有好 3、如果有频繁的增删操作，数组可能需要扩容（通过复制数据的方式），但链表对频繁的增删天然友好 栈：具有LIFO的特性，在栈顶，支持pop操作和push操作，此外还有peek返回栈顶元素不出栈，只支持对栈顶的操作 > 可以用于解决括号匹配问题，字符串反转问题 Java中的栈是使用Vector实现的，amazing\~ 队列：具有FIFO特性，只允许从队尾入队，从队头出队，主要也有几种实现：单队列、循环队列 因为单队列会出现front前面无法利用的问题，因此引入了循环队列 > 实现有阻塞队列、运用于生产者消费者模型，线程池中的任务队列。 红黑树：算是对平衡二叉树的一种优化，平衡二叉树在极端情况下的时间复杂度为O（N）（所有节点都存放于右子树上，这样就退化成了链表）。为了解决这个问题，提出了红黑树的概念来进行改进，在每次进行增加节点和删除节点的时候都会进行树的一次平衡。 B+树：在数据库索引大量使用到了B树（也叫B-树）和B+树的数据结构 先记录B-树，在使用B-树时候需要给定阶数m，如5阶的B树 B树需要保证如下几条规则： 根节点的关键字数量（存储元素的个数）范围是：`[1, m - 1]` 非根节点的关键字数量范围是：`[m / 2, m - 1]` 节点中的关键字需要按顺序排列，每个关键字的左子树的所有关键字都小于他，右子树的所有关键字都大于它 如一个五阶的B树的插入：18、70、50、40、22、23、25、39 当插入到22的时候发现根节点大于m-1了，此时需要分裂，因为需要保证非根节点的数量至少为2，只有一种情况了： ![img](https://segmentfault.com/img/remote/1460000020416581) ![img](https://segmentfault.com/img/remote/1460000020416582) 因为B-树需要保证根节点到每个子节点的长度一致，保证最短的树高，因此会出现下面的转换 ![img](https://segmentfault.com/img/remote/1460000020416584) ![img](https://segmentfault.com/img/remote/1460000020416585) 将左边的中间提到跟节点去，这时候保证划分出来的三个数据段都是以根节点的23和40作为分界点划分出来的。 上述的插入情况是相对直观的，下面的删除操作可能有几种情况： * 叶子结点如果删除之后节点数量还是大于等于m/2，就直接删除即可 * 叶子结点如果删除之后节点数量小于m/2，就需要向兄弟节点借一个节点，通过公有的父节点来完成（其实B树就像是一个数据流，从左子树到根节点到右子树，如果此时左子树元素不够用的，将根节点元素挪到左子树，右子树挪一个元素顶替根节点即可） * 非叶子节点删除是从右子树中挪动一个节点过去，然后再经过上述思想就行调整树大小 这是B树的数据结构，也叫B-树，下面介绍B+树 与B-树的结构非常类似，如根节点的元素个数为`[1, m - 1]`，非根节点的元素个数为`[m / 2, m - 1]`，不同点是非叶子节点仅仅只存放右子树的第一个元素的索引，因此也被称为 内部节点或者是索引节点， ![img](https://segmentfault.com/img/remote/1460000020416599) 感觉之所以要使用B+树就是因为在删除操作的时候仅仅涉及到兄弟元素的移动，然后对父节点直接进行修改，不用像是用B树一样去借一个父节点的元素了。 B+树较之于B树，MySQL之所以选择B+树作为索引的数据结构，主要是所有数据都存放在叶子结点上，数据更加集中，而不是像B树那样数据可以存放在非叶子节点上，这样可以更加好的利用CPU的缓存机制来减少磁盘的读写量 布隆过滤器，可以看成是数组和哈希函数两部分组成的数据结构，占用空间非常小，但是存在一个问题：可能产生误报，且随着元素增多，误报的几率越大 如果申请100 00000个大小的数组也才占用122kb的空间。 增加过程【需要注意多个哈希函数的处理】： 1、加入元素的时候，通过多个哈希函数算出多个哈希值 2、将每个哈希值的位置置1 删除过程： 1、给定元素进行多次哈希运算 2、判断数组中是否所有的位数都为1，如果都是1说明存在 ![布隆过滤器hash计算](https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-11/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8-hash%E8%BF%90%E7%AE%97.png) > 如果返回元素存在，可能是误判，如果返回某个元素不存在，那么一定是正确地 使用场景：防止Redis缓存击穿 布隆过滤器在很多地方存在运用，如Guava对他进行了默认实现 自从Redis4.0开始支持插件，布隆过滤器RedisBloom就存在其中 跳表 SkipList，主要是对链表插入效率的一个补充 如果当前链表是排好序了的，然后插入数据之后还是要保证有序，那么此时就出现问题了，查找到插入点的效率是O（N），非常低。 优化思路：将链表中的一半节点作为关键节点抽出作为索引，从而减少比较次数，存储空间多了一半，但是效率也增加了一半【类似于MySQL的索引】 ![image-20210224153159847](https://gitee.com/LuckyCurve/img/raw/master/img/image-20210224153159847.png) 此时进一步优化，建立索引之上的索引，如图 ![image-20210224153234784](https://gitee.com/LuckyCurve/img/raw/master/img/image-20210224153234784.png) 如此的递归下去，当只有两个节点的时候停止，这样的数据结构就是跳跃表 但是随着数据的插入，会发现上层索引的关键性越来越小，此时需要在新增节点中提拔一些节点来增加关键性，是否提拔节点使用抛硬币的方式进行（50几率称为1级索引，然后又有50几率称为二级索引直到最高级）。 大部分时间复杂度降低为O（logN），但是占据空间为2N，空间复杂度为O（N） 删除节点则更好操作，如果有索引则删除索引即可。 ## 算法面试常见问题 总结几道解题思路，题还没刷完 ### 字符串类： 最长公共前缀 1、排序，比较第一个和最后一个 2、找一个为基准，不断进行比较得出长度 最长回文 动态规划了，长度为123都可以直接得出，长度为4之后开始 $$ dp\[i]\[j] = \begin{cases} true & j-i == 0 | 1\\ array\[i] == array\[j] & j-i<=3\\ (array\[i] == array\[j])\ &\ dp\[i+1]\[j-1] \&otherwise \end{cases} $$ 括号是否匹配&括号匹配深度 判断是否匹配，使用栈，进栈出栈操作，然后判断栈是否为空 判断深度，碰到左括号+1，右括号-1，遍历整个字符串获取最大值 自己实现String转Integer 主要注意越界问题，其他都还好，如果有符号，则直接在每一步上都乘上符号 ### 链表类： 两数相加，链表逆序存储 注意点：进位，当一边为null直接连接上另一边，最后要加上进位信息 链表翻转，使用递归来做 ```java public ListNode reverse(ListNode node) { if (node == null || node.next == null) { return node; } ListNode last = reverse(node.next); node.next.next = node; node.next = null; return last; } ``` 如果是翻转前N个节点 ```java private ListNode next; public ListNode reverse(ListNode head, int n) { if (n == 1) { next = head.next; return head; } ListNode last = reverse(head.next, n - 1); head.next.next = head; head.next = next; return last; } ``` 如果是翻转m到n的元素，也可以转换 ```java public ListNode reverseBetween(ListNode head, int m, int n) { if (m == 1) { return reverse(head, n); } else { head.next = reverseBetween(head.next, m - 1, n - 1); return head; } } ListNode next; public ListNode reverse(ListNode head, int n) { if (n == 1) { next = head.next; return head; } ListNode last = reverse(head.next, n - 1); head.next.next = head; head.next = next; return next; } ``` 求倒数第k个节点 倒数第k个节点和最后一个节点相隔k-1。维持fast和slow，fast先跑到k，然后fast和node同步跑，如果fast为null，则slow的位置即为倒数第k个节点 删除倒数第n个节点 使用上述方法找到第n+1个节点即可 剑指offer上的题目 斐波那契数列 用递归肯定能解出来，但是慢 思路：使用pre指向前一个元素，cur指向当前元素，从3开始，前面的012自己判断，最后返回cur，变换思路为temp=pre pre = cur cur = temp + cur 跳台阶问题 每次跳1或者2，问到终点多少种跳法，递归：`i = (i - 1) + (i - 2)`，递归出口(1) = 1 (2) = 2，别写(0) = 1和(1) = 1了，要多执行好多遍 变态跳台阶 求n阶跳法，可以从1一直跳到n (n) = (n - 1) + (n - 2) + ...... + 1 (n - 1) = (n - 2) + ...... + 1 (n) = 2 (n - 1) = 4(n - 2) = 2的n-1次方的(1) (1) = 1，结果为2的n-1次方 求double的n次方 可以直接累乘，复杂度为On 使用二分幂来进行优化，主要是 $$ a^n = \begin{cases} 1 && n == 0 \\ a && n == 1 \\ a ^ {n/2} \* a ^ {n/2} && a & 1 == 0 \\ a ^ {(n-1)/2} \* a ^ {(n-1)/2} \* a && a & 1 == 1 \\ \end{cases} $$ 时间复杂度降低为Ologn 将奇数与偶数分离，保持相对位置不变 创建一个等大数组，用于奇偶存放，最后再进行同步 两个栈实现队列 非常简单，一个栈存放正序，一个栈存放反序 同步使用for-each，都是从低到顶，然后使用Collections.reverse方法进行翻转 给定栈的入栈和出栈元素顺序，判断是否匹配 思路： 入栈1,2,3,4,5 出栈4,5,3,2,1 首先1入辅助栈，此时栈顶1≠4，继续入栈2 此时栈顶2≠4，继续入栈3 此时栈顶3≠4，继续入栈4 此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3 此时栈顶3≠5，继续入栈5 此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3 …. 依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。