Skip to content

Latest commit

 

History

History
676 lines (458 loc) · 38.7 KB

data.md

File metadata and controls

676 lines (458 loc) · 38.7 KB

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii# 树

1、红黑树和AVL树的定义，特点，以及二者区别

平衡二叉树（AVL树）：

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

红黑树：

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。

性质：

  1. 每个节点非红即黑
  2. 根节点是黑的;
  3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
  4. 如果一个节点是红色的，则它的子节点必须是黑色的。
  5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

区别：

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

2、请你说一下哈夫曼编码

哈夫曼编码是哈夫曼树的一种应用，广泛用于数据文件压缩。哈夫曼编码算法用字符在文件中出现的频率来建立使用0，1表示个字符的最优表示方式，其具体算法如下：

(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

(2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

(3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

3、请你介绍一下B+树

B+是一种多路搜索树，主要为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，每个节点的可以有多个孩子，并且按照关键字大小有序排列。所有记录节点都是按照键值的大小顺序存放在同一层的叶节点中。相比B树，其具有以下几个特点：

每个节点上的指针上限为2d而不是2d+1（d为节点的出度）

内节点不存储data,只存储key

叶子节点不存储指针

4、请你说一说map和unordered_map的底层实现

map底层是基于红黑树实现的，因此map内部元素排列是有序的。而unordered_map底层则是基于哈希表实现的，因此其元素的排列顺序是杂乱无序的。

对于map，其底层是基于红黑树实现的，优点如下：1)有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

2)map的查找、删除、增加等一系列操作时间复杂度稳定，都为logn

缺点如下：

1）查找、删除、增加等操作平均时间复杂度较慢，与n相关

对于unordered_map来说，其底层是一个哈希表，优点如下：

查找、删除、添加的速度快，时间复杂度为常数级O(c)

缺点如下：

因为unordered_map内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高

Unordered_map的查找、删除、添加的时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)

5、请你回答一下epoll怎么实现的

Linux epoll机制是通过红黑树和双向链表实现的。 首先通过epoll_create()系统调用在内核中创建一个eventpoll类型的句柄，其中包括红黑树根节点和双向链表头节点。然后通过epoll_ctl()系统调用，向epoll对象的红黑树结构中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。最后通过epoll_wait()系统调用判断双向链表是否为空，如果为空则阻塞。当文件描述符状态改变，fd上的回调函数被调用，该函数将fd加入到双向链表中，此时epoll_wait函数被唤醒，返回就绪好的事件。

6、请你说一说Top(K)问题

1、直接全部排序（只适用于内存够的情况）当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。

这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出top K个数据，所以该方法并不十分高效，不建议使用。

2、快速排序的变形 （只使用于内存够的情况）

这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。

这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index > K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回Top K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。

3、最小堆法

这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。

4、分治法

将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下NK个数据，如果内存不能容纳NK个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。

5、Hash法

如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。

7、简述什么是前缀树 ？

前缀树（Trie），又称字典树或键树，是一种用于快速检索的树形数据结构。它特别适用于处理字符串集合，以实现快速的字符串检索、前缀匹配、词频统计等操作。前缀树的核心思想是利用字符串集合中的公共前缀来减少查询时间，从而达到比线性查找或其他简单查找方法更高的效率。

特点

  • 每个节点代表一个字符串（或字符串的一部分），根节点代表空字符串。
  • 从根节点到某一节点的路径，连起来，就是该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

应用

  • 自动补全：输入法软件中，根据用户已输入的部分字符，快速找到可能的完整单词或句子。
  • 拼写检查：快速查找单词是否存在于字典中，以检查拼写错误。
  • 词频统计：统计和排序大量文本中单词的出现频率。
  • IP路由匹配：在网络路由中，快速匹配IP地址的最长前缀。
  • 字符串查找：快速检索特定前缀的所有字符串。

优点

  • 高效的字符串检索：可以在O(m)时间内完成搜索，其中m是待查找字符串的长度。
  • 空间优化：共享公共前缀的字符串不需要重复存储，减少了空间需求。

缺点

  • 空间消耗：尽管前缀树减少了重复前缀的存储，但是在存储大量短字符串或字符集很大的情况下，前缀树仍可能占用大量内存。
  • 依赖于字符串长度：对于非常长的字符串，构建和查询前缀树的时间也会增加。

8、什么是平衡二叉树？

平衡二叉树是一种特殊的二叉搜索（排序）树（BST），它在普通的二叉搜索树的基础上增加了一个条件：树中任何节点的两个子树的高度差都不超过1。这个条件帮助保证了树的深度在最坏情况下仍保持对数级别，从而保证了操作（如查找、插入、删除等）的时间复杂度在最坏情况下也是O(log n)，其中n是树中节点的数量。平衡二叉树的这个特性使得它在需要维持数据有序且同时需要高效操作的场景中非常有用。

类型

  • AVL树：最早被发明的自平衡二叉搜索树，严格保持左右子树的高度差不超过1。插入和删除操作可能需要通过旋转操作来重新平衡树。
  • 红黑树：一种稍微宽松的平衡二叉树，通过确保树中不存在连续的红节点并且从根到叶子的所有路径上黑节点的数量相同，来近似平衡。红黑树在插入和删除操作后更容易维持平衡。
  • B树和B+树：虽然严格来说不是二叉树，但它们是为磁盘存储设计的平衡树结构，可以拥有多于两个子节点。B树和B+树广泛应用于数据库和文件系统。
  • Treap（树堆）和Splay树：其他类型的平衡二叉搜索树，通过随机化或者操作访问模式来维持树的平衡。

9、简述什么是B-tree、B+tree多叉树 ？

B树（B-tree）和B+树（B+-tree）是用于存储和管理大量数据的多叉（或多路）平衡查找树。它们特别设计用于有效地在磁盘等辅助存储设备上进行读写操作，广泛应用于数据库和文件系统中。这两种类型的树通过保持数据结构的平衡来确保操作的高效性，即使在包含大量节点的情况下也能保持良好的搜索性能。

B树：B树是一种自平衡的树，具有以下特性：

  • 树中每个节点最多包含(m)个子节点，其中(m)是树的阶。
  • 除根节点和叶子节点外，每个节点至少有(\lceil m/2 \rceil)个子节点。
  • 根节点至少有两个子节点（如果它不是叶子节点）。
  • 所有的叶子节点都位于同一层。
  • 节点中的键（数据项）以有序方式排列，节点内部的键分割子节点的范围。

B+树：B+树是B树的变种，具有B树的所有特性，并包括以下额外特性：

  • 树的叶子节点包含了所有键值信息，以及指向记录的指针，而非叶子节点只存储键值作为索引信息，不包含实际的数据记录。
  • 叶子节点之间按键值顺序通过指针连接，形成一个链表，便于范围查询。
  • 非叶节点的键值也会在子节点中重复出现，这使得B+树在找到路标信息后能更快地定位到实际数据。

B树和B+树的应用

  • 数据库索引：B树和B+树是许多类型数据库系统中索引结构的基础，因为它们能够高效地管理大量数据，支持快速的插入、删除和查找操作。
  • 文件系统：文件系统中的目录结构常用B树或B+树来组织，以优化文件的存取和搜索速度。

B树和B+树的比较

  • 搜索性能：B+树提供了更快的查找速度，因为所有实际数据都在叶子节点上并且叶子节点形成一个有序链表，便于快速顺序访问。
  • 空间利用率：B+树的非叶子节点不存储数据记录，仅作索引用，这样同样大小的节点可以存更多的键，使得树的高度更低，减少了磁盘I/O操作。
  • 范围查询：由于B+树的叶子节点形成了有序链表，使得B+树在进行范围查询时比B树更加高效。



堆、栈、队列

1、请说一说你理解的stack overflow，并举个简单例子导致栈溢出

栈溢出概念：栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。

栈溢出的原因：

  1. 局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。局部变量是存储在栈中的，因此这个很好理解。解决这类问题的办法有两个，一是增大栈空间,二是改用动态分配，使用堆（heap）而不是栈（stack）。
  2. 递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导致堆栈溢出。
  3. 指针或数组越界。这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。

栈溢出例子：

#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[]) {
    char buf[256];
    strcpy(buf,argv[1]);
    printf("Input:%s\n",buf);
    return 0;
}

上述代码中的strcpy(buf,argv[1]);这一行发生了缓冲区溢出错误，因为源缓冲区内容是用户输入的。

2、请你回答一下栈和堆的区别，以及为什么栈要快

堆和栈的区别：堆是由低地址向高地址扩展；栈是由高地址向低地址扩展

堆中的内存需要手动申请和手动释放；栈中内存是由OS自动申请和自动释放，存放着参数、局部变量等内存

堆中频繁调用malloc和free,会产生内存碎片，降低程序效率；而栈由于其先进后出的特性，不会产生内存碎片

堆的分配效率较低，而栈的分配效率较高

栈的效率高的原因：

栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的寄存器存储栈的地址，压栈和入栈有专门的指令执行；而堆是由C/C++函数库提供的，机制复杂，需要一些列分配内存、合并内存和释放内存的算法，因此效率较低。

3、手写代码：两个栈实现一个队列

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        if(stack2.size()!=0){
            int tmp = stack2.top();
            stack2.pop();
            return tmp;
        }
        else{
            while(stack1.size()!=0){
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        	return pop();
    	}
    }
}

private:
    stack<int> stack1;
    stack<int> stack2;
 }；

4、请你说一说小根堆特点

堆是一棵完全二叉树（如果一共有h层，那么1~h-1层均满，在h层可能会连续缺失若干个右叶子）。

1）小根堆

若根节点存在左子女则根节点的值小于左子女的值；若根节点存在右子女则根节点的值小于右子女的值。

2）大根堆

若根节点存在左子女则根节点的值大于左子女的值；若根节点存在右子女则根节点的值大于右子女的值。

5、说一说栈有哪些应用场景？

  1. 程序调用栈 在大多数编程语言中，函数（或方法）调用时使用栈来保存执行上下文，这包括返回地址、参数、局部变量等。当一个函数调用另一个函数时，后者的执行上下文被推入栈中，函数执行结束后，上下文被弹出，控制权返回到调用者。

  2. 表达式求值 栈用于算术表达式的求值，尤其是处理复杂表达式（包括前缀、中缀、后缀表达式）时。通过使用栈，可以方便地对表达式进行解析、运算符的优先级处理和计算。

  3. 括号匹配 在编译器的语法分析阶段，栈经常用来检查源代码中的括号（包括圆括号、方括号和花括号）是否正确匹配。每次遇到开括号时，将其推入栈中；遇到闭括号时，检查并弹出栈顶的开括号，以验证匹配。

  4. 页面访问历史 在浏览器中，后退按钮的实现就是一个典型的栈应用场景。访问的每个页面都按访问顺序被推入栈中，点击后退按钮时就从栈中弹出当前页面，从而访问上一个页面。

  5. 逆序字符串 栈可以用于字符串的逆序。将字符串中的每个字符依次推入栈中，然后再依次弹出，就可以得到逆序后的字符串。

  6. 深度优先搜索（DFS） 在图和树的遍历中，深度优先搜索算法使用栈来记录访问路径。这种方法可以有效地遍历所有节点，尤其是在处理图结构时，栈帮助记录已访问的顶点，以避免重复访问。

  7. 递归实现的非递归化 某些递归算法可以通过使用栈的数据结构转换为非递归形式，通过手动管理栈来模拟递归调用的过程。

  8. 语法解析 在编译技术中，栈用于语法解析和语法树的构建，特别是在处理具有层级结构的语言构造时。

6、栈的内存是怎么分配的 ？

栈的内存分配方式既可以是静态的（如基于数组的实现，预先分配固定大小的内存），也可以是动态的（如基于链表的实现，按需分配内存）。而对于程序的执行栈，其内存通常是由操作系统在程序启动时自动分配的固定大小空间，专门用于处理函数调用的上下文。

7、简述队列的使用场景 ？

计算机科学和软件开发

  • 操作系统：在多线程和进程管理中，队列用于调度任务和管理进程的执行顺序。
  • 网络请求处理：服务器使用队列管理并发请求，保证按照请求到达的顺序进行处理。
  • 打印任务：打印机使用队列来管理打印任务，确保按提交顺序打印文档。
  • 数据流处理：在数据流应用中，队列用于缓冲和顺序处理数据块，如视频流数据包的顺序播放。
  • 异步编程：在异步编程模型中，队列用于管理执行任务和消息传递，确保任务按顺序执行。

算法

  • 广度优先搜索（BFS）：在图和树的搜索算法中，队列用于存储待访问的节点，保证按层次顺序访问。
  • 缓存实现：在某些缓存策略中，队列用于记录访问顺序，帮助实现最少使用（LRU）等缓存淘汰策略。

系统设计

  • 消息队列系统：在分布式系统中，消息队列是一种核心组件，用于异步处理和传输数据，解耦系统组件。
  • 事件驱动编程：在事件驱动的系统中，队列用于存储和管理事件，按照事件发生的顺序处理。

实际应用

  • 顾客服务：在银行、售票窗口等场所，队列用于管理顾客等待服务的顺序。
  • 呼叫中心：管理来电，确保客户的电话咨询按照到达顺序被处理。
  • 物流与供应链：在生产线和物流中，队列用于顺序安排作业任务或货物处理。

8、说一说堆有哪些应用场景？

  1. 优先队列 最直接的应用是实现优先队列。优先队列是一种特殊的队列，其中每个元素都有一定的优先级，优先级最高的元素最先被删除。堆能够高效地支持优先队列的所有操作，如插入新元素和移除最高（或最低）优先级元素。这在很多实际场景中非常有用，比如任务调度、带优先级的事件处理系统、网络流量管理等。

  2. 堆排序 堆排序是一种基于堆的排序算法，利用最大堆（或最小堆）的性质来排序数据。它的主要步骤包括构建一个堆，然后反复移除堆顶元素并维持堆的性质，直到堆为空。堆排序的时间复杂度为O(n log n)，且不需要额外的存储空间，是一种非常高效的排序方法。

  3. 图算法 在许多图算法中，比如计算最短路径的Dijkstra算法和构建最小生成树的Prim算法，使用优先队列来选择下一个要处理的顶点。堆作为优先队列的实现，可以有效地减少这些算法的运行时间。

  4. 动态数据流的中值查找 在处理动态数据流时，堆可以用来快速计算数据的中值或其他顺序统计量。通过维护一个最大堆和一个最小堆，可以保证两个堆的顶部元素表示当前所有数据的中间值。

  5. 带权调度问题 在处理带权任务调度问题时，可以使用最小堆来安排任务的执行顺序，以最小化等待时间或优化其他指标。

  6. Top K问题 堆经常用于解决Top K问题，即从一组数据中找到最大或最小的K个元素。使用最小堆（或最大堆）可以有效地解决这类问题，特别是在处理大数据流或数据集合非常大时。

  7. 频率统计和数据压缩 在频率统计和数据压缩领域，如Huffman编码算法，使用最小堆来构建Huffman树，以实现高效的编码方案。

9、简述什么是中缀、前缀、后缀符号？

中缀符号（Infix Notation）

  • 定义：运算符位于操作数的中间。这是人们在日常书写数学和逻辑表达式时最常用的格式。
  • 例子：A + B，A - B * C。
  • 特点：中缀表达式需要考虑运算符的优先级和括号，以确定操作数的组合方式。

前缀符号（Prefix Notation，波兰表示法）

  • 定义：运算符位于操作数之前。这种格式不需要括号来指示运算的顺序，运算的顺序遵循自顶向下的方式。
  • 例子：+ A B 表示 A + B，- A * B C 表示 A - (B * C)。
  • 特点：前缀表达式的求值可以从右向左进行，每遇到一个运算符就应用到紧接着的两个操作数上。

后缀符号（Postfix Notation，逆波兰表示法）

  • 定义：运算符位于操作数之后。类似于前缀表示法，后缀表示法也不需要括号来指明运算的顺序。
  • 例子：A B + 表示 A + B，A B C * - 表示 A - (B * C)。
  • 特点：后缀表达式的求值可以从左向右进行，每遇到一个运算符就应用到之前的两个操作数上，适合计算机处理。



数组

1、请你回答一下Array&List， 数组和链表的区别

数组的特点：数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。但数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。并且数组不利于扩展，数组定义的空间不够时要重新定义数组。

链表的特点：

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

各自的优缺点

数组的优点：

  1. 随机访问性强
  2. 查找速度快

数组的缺点:

  1. 插入和删除效率低
  2. 可能浪费内存
  3. 内存空间要求高，必须有足够的连续内存空间。
  4. 数组大小固定，不能动态拓展

链表的优点:

  1. 插入删除速度快
  2. 内存利用率高，不会浪费内存
  3. 大小没有固定，拓展很灵活。

链表的缺点:

不能随机查找，必须从第一个开始遍历，查找效率低

2、一个长度为N的整形数组，数组中每个元素的取值范围是[0,n-1],判断该数组否有重复的数，请说一下你的思路并手写代码

把每个数放到自己对应序号的位置上，如果其他位置上有和自己对应序号相同的数，那么即为有重复的数值。时间复杂度为O(N),同时为了节省空间复杂度，可以在原数组上进行操作，空间复杂度为O(1)

bool IsDuplicateNumber(int *array, int n)
{
    if(array==NULL) return false;
    int i,temp;
    for(i=0;i<n;i++)
    {
        while(array[i]!=i)
        {
            if(array[array[i]]==array[i]) return true;
            temp=array[array[i]];
            array[array[i]]=array[i];
            array[i]=temp;
        }
    }
    return false;
}



排序

十大排序算法




哈希

1、请你来说一说hash表的实现，包括STL中的哈希桶长度常数

hash表的实现主要包括构造哈希和处理哈希冲突两个方面：对于构造哈希来说，主要包括直接地址法、平方取中法、除留余数法等。

对于处理哈希冲突来说，最常用的处理冲突的方法有开放定址法、再哈希法、链地址法、建立公共溢出区等方法。SGL版本使用链地址法，使用一个链表保持相同散列值的元素。

虽然链地址法并不要求哈希桶长度必须为质数，但SGI STL仍然以质数来设计哈希桶长度，并且将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28个质数之中，“最接近某数并大于某数”的质数。

2、请你回答一下hash表如何rehash，以及怎么处理其中保存的资源

C++的hash表中有一个负载因子loadFactor，当loadFactor<=1时，hash表查找的期望复杂度为O(1). 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <1的情况下，才能够添加。因此，当Hash表中loadFactor==1时，Hash就需要进行rehash。rehash过程中，会模仿C++的vector扩容方式，Hash表中每次发现loadFactor ==1时，就开辟一个原来桶数组的两倍空间，称为新桶数组，然后把原来的桶数组中元素全部重新哈希到新的桶数组中。

3、请你说一下哈希表的桶个数为什么是质数，合数有何不妥？

哈希表的桶个数使用质数，可以最大程度减少冲突概率，使哈希后的数据分布的更加均匀。如果使用合数，可能会造成很多数据分布会集中在某些点上，从而影响哈希表效率。算法：

给定一个数字数组，返回哈夫曼树的头指针

struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)
{
int k1 = -1, k2;
for (j = 0; j < n; j++)
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;
b[k2] = NULL;
}
free(b);
return q;
}

4、请你说一下解决hash冲突的方法

当哈希表关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，这样的现象称为哈希冲突。目前常用的解决哈希冲突的方法如下： 开放定址法: 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。

链地址法：将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中

建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。

5、什么情况下可是使用哈希表？

  1. 快速数据查找 当需要快速查找、插入或删除数据项时，哈希表提供了接近O(1)的平均时间复杂度，这比其他数据结构如链表、数组或二叉搜索树更高效。

  2. 实现映射关系 哈希表自然支持键值对的存储，使其成为实现映射（Map）或字典（Dictionary）结构的理想选择。当需要存储和检索键值对时，哈希表是一个非常好的选择。

  3. 去重 哈希表可以用来快速检查一个元素是否已存在于集合中，因此非常适用于去重操作。

  4. 缓存实现 哈希表因其快速访问特性，被广泛用于实现缓存机制（如LRU缓存），可以快速地存取缓存的数据项。

  5. 数据库索引 数据库系统中的索引通常使用哈希表来实现，以支持快速的数据检索。

  6. 计数器 在需要对大量数据进行计数时（如统计词频、网站访问量等），哈希表可以作为一个高效的计数器。

  7. 实现集合 当需要快速判断元素是否属于某个集合时，哈希表提供了一种高效的方式来实现集合操作（如并集、交集、差集等）。

  8. 防止重复提交 在Web开发中，哈希表可以用来存储用户的请求标识，以防止表单的重复提交。




链表

1、简述什么是链表 ？

链表是一种常见的基础数据结构，它是由一系列节点组成的集合。每个节点至少包含两个部分：一部分存储数据元素（数据字段），另一部分存储指向下一个节点的链接（指针或引用）。链表通过节点间的指针连接起来，形成一个序列。

2、简述链表的分类 ？

单向链表（Singly Linked List）

  • 定义：每个节点包含数据和一个指向下一个节点的指针。链表的遍历只能是单向的，从头节点开始直到遇到一个指针指向null的节点，表示链表的结束。
  • 用途：适用于简单的数据结构，需要顺序访问元素时。

双向链表（Doubly Linked List）

  • 定义：每个节点包含数据和两个指针，一个指向前一个节点，另一个指向下一个节点。这允许链表可以双向遍历。
  • 用途：适用于需要双向遍历的场景，如实现某些类型的缓存机制或复杂的数据结构，比如双向队列（deque）。

循环链表（Circular Linked List）

  • 定义：在单向链表的基础上，最后一个节点的指针不是指向null，而是指回链表的头节点，形成一个环。
  • 用途：适用于需要周期性访问元素的场景，如轮转调度算法。

双向循环链表（Doubly Circular Linked List）

  • 定义：结合双向链表和循环链表的特点，链表中的每个节点都有两个链接，一个指向前一个节点，另一个指向下一个节点，且最后一个节点的下一个节点是头节点，头节点的前一个节点是尾节点，形成一个环。
  • 用途：适用于需要双向周期访问元素的复杂场景，如高效地实现某些数据集合的迭代器。

3、链表的应用场景有哪些？

  1. 动态内存管理 链表在动态内存分配和管理方面非常有用，因为它能够灵活地调整数据结构的大小，不需要预先声明固定的空间大小。这使得链表成为编写内存管理器和垃圾收集算法时的一个好选择。

  2. 实现栈、队列和双端队列

    • 栈：链表非常适合实现栈结构，因为栈的主要操作（入栈和出栈）都发生在同一端，链表能够提供高效的时间复杂度O(1)的插入和删除操作。
    • 队列：使用链表可以方便地实现队列结构，特别是链表允许在尾部插入和头部删除的操作，与队列的FIFO（先入先出）特性完美匹配。
    • 双端队列：链表（特别是双向链表）也可以用来实现双端队列，其中元素可以从两端插入或删除，为复杂的数据操作提供了灵活性。

  3. 图的表示 在表示图结构时，链表可以用来动态地存储顶点和边信息，尤其是在邻接表表示法中，链表用于存储与每个顶点相邻的顶点列表。

  4. 哈希表的冲突解决 链表是解决哈希表冲突的一种常见方法，称为链地址法或分离链接法。当两个键映射到同一哈希值时，这些键的条目可以存储在同一个索引下的链表中。

  5. 多项式运算 链表可以用来表示多项式，其中每个节点表示多项式中的一项。这样可以方便地进行多项式的加法、乘法等运算，特别是对于稀疏多项式的操作。

  6. 文本编辑器的实现 链表（特别是双向链表）可以用于实现文本编辑器的基本功能，如光标移动、文本插入和删除。链表允许在任意位置快速插入和删除字符，非常适合处理动态变化的文本数据。

  7. 内存分配 在操作系统中，链表被用于管理可用内存块和已分配内存块，以支持动态内存分配。

4、头指针和头结点的区别？

  • 性质上的区别：头指针是一个指向链表第一个实际数据节点的指针；头节点是链表中的一个额外的、通常不存储有效数据的辅助节点。
  • 功能上的区别：头指针用于访问链表的起始位置；头节点则用于简化链表操作，特别是插入和删除操作。
  • 存在意义上的区别：头指针是为了标识链表的开始；头节点是为了操作的统一和便利性。



高级算法

1、请问加密方法都有哪些

1、单向加密

单向加密又称为不可逆加密算法，其密钥是由加密散列函数生成的。单向散列函数一般用于产生消息摘要，密钥加密等，常见的有：

MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，非可逆，相同的明文产生相同的密文；

SHA（Secure Hash Algorithm）：可以对任意长度的数据运算生成一个160位的数值。其变种由SHA192，SHA256，SHA384等；

CRC-32，主要用于提供校验功能；

算法特征：

输入一样，输出必然相同；

雪崩效应，输入的微小改变，将会引起结果的巨大变化；

定长输出，无论原始数据多大，结果大小都是相同的；

不可逆，无法根据特征码还原原来的数据；

2、对称加密

采用单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。

特点：

1、加密方和解密方使用同一个密钥；

2、加密解密的速度比较快，适合数据比较长时的使用；

3、密钥传输的过程不安全，且容易被破解，密钥管理也比较麻烦；

优点：对称加密算法的优点是算法公开、计算量小、加密速度快、加密效率高。

缺点：对称加密算法的缺点是在数据传送前，发送方和接收方必须商定好秘钥，然后使双方都能保存好秘钥。其次如果一方的秘钥被泄露，那么加密信息也就不安全了。另外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的唯一秘钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。

3、非对称加密

非对称密钥加密也称为公钥加密，由一对公钥和私钥组成。公钥是从私钥提取出来的。可以用公钥加密，再用私钥解密，这种情形一般用于公钥加密，当然也可以用私钥加密，用公钥解密。常用于数字签名，因此非对称加密的主要功能就是加密和数字签名。

特征：

1）秘钥对，公钥(public key)和私钥(secret key)

2）主要功能：加密和签名

发送方用对方的公钥加密，可以保证数据的机密性（公钥加密）。

发送方用自己的私钥加密，可以实现身份验证（数字签名）。

3）公钥加密算法很少用来加密数据，速度太慢，通常用来实现身份验证。

常用的非对称加密算法

RSA：由 RSA公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的；既可以实现加密，又可以实现签名。

DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）。

ECC（Elliptic Curves Cryptography）：椭圆曲线密码编码。

2、什么是LRU缓存

LRU(最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高

实现：使用一个链表保存缓存数据，将新数据插入到头部，每当缓存命中时，则将命中的数据移动到链表头部，当链表满的时候，将链表尾部的数据丢弃。

3、请你说一说洗牌算法

1、Fisher-Yates Shuffle算法

最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：

1）初始化原始数组和新数组，原始数组长度为n(已知)。

2）从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）。

3）从剩下的k个数中把第p个数取出。

4）重复步骤2和3直到数字全部取完。

5）从步骤3取出的数字序列便是一个打乱了的数列。

时间复杂度为O(n*n)，空间复杂度为O(n)。

2）Knuth-Durstenfeld Shuffle

Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，在原始数组上对数字进行交互，省去了额外O(n)的空间。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

算法步骤为：

  1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
  2. 生成一个从 0 到 n - 1 的随机数 x；
  3. 输出 arr 下标为 x 的数值，即为第一个随机数；
  4. 将 arr 的尾元素和下标为 x 的元素互换；
  5. 同2，生成一个从 0 到 n - 2 的随机数 x；
  6. 输出 arr 下标为 x 的数值，为第二个随机数；
  7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；

……

如上，直到输出m 个数为止

时间复杂度为O(n)，空间复杂度为O(1)，缺点必须知道数组长度n。