> For the complete documentation index, see [llms.txt](https://luckycurvec.gitbook.io/java-knowledge-architecture/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luckycurvec.gitbook.io/java-knowledge-architecture/mian-shi-11/shu-ju-jie-gou-suan-fa.md).

# 数据结构&算法

## 数据结构面试整理

主要是对常规数据结构的整理，需要补充红黑树、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/布隆过滤器-hash运算.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

…. 依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luckycurvec.gitbook.io/java-knowledge-architecture/mian-shi-11/shu-ju-jie-gou-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.