面试题集

算法复杂度 (Algorithm Complexity)

• 时间复杂度 (Time Complexity): 估算算法执行所需的时间随输入规模 N 增大的变化趋势。它不是指具体的执行秒数（因为这还依赖于硬件、编程语言等），而是指算法执行的基本操作数量的增长级别。
• 大O符号描述的是算法复杂度的渐进上界 (asymptotic upper bound) 忽略低阶项 忽略常数系数 大O表示法通常描述的是最坏情况下的复杂度，因为它提供了一个性能的保证上限
• O(N) 被称为线性复杂度 (Linear Complexity)。这意味着算法的执行时间（或所需空间）与输入数据的规模 N 成正比关系。
• O(1) - 常数复杂度 (Constant Complexity): 算法的执行时间不随输入规模 N 的变化而变化
• O(logN) - 对数复杂度 (Logarithmic Complexity): 当 N 增大时，执行时间以对数级别增长
• O(NlogN) - 线性对数复杂度 (Linearithmic Complexity): 常见于高效的排序算法。 例如：归并排序 (Merge Sort)，快速排序 (Quick Sort) 的平均情况，堆排序 (Heap Sort)。
• O(N 2) - 平方复杂度 (Quadratic Complexity): 执行时间与 N 的平方成正比。通常涉及对数据集的嵌套循环。
• O(N!) - 阶乘复杂度 (Factorial Complexity): 执行时间随 N 呈阶乘级增长，比指数级增长更快，非常低效。

讲解一下 贪心算法 动态规划算法 和分治法？

• 它在每一步决策时，都采取当前状态下最好或最优的选择，而不从整体最优上加以考虑。它期望通过每一次的局部最优选择， 不一定能得到全局最优解： 贪心算法的致命弱点在于它不能保证最终得到的是全局最优解
• 动态规划算法 （Dynamic Programming,）核心思想是将一个复杂的问题分解为若干个重叠的子问题，记录并复用子问题解，避免重复计算利用已解决的子问题的解来高效地解决更大的问题。 定义状态 找出状态转移方程： 这是动态规划最核心的一步。需要找到当前状态如何由之前的状态推导出来。 确定初始条件（边界条件） 构造最优解
• 分治法的核心思想是将一个难以直接解决的大问题，分割成一些规模较小的子问题，分别解决。然后将各个子问题的解合并起来，从而得到原问题的解。分解 (Divide)： 将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。解决 (Conquer)： 若子问题规模较小且容易解决则直接解决，否则递归地解决各个子问题。合并 (Combine)： 将各个子问题的解合并为原问题的解。

各种排序算法

• 一个排序算法是稳定的，如果它能保证在排序完成后，具有相同键值（排序依据的值）的元素保持它们在输入序列中的相对顺序。 各种排序算法的性能总结 不稳定的排序算法有：希尔排序、选择排序、堆排序、快速排序。 ————————————————– 排序方法: 插入排序 时间复杂度 (平均): O(n^2) 时间复杂度 (最坏): O(n^2) 时间复杂度 (最好): O(n) 空间复杂度: O(1) 稳定性: 稳定 ————————————————– 排序方法: 选择排序 时间复杂度 (平均): O(n^2) 时间复杂度 (最坏): O(n^2) 时间复杂度 (最好): O(n^2) 空间复杂度: O(1) 稳定性: 不稳定 这种“交换”操作可能会跨越很长的距离，从而可能改变等值元素的相对顺序。 ————————————————– 排序方法: 快速排序 时间复杂度 (平均): O(n log n) 时间复杂度 (最坏): O(n^2) 时间复杂度 (最好): O(n log n) 空间复杂度: O(log n) 稳定性: 不稳定 选择基准然后分区，把比基准小的放在基准左边，把比基准大的放在基准右边，然后递归，涉及到了交换 ————————————————– 排序方法: 归并排序 时间复杂度 (平均): O(n log n) 时间复杂度 (最坏): O(n log n) 时间复杂度 (最好): O(n log n) 空间复杂度: O(n) 稳定性: 稳定 ————————————————– ★★★★★★归并排序的最坏时间复杂度优于快排，为什么我们还是选择快排？ 快速排序通常比归并排序更快。尽管快速排序在最坏情况下的性能可能较差，但在大多数情况下，它的平均时间复杂度要比归并排序低。 快速排序是原地排序算法。原地排序算法是指排序过程中不需要额外的存储空间，只利用原始输入数组进行排序。 快速排序的实现相对简单。相比于归并排序，快速排序的实现更为简洁，代码量更少。 总结：由于快速排序在平均情况下表现更好、占用更少的空间并且更易于实现。 ————————————————– 排序方法: 希尔排序 时间复杂度 (平均): O(n^1.3) (近似值) 时间复杂度 (最坏): O(n^2) 时间复杂度 (最好): O(n) 空间复杂度: O(1) 稳定性: 不稳定 ————————————————– 排序方法: 堆排序 时间复杂度 (平均): O(n log n) 时间复杂度 (最坏): O(n log n) 时间复杂度 (最好): O(n log n) 空间复杂度: O(1) 稳定性: 不稳定 ————————————————– 排序方法: 冒泡排序 时间复杂度 (平均): O(n^2) 时间复杂度 (最坏): O(n^2) 时间复杂度 (最好): O(n) 空间复杂度: O(1) 稳定性: 稳定 ————————————————–

KMP算法

• KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，它能在O(m+n)的时间复杂度内完成字符串匹配，其中m是模式串的长度，n是文本串的长度。相比于朴素的字符串匹配算法，KMP算法的优势在于，当发生不匹配时，它能避免文本串指针的回溯，而是利用已经匹配的部分信息来确定下一次比较的起始位置。

• KMP算法的核心在于构建一个“部分匹配表”（也称为“前缀函数”或“next数组”），这个表记录了模式串中每个位置之前最长的公共前后缀的长度。

查找，树

静态查找的方法有哪些

• 顺序查找：关键字和所有元素一个个对比，O(n)
• 二分查找：要求查找表为顺序存储结构且有序，将 n 个元素分成大致相等的两部分，取 a[n/2] 和关键 字作比较，如果相等，则找到了；如果大于或者小于，则递归地在相应的半部分查找，O(logn)
• 分块查找：将查找表分成若干子表，保证子表间有序，而子表内无序，将各子表的最大元素构成一张索 引表。查找时先用索引表找到位于哪个块，再在块内进行顺序查找

满二叉树和完全二叉树有什么区别？

• 满二叉树高度为h。结点的个数就是2^h-1，除了最后一层叶子结点，所有的结点都有两个孩，每一层都是满的 所有的结点度为2

• 完全二叉树就是在满二叉树的基础上，最后一层从右往左删除一些叶子节点，如果一个结点只有一个叶子结点那一定是左孩子

由遍历序列构造二叉树

• 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
• 由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
• 由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树
• 需要注意的是，若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。
• 一定要有中序遍历

树的存储结构？

二叉搜索树 BST

• 二叉搜索树（二叉排序树）：左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于 根节点的值，它的左右子树也分别为二叉搜索树。

• 二叉搜索树中序遍历的结果是有序的。

• 删除一个结点时，当左、右子树都不为空，则在右子树上找中序的第一个子结点填补

• 理想情况下的查找速度可以用 O(logn) 来衡量 最差的情况就是非常不平衡退化成链表 于是产生了AVL

平衡二叉树 AVL

• 平衡二叉树（AVL树）：是一种特别的二叉排序树，它的左右子树的高度差的绝对值不超过 1

• 二叉搜索树上的操作的时间复杂度取决于树高，二叉树容易退化为一条链，而平衡二叉树通过降低树的高度，提高效率。平衡因子 = 某节点的左子树深度 - 右子树深度，任意结点的平衡因子只能是+1 -1 0

• 插入结点时，要保证平衡，则可能要进行平衡旋转，包括四种情况 在左子树的左子树上插入节点时向右进行单向旋转； 在右子树的右子树上插入节点时向左进行单向旋转； 在左子树的右子树插入节点时先向左旋转再向右旋转； 在右子树的左子树插入节点时先向右旋转再向左旋转。

• AVL树在查找操作上能始终保持 O(logn) 的时间复杂度，即使在最坏情况下也是如此。
• 关于如何旋转 https://blog.csdn.net/qq_43762191/article/details/107280503

红黑树

• 红黑树是一种自平衡的二叉搜索树，保证时间复杂度为 O(logn)
• 结点非黑即红，根结点一定是黑色，叶子结点（NIL）一定是黑色 ，不存在两个相邻的红结点，从任一结点到每个叶子结点的所有路径，都包含相同数目的黑色节点，这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
• https://houbb.github.io/2020/10/17/data-struct-tree-04-red-black-tree

B树 B+树

• B 树是所有结点的平衡因子均等于 0 的多路平衡查找树，B+ 树是对 B 树的改进。

• B 树的一个结点可以存储多个值，这些值是按照递增排序的，一个结点有多个子树，所有叶子结点都位于同一层。 优点：数据库查询中，通过 B 树来存储数据，可以减少树高，即可以减少磁盘 I/O ，提高查询效率（结点内查找是在内存进行的，比磁盘快得多）。 缺点：不利于区间查找，如要找 0~100 的索引值，那么 B 树需要多次从根结点开始逐个查找。

• B+ 树是对 B 树的改进，MySQL 种用的就是 B+ 树，它的叶子结点直接有指针，构成了一个链表，这个链表是有序的，即可以直接通过遍历链表进行区间查找，非叶子结点的元素在叶子结点上都冗余了，非叶子结点仅仅是作为快速查找的索引。

什么是哈夫曼树？如何构造？哈夫曼树的应用

• 关键是最小的带权路径长度WPL，哈夫曼树又称为最优二叉树，其特点是，给定一组带权的叶子结点，若构造所得到的二叉树拥有最小的带权路径长度WPL，则称该二叉树为一棵哈夫曼树。

• 构造办法：首先在集合中挑选出两个权值最小的叶子结点进行合并得到新的结点加入集合，再将两个被选中的结点剔除出集合。在树的构造上，将这两个结点作为叶子结点衔接到合并而成的新结点上。重复以上过程直到集合中只有一个元素，哈夫曼树则完成构造。

• 哈夫曼编码能够保证是前缀码，消除编码的二义性，即每个编码都不是另一个编码的前缀。哈夫曼编码能够保证字符编码总长最短

• 所以，哈夫曼编码的性质有：１，哈夫曼编码是前缀码２，哈夫曼编码是最优前缀码

哈希函数 哈希表

• 哈希表（散列表）：通过哈希函数将查找表中的关键字映射成一个地址来加快查找速度
• 哈希函数的构造
  • 直接定址法：取关键字的某个线性函数值作为地址，适用于关键字分布均匀的情况
  • 除留余数法：取关键字对某个数取余的值作为地址
  • 数字分析法：当关键字位数很大时，取分布均匀的任意几位作为地址
  • 平方取中法：取关键字的平方的中间几位作为地址
• 如何解决哈希冲突
  • 哈希冲突：两个不同的数经过哈希函数计算后得到了同一个地址
  • 开放定址法：遇到哈希冲突时，去寻找一个新的空闲的哈希地址。包含线性探测法，二次探测法，双重散列。
  • 链接法：将所有哈希地址相同的记录都链接在同一链表中
  • 再哈希法：构造多个哈希函数，如果发生哈希冲突时就使用另外的哈希函数计算
  • 溢出表法：将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中
• 哈希函数是一种将任意长度的输入数据（也称为“键”或“关键字”，Key）通过一个特定的算法，映射成固定长度的输出（称为“哈希值”、“散列值”或“哈希码”，Hash Code）的函数。

  hash_value = hash_function(key)
  

• 对于相同的输入键，哈希函数必须总是产生相同的哈希值。这是最基本的要求。 计算哈希值的过程应该非常快，不能成为性能瓶颈。哈希函数应尽可能地将输入键均匀地映射到哈希值空间中的每一个位置。这意味着对于任意一个键，它被映射到任何一个哈希值的概率应该大致相等。这有助于减少哈希冲突。不同的输入键应该尽可能产生不同的哈希值。然而，由于输入空间通常远大于输出空间（哈希值的取值范围有限），哈希冲突（不同的键产生相同的哈希值）是不可避免的。一个好的哈希函数应该努力使冲突的概率降到最低。输入键的微小变化应该导致输出哈希值的巨大且不可预测的变化。这在密码学应用中尤为重要，可以防止通过相似输入来推测原始数据。

• 常见的哈希函数示例：
• 除留余数法 (Division Method)： h(key) = key % M，其中 M 通常是一个质数，作为哈希表的大小。这是最简单也比较常用的一种方法。
• 加密哈希函数： SHA-1, SHA-256, SHA-512 等。这类函数除了上述特性外，还具有单向性（难以从哈希值反推出原始输入）和强抗碰撞性（难以找到两个不同输入产生相同哈希值）。
• 平方取中法 (Mid-square Method)： 计算键的平方，然后取中间的几位作为哈希值。
• 斐波那契散列 (Fibonacci Hashing)
• 字符串哈希函数： 例如 BKDRHash, APHash, DJBHash, SDBMHash, MurmurHash, CityHash, xxHash 等，它们专门为字符串设计，力求在速度和散列均匀性之间取得平衡。
• 哈希表是一种根据键 (Key) 直接访问内存存储位置的数据结构。

堆 堆的基本操作 堆的应用

• https://blog.csdn.net/qq_34270874/article/details/113091364

• 堆的基本操作，
  • 插入 (Insert)： 将一个新元素添加到堆中，O(logn)，先放在数组的末尾，然后根据父亲结点=⌊(i−1)/2⌋(下取整)，进行比较和交换，最差的情况就是从叶子节点一直上浮到根节点。
  • 大顶堆删除最大元素示例： 删除堆的根节点，然后把最后一个元素移到根部，再往下进行比较交换维护堆结构，O(logn)
  • 堆化 (Heapify)： 调整一个数组或子树，使其满足堆的性质。
  • 建堆 (Build Heap)： 将一个无序数组转换为一个堆。从最后一个非叶子节点开始，逐个向上对其进行“下沉”操作，确保每个子树都满足大顶堆的性质。最后一个非叶子节点的索引是 ⌊(n/2)−1⌋
• 堆在计算机中的应用

topk问题

• 维护一个小顶堆可以快速得出当前前K大的数据
• 因为堆顶是最小的元素，方便“踢人”（理解了很久）。因为我们想要找到最大的 K 个元素。堆中始终维护着当前遇到的 K 个最大元素。小顶堆的堆顶是这 K 个元素中最小的。当我们遇到一个新元素时，如果它比堆顶还小，那它肯定不在前 K 大的范围内。如果它比堆顶大，那么它有资格进入前 K 大的范围，而堆顶那个更小的元素就应该被踢出去。小顶堆的特性使得我们能够 O(1) 地访问到这 K 个元素中的“门槛”（即堆顶）

如何快速判断一个元素是否在1亿个元素中？★★

使用HashMap很难处理，因为非常消耗内存空间，很可能会导致内存溢出。因此可以采用位图法（布隆过滤器）。

首先对1亿个元素j进行遍历，对每一个元素使用一个函数或者多个哈希函数进行映射，把它映射到一个具有32比特位的位图中，那么这个位图理论上可以存储2^32个元素，且只占用512MB内存（2^32bit = 2^29B = 2^9MB = 512MB，事实上当2^27最接近1亿，也可以使用27位的位图）。等1亿个元素都存储到位图中时，再对想要判断的元素进行相同的哈希函数映射，如果一个元素实际不存在于位图，但是也有被判断为存在，这是因为有可能会产生哈希冲突。

如果构建好了位图，那么判断一个元素是否在1亿个元素的时间复杂度是O(1)。

最小生成树算法？

• 什么是最小生成树 (MST)？在一个连通的、无向的、带权重的图中，最小生成树 (MST) 是该图的一个子图，它具备以下特点：包含图中所有的顶点: 子图连接了原图中的每一个顶点。是一棵树 (Tree): 子图是无环的。对于包含 V 个顶点的图，其生成树恰好有 V−1 条边。权重之和最小: 在所有可能的生成树中，该子图的各条边的权重之和是最小的。

• 主要有两种著名的贪心算法可以找到最小生成树：Prim 算法 和 Kruskal 算法。

最短路径算法?

• dijkstra算法：求解单源最短路径的贪心算法，要求边权不为负

• Floyd算法：求解多源图最短路径的动态规划算法

图通常用什么数据结构进行存储？

• 邻接矩阵是用一个二维数组来表示图。如果图有 N 个顶点，那么这个二维数组的大小就是 N×N。对于无权图，如果顶点 i 和顶点 j 之间有边相连，则矩阵中第 i 行第 j 列的元素 A[i][j] 为 1 (或 true)，否则为 0 (或 false)。对于有权图， A[i][j] 表示顶点 i 和顶点 j 之间边的权重。如果两点间没有边，可以表示为无穷大 (Infinity) 或一个特殊值 (如 0，但要注意区分权重为0的情况)。对于无向图，邻接矩阵是对称的，即 A[i][j]=A[j][i]。判断两个顶点之间是否有边非常快，只需要 O(1) 的时间复杂度。空间复杂度较高，为 O(N^2)，其中 N 是顶点数量。对于稀疏图 (边的数量远小于顶点数量的平方) 会浪费大量存储空间。

• 邻接表 (Adjacency List)，邻接表是图的一种链式存储结构。它为图中的每个顶点维护一个列表 (或链表)，这个列表存储了所有与该顶点直接相邻的顶点。通常使用一个数组，数组的每个元素对应图中的一个顶点。数组的每个元素指向一个链表 (或其他动态数据结构，如动态数组、哈希表等)。链表中的每个节点表示与当前顶点相邻的一个顶点。获取一个顶点的所有邻接点非常高效。判断两个顶点之间是否有边，最坏情况下需要遍历其中一个顶点的邻接链表，时间复杂度为 O(degree(v))，其中 degree(v) 是顶点的度。对于稠密图，这个操作可能比邻接矩阵慢。

简单介绍dfs和bfs

• dfs是使用栈进行深度优先搜索，按照一个路径一直访问到底，
• bfs是使用队列使用广度优先搜索，先访问源点，然后访问它的相邻结点，根据每个相邻结点的访问，依次继续访问他们的邻居结点
• dfs找到可行解 bfs找到最短路径

---

• Previous
  线性代数概率论复习
• Next
  项目复习