数据结构&算法

数据结构面试整理

主要是对常规数据结构的整理，需要补充红黑树、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，只有一种情况了：

因为B-树需要保证根节点到每个子节点的长度一致，保证最短的树高，因此会出现下面的转换

将左边的中间提到跟节点去，这时候保证划分出来的三个数据段都是以根节点的23和40作为分界点划分出来的。

上述的插入情况是相对直观的，下面的删除操作可能有几种情况：

  • 叶子结点如果删除之后节点数量还是大于等于m/2，就直接删除即可

  • 叶子结点如果删除之后节点数量小于m/2，就需要向兄弟节点借一个节点，通过公有的父节点来完成（其实B树就像是一个数据流，从左子树到根节点到右子树，如果此时左子树元素不够用的，将根节点元素挪到左子树，右子树挪一个元素顶替根节点即可）

  • 非叶子节点删除是从右子树中挪动一个节点过去，然后再经过上述思想就行调整树大小

这是B树的数据结构，也叫B-树，下面介绍B+树

与B-树的结构非常类似，如根节点的元素个数为[1, m - 1]，非根节点的元素个数为[m / 2, m - 1]，不同点是非叶子节点仅仅只存放右子树的第一个元素的索引，因此也被称为 内部节点或者是索引节点，

感觉之所以要使用B+树就是因为在删除操作的时候仅仅涉及到兄弟元素的移动，然后对父节点直接进行修改，不用像是用B树一样去借一个父节点的元素了。

B+树较之于B树，MySQL之所以选择B+树作为索引的数据结构，主要是所有数据都存放在叶子结点上，数据更加集中，而不是像B树那样数据可以存放在非叶子节点上，这样可以更加好的利用CPU的缓存机制来减少磁盘的读写量

布隆过滤器，可以看成是数组和哈希函数两部分组成的数据结构，占用空间非常小，但是存在一个问题：可能产生误报，且随着元素增多，误报的几率越大

如果申请100 00000个大小的数组也才占用122kb的空间。

增加过程【需要注意多个哈希函数的处理】：

1、加入元素的时候，通过多个哈希函数算出多个哈希值

2、将每个哈希值的位置置1

删除过程：

1、给定元素进行多次哈希运算

2、判断数组中是否所有的位数都为1，如果都是1说明存在

如果返回元素存在，可能是误判，如果返回某个元素不存在，那么一定是正确地

使用场景：防止Redis缓存击穿

布隆过滤器在很多地方存在运用，如Guava对他进行了默认实现

自从Redis4.0开始支持插件，布隆过滤器RedisBloom就存在其中

跳表

SkipList，主要是对链表插入效率的一个补充

如果当前链表是排好序了的，然后插入数据之后还是要保证有序，那么此时就出现问题了，查找到插入点的效率是O（N），非常低。

优化思路：将链表中的一半节点作为关键节点抽出作为索引，从而减少比较次数，存储空间多了一半，但是效率也增加了一半【类似于MySQL的索引】

此时进一步优化，建立索引之上的索引，如图

如此的递归下去，当只有两个节点的时候停止，这样的数据结构就是跳跃表

但是随着数据的插入，会发现上层索引的关键性越来越小，此时需要在新增节点中提拔一些节点来增加关键性，是否提拔节点使用抛硬币的方式进行（50几率称为1级索引，然后又有50几率称为二级索引直到最高级）。

大部分时间复杂度降低为O（logN），但是占据空间为2N，空间复杂度为O（N）

删除节点则更好操作，如果有索引则删除索引即可。

算法面试常见问题

总结几道解题思路，题还没刷完

字符串类：

最长公共前缀

1、排序，比较第一个和最后一个

2、找一个为基准，不断进行比较得出长度

最长回文

动态规划了，长度为123都可以直接得出，长度为4之后开始

dp[i][j]={truej−i==0∣1array[i]==array[j]j−i<=3(array[i]==array[j]) & dp[i+1][j−1]otherwisedp[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直接连接上另一边，最后要加上进位信息

链表翻转，使用递归来做

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个节点

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的元素，也可以转换

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

使用二分幂来进行优化，主要是

an={1n==0an==1an/2∗an/2a&1==0a(n−1)/2∗a(n−1)/2∗aa&1==1a^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

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

上一页面试下一页面试

最后更新于