数据结构算法高频总结三

发表于 2025/01/13 更新于 2025/01/13

作者 匆匆那年 35 分钟阅读

计算二叉树层高

计算二叉树的层高是通过递归或迭代的方式找到从根节点到最远叶节点的最长路径上的节点数。

方法 1：递归实现

思路

如果当前节点为空，返回高度为 0。
递归计算左子树和右子树的高度。
当前节点的高度为左右子树高度的最大值加 1。

C++ 实现

  
#include <iostream>

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归计算二叉树的层高
int getTreeHeight(TreeNode* root) {
    if (!root) return 0; // 空节点高度为 0
    int leftHeight = getTreeHeight(root->left);  // 左子树高度
    int rightHeight = getTreeHeight(root->right); // 右子树高度
    return std::max(leftHeight, rightHeight) + 1; // 当前节点高度
}

// 测试函数
int main() {
    // 创建二叉树
    //         1
    //       /   \
    //      2     3
    //     / \     \
    //    4   5     6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    std::cout << "Tree Height: " << getTreeHeight(root) << std::endl;

    // 清理内存（手动释放）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

方法 2：迭代实现

思路

使用层序遍历（BFS），通过队列遍历二叉树的每一层。
每处理一层，层高加 1。
遍历结束时，层高即为二叉树的高度。

C++ 实现

  
#include <iostream>
#include <queue>

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 迭代计算二叉树的层高
int getTreeHeightIterative(TreeNode* root) {
    if (!root) return 0; // 空树高度为 0

    std::queue<TreeNode*> q;
    q.push(root);
    int height = 0;

    while (!q.empty()) {
        int levelSize = q.size(); // 当前层的节点数量
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            // 将下一层的节点加入队列
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        height++; // 每处理一层，高度加 1
    }

    return height;
}

// 测试函数
int main() {
    // 创建二叉树
    //         1
    //       /   \
    //      2     3
    //     / \     \
    //    4   5     6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    std::cout << "Tree Height (Iterative): " << getTreeHeightIterative(root) << std::endl;

    // 清理内存（手动释放）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

时间与空间复杂度

递归方法

时间复杂度：$O(n)$，其中 $n$ 是节点总数，每个节点只访问一次。
空间复杂度：$O(h)$，递归调用栈的最大深度为二叉树的高度 $h$。

迭代方法

时间复杂度：$O(n)$，每个节点只入队和出队一次。
空间复杂度：$O(w)$，队列中最大可能存储的节点数为二叉树的宽度 $w$。

示例运行

输入：

输出：

Tree Height: 3
Tree Height (Iterative): 3

总结

递归方法简单直观，代码清晰，但在树的高度较大时可能会导致栈溢出。
迭代方法基于队列的层序遍历，更适合深度较大的树，避免了递归栈的限制。

给一个连续非空子数组，找它乘积最大的（动态规划）

找到一个连续非空子数组的最大乘积问题，可以通过动态规划（Dynamic Programming, DP）来解决。这是一个经典的最大乘积子数组问题。

问题分析

因为负数的乘积可能变成正数，因此需要同时跟踪：
- 最大乘积（maxProduct）
- 最小乘积（minProduct）
- maxProduct 用于找到当前最大乘积，而 minProduct 用于处理负数的情况。
每次迭代时，对于当前元素 nums[i]：
- 更新 maxProduct[i] 为 $\max(nums[i], nums[i] \times maxProduct[i-1], nums[i] \times minProduct[i-1])$。
- 更新 minProduct[i] 为 $\min(nums[i], nums[i] \times maxProduct[i-1], nums[i] \times minProduct[i-1])$。
使用一个全局变量记录最大值即可。

实现步骤

遍历数组，同时维护当前的 maxProduct 和 minProduct。
每次更新 maxProduct 和 minProduct，并记录全局最大值。
最终返回全局最大值。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>

int maxProduct(const std::vector<int>& nums) {
    if (nums.empty()) return 0;

    int maxProduct = nums[0];
    int minProduct = nums[0];
    int result = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
        int current = nums[i];
        if (current < 0) {
            std::swap(maxProduct, minProduct); // 交换最大和最小，因为负数会改变符号
        }

        maxProduct = std::max(current, maxProduct * current);
        minProduct = std::min(current, minProduct * current);

        result = std::max(result, maxProduct); // 更新全局最大值
    }

    return result;
}

int main() {
    std::vector<int> nums = {2, 3, -2, 4, -1};

    int maxProductValue = maxProduct(nums);

    std::cout << "Maximum product of subarray: " << maxProductValue << std::endl;

    return 0;
}

代码解析

初始化：
- maxProduct 和 minProduct 初始化为第一个元素。
- result 初始化为第一个元素。
遍历数组：
- 如果当前元素为负数，交换 maxProduct 和 minProduct，因为负数会导致最小变最大，最大变最小。
- 更新 maxProduct 和 minProduct，分别取当前元素、自身乘积后的最大值或最小值。
更新结果：
- 在每次迭代中，将当前 maxProduct 与全局最大值比较，更新全局最大值。

时间和空间复杂度

时间复杂度：
$O(n)$
- 只需遍历数组一次。
空间复杂度：
$O(1)$
- 只需要常数空间保存当前的 maxProduct 和 minProduct。

测试用例

输入：

nums = [2, 3, -2, 4, -1]

输出：

Maximum product of subarray: 48

解释：

子数组 [2, 3] 的乘积为 6。
子数组 [4, -1] 的乘积为 -4。
子数组 [2, 3, -2, 4, -1] 的乘积为 48（最大）。

总结

通过动态规划的方法，可以高效求解最大乘积子数组的问题。
负数的处理是关键，需要维护 minProduct 来应对符号反转的情况。

排序算法，哪些是稳定的，哪些是不稳定的

在排序算法中，稳定性是指在排序过程中，如果两个元素的键值相等，排序后它们的相对顺序保持不变。以下是常见排序算法的稳定性分析：

稳定的排序算法

1. 冒泡排序（Bubble Sort）

原理：通过多次交换相邻的元素，将较大的元素逐渐冒泡到数组末尾。
稳定性：稳定。
原因：相邻元素交换时不会改变相等元素的相对位置。

2. 插入排序（Insertion Sort）

原理：将每个元素插入到已排序部分的正确位置。
稳定性：稳定。
原因：插入时只在需要的位置插入，不会改变相等元素的顺序。

3. 归并排序（Merge Sort）

原理：分治法，将数组分成两个子数组分别排序，再合并为有序数组。
稳定性：稳定。
原因：在合并时，如果左右两个子数组的元素相等，优先选择左子数组的元素，保证顺序不变。

4. 基数排序（Radix Sort）

原理：按位排序，从最低有效位到最高有效位依次排序。
稳定性：稳定。
原因：在每一位的排序中，保持相同位的元素顺序不变。

5. 计数排序（Counting Sort）

原理：统计每个元素出现的次数，按计数重构数组。
稳定性：稳定。
原因：在重构过程中，按计数顺序插入，保证相等元素的顺序。

不稳定的排序算法

1. 选择排序（Selection Sort）

原理：每次选择未排序部分中最小（或最大）的元素，放到排序部分的末尾。
稳定性：不稳定。
原因：在选择最小（或最大）元素时，可能跨越相等元素并改变它们的顺序。

2. 快速排序（Quick Sort）

原理：选择一个基准元素，将数组划分为小于基准和大于基准的两个部分，再递归排序。
稳定性：不稳定。
原因：基准元素交换位置时可能改变相等元素的顺序。

3. 堆排序（Heap Sort）

原理：基于堆数据结构，将数组看成完全二叉树，不断取堆顶元素。
稳定性：不稳定。
原因：在堆调整时，可能会跨层交换元素，改变相等元素的顺序。

4. 希尔排序（Shell Sort）

原理：是插入排序的改进版，通过分组进行排序，逐步缩小分组间隔。
稳定性：不稳定。
原因：在分组排序时，相等元素可能被跨组移动，改变顺序。

排序算法稳定性总结表

排序算法	稳定性
冒泡排序	稳定
插入排序	稳定
归并排序	稳定
基数排序	稳定
计数排序	稳定
选择排序	不稳定
快速排序	不稳定
堆排序	不稳定
希尔排序	不稳定

稳定性对实际应用的影响

需要稳定排序的场景：
- 当需要按多个关键字排序时，必须使用稳定排序。例如，先按年龄排序，再按姓名排序。
- 在需要保留相同键值元素的原始顺序时，如数据库记录的排序。
不需要稳定排序的场景：
- 如果元素的键值是唯一的，则稳定性无关紧要。
- 在对性能要求更高的场景中，可以优先选择快速排序或堆排序。

选择排序算法的依据

如果数据量小并且需要稳定性：选择插入排序或冒泡排序。
如果数据量大且需要稳定性：选择归并排序或基数排序。
如果数据量大且对稳定性无要求：选择快速排序或堆排序。

布隆过滤器介绍

布隆过滤器（Bloom Filter）简介

布隆过滤器是一种概率型数据结构，用来高效判断一个元素是否存在于一个集合中。它可以快速判断一个元素“可能存在”或“一定不存在”，但不能确定一个元素“一定存在”。它是一种空间效率高但有一定误差的数据结构，广泛应用于去重、缓存系统等场景。

布隆过滤器的基本原理

位数组（bit array）：
- 布隆过滤器使用一个长度为 $m$ 的位数组（bit array），初始时所有位都设为 0。
哈希函数（hash functions）：
- 使用 $k$ 个不同的哈希函数，将元素映射到位数组中的 $k$ 个位置（索引值）。
插入操作：
- 对要插入的元素 $x$，通过 $k$ 个哈希函数分别计算 $k$ 个位置，将位数组中这些位置的值置为 1。
查询操作：
- 对某个元素 $y$，通过 $k$ 个哈希函数计算其对应的 $k$ 个位置：
  - 如果所有这些位置的值均为 1，则元素可能存在。
  - 如果任意一个位置的值为 0，则元素一定不存在。

布隆过滤器的特性

空间效率高：
- 通过位数组和多个哈希函数实现，比传统的集合数据结构（如哈希表）节省大量空间。
有误报但无漏报：
- 误报：布隆过滤器可能会判断一个元素“可能存在”，但实际上并不存在。
- 无漏报：如果布隆过滤器判断一个元素“不存在”，则它一定不存在。
不可删除：
- 布隆过滤器不支持删除操作（经典布隆过滤器中删除会导致误判）。

布隆过滤器的构造与公式

误报率公式

布隆过滤器的误报率由以下公式给出：

$P = \left( 1 - \left( 1 - \frac{1}{m} \right)^{kn} \right)^k$

$P$：误报率。
$m$：位数组的大小。
$k$：哈希函数的数量。
$n$：插入的元素个数。

优化哈希函数的数量

为了使误报率最小化，哈希函数的最佳数量为：

$k = \frac{m}{n} \ln 2$

优缺点

优点：

空间效率高：相比传统集合数据结构，布隆过滤器占用的内存更少。
查询速度快：查询操作时间复杂度为 $O(k)$，与哈希函数的计算次数成正比。
适合大规模数据：非常适合处理无法完全加载到内存的大规模数据。

缺点：

有误报：可能误判元素存在，但实际不存在。
不可删除：经典布隆过滤器不支持删除操作，除非使用计数布隆过滤器。
对哈希函数的依赖：哈希函数的设计会直接影响误报率。

常见应用场景

缓存系统：
- 在缓存系统（如 Redis）中，布隆过滤器用于判断一个元素是否存在，减少访问后端数据库的次数。
去重：
- 在数据去重场景中，用布隆过滤器快速判断数据是否已经出现过。
网络爬虫：
- 网络爬虫使用布隆过滤器记录已经访问过的 URL，避免重复爬取。
数据库系统：
- 数据库中用布隆过滤器判断某个键是否可能存在于表中，减少不必要的磁盘查找。
垃圾邮件过滤：
- 布隆过滤器可用于检查邮件地址是否在黑名单中。

代码实现（C++ 示例）

以下是一个简单的布隆过滤器实现：

  
#include <iostream>
#include <vector>
#include <functional>

class BloomFilter {
private:
    std::vector<bool> bitArray; // 位数组
    size_t size;               // 位数组大小
    size_t numHashFunctions;   // 哈希函数数量

public:
    BloomFilter(size_t size, size_t numHashFunctions)
        : bitArray(size, false), size(size), numHashFunctions(numHashFunctions) {}

    // 插入元素
    void insert(int element) {
        for (size_t i = 0; i < numHashFunctions; ++i) {
            size_t hash = hashFunction(element, i);
            bitArray[hash % size] = true;
        }
    }

    // 查询元素是否可能存在
    bool contains(int element) const {
        for (size_t i = 0; i < numHashFunctions; ++i) {
            size_t hash = hashFunction(element, i);
            if (!bitArray[hash % size]) {
                return false; // 一定不存在
            }
        }
        return true; // 可能存在
    }

private:
    // 简单哈希函数
    size_t hashFunction(int element, size_t seed) const {
        return std::hash<int>()(element + seed * 31);
    }
};

int main() {
    // 创建布隆过滤器（位数组大小为 1000，使用 3 个哈希函数）
    BloomFilter bloomFilter(1000, 3);

    // 插入元素
    bloomFilter.insert(42);
    bloomFilter.insert(23);
    bloomFilter.insert(89);

    // 查询元素
    std::cout << "42 in filter? " << (bloomFilter.contains(42) ? "Yes" : "No") << std::endl;
    std::cout << "23 in filter? " << (bloomFilter.contains(23) ? "Yes" : "No") << std::endl;
    std::cout << "100 in filter? " << (bloomFilter.contains(100) ? "Yes" : "No") << std::endl;

    return 0;
}

示例运行

in filter? Yes
in filter? Yes
in filter? No

扩展

计数布隆过滤器：
- 在每个位上使用计数器，支持删除操作。
分布式布隆过滤器：
- 在分布式系统中，多个节点协作完成布隆过滤器的功能。
压缩布隆过滤器：
- 通过优化位数组存储，进一步降低内存占用。

总结

布隆过滤器是一种高效的概率型数据结构，特别适合在有限内存中处理大规模数据场景。尽管存在误报，但其优势使得它在实际应用中非常流行，如缓存、去重、网络爬虫等场景中都有广泛使用。

为什么不用布隆过滤器

尽管布隆过滤器（Bloom Filter）在某些场景中表现优秀，但它并不是适合所有场景的完美解决方案。以下是一些可能导致不使用布隆过滤器的原因：

1. 误报问题

原因：
- 布隆过滤器的查询结果可能存在误报：它可能会判断某个元素“可能存在”，但实际上该元素并不存在。
影响：
- 在需要精准结果的场景中，这种误报会导致额外的开销或错误。
替代方案：
- 可以使用哈希表或其他确定性数据结构，这些不会出现误报问题。

2. 不支持删除

原因：
- 布隆过滤器不支持删除元素。一旦将某个元素插入布隆过滤器，无法直接移除它。
- 如果删除某个位，会影响其他哈希函数映射到同一位的元素。
影响：
- 对动态数据集（需要频繁插入和删除）不适用，例如缓存中需要定期移除过期数据。
替代方案：
- 使用 计数布隆过滤器，在每个位记录一个计数器以支持删除操作。

3. 空间使用效率并非总是最优

原因：
- 布隆过滤器在某些场景下的空间使用效率并不总是最优，尤其是数据规模较小时。
- 如果元素数量较少，布隆过滤器的位数组大小可能需要相对较大，才能维持较低的误报率。
影响：
- 在小数据集场景中，布隆过滤器可能比直接存储所有元素占用更多空间。
替代方案：
- 使用简单的哈希表或位图（bitmap）。

4. 依赖哈希函数质量

原因：
- 布隆过滤器需要多个独立的高质量哈希函数。
- 如果哈希函数设计不当，可能会导致哈希冲突过多，增加误报率，甚至让布隆过滤器的效果大打折扣。
影响：
- 在对哈希函数设计要求较高或环境有限的场景中，不适合使用布隆过滤器。
替代方案：
- 选用专门设计的哈希函数（如 MurmurHash 或 CityHash）。

5. 数据重建成本高

原因：
- 布隆过滤器不存储原始数据。如果布隆过滤器被破坏或需要调整大小（如位数组扩容），就需要重新构建整个布隆过滤器。
影响：
- 数据量大时，重新构建成本可能非常高。
替代方案：
- 使用其他动态数据结构（如哈希表或树）更方便重建。

6. 对误报率要求严格的场景

原因：
- 在某些场景中，误报率即使极低也可能导致严重后果。例如：
  - 数据库的唯一性约束。
  - 安全系统（如判断 IP 是否恶意）。
- 布隆过滤器无法消除误报风险。
影响：
- 误报率可能导致错误处理、性能损耗甚至安全漏洞。
替代方案：
- 使用确定性的数据结构，如哈希表或树。

7. 不适用于大范围动态数据

原因：
- 布隆过滤器需要事先设定位数组大小。如果数据量远超预期，则需要重新构建，代价高昂。
- 对于快速变化的大数据流，布隆过滤器无法很好地适应。
影响：
- 对于数据规模不可预测或增长迅速的场景，布隆过滤器表现不佳。
替代方案：
- 可扩展布隆过滤器（Scalable Bloom Filter）：通过动态扩展位数组来适应增长的数据规模。

8. 无法获取元素本身

原因：
- 布隆过滤器不存储元素的具体信息，仅通过位数组和哈希函数判断元素是否可能存在。
影响：
- 如果需要查询具体的元素值，布隆过滤器无法胜任。
替代方案：
- 使用哈希表或其他存储完整元素的数据结构。

总结：什么时候不用布隆过滤器

原因	影响	替代方案
误报问题	需要精准结果的场景	哈希表、树等确定性数据结构
不支持删除	动态数据集（频繁插入删除）	计数布隆过滤器
小数据集空间利用率不高	数据规模较小时，占用空间可能较大	哈希表、位图
依赖哈希函数质量	哈希函数不可靠或难以设计	设计高质量哈希函数，选择适合的过滤器
数据重建成本高	数据流大且需要频繁调整	可扩展布隆过滤器
对误报率要求严格的场景	误报可能导致严重后果	哈希表、树
数据范围动态变化大	数据规模不可预测或变化快速	可扩展布隆过滤器、哈希表
无法获取元素本身	需要存储或查询具体元素值	哈希表或其他存储完整元素的结构

布隆过滤器的适用场景

尽管存在上述限制，布隆过滤器仍非常适合以下场景：

缓存系统：快速判断数据是否存在于缓存中，减少对后端服务的访问。
大规模数据去重：如网络爬虫的 URL 去重。
黑名单过滤：如判断 IP、邮箱是否在黑名单中。
流处理系统：处理大规模实时数据流时，用于初步筛选。

选择是否使用布隆过滤器需要根据具体场景的需求进行权衡。

树的深度和高度。能否都在一个dfs里面呢？

树的深度和高度是两个相关但不同的概念，它们可以在一个深度优先搜索（DFS）中同时计算。

深度和高度的定义

深度（Depth）：
- 从树的根节点到当前节点的边数。
- 根节点的深度为 $0$。
高度（Height）：
- 从当前节点到叶子节点的最长路径的边数。
- 叶子节点的高度为 $0$。

DFS 中同时计算深度和高度

在 DFS 遍历中，可以通过递归的参数传递当前节点的深度，同时在递归的返回值中计算当前节点的高度。
深度在递归过程中逐层累加，记录访问路径上的信息。
高度在递归返回时逐层累加，从叶子节点向根节点计算。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>

// 定义树的节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// DFS 同时计算深度和高度
void dfs(TreeNode* node, int depth, int& maxDepth, int& maxHeight) {
    if (!node) return;

    // 更新最大深度
    maxDepth = std::max(maxDepth, depth);

    // 递归遍历左子树和右子树
    int leftHeight = 0, rightHeight = 0;
    if (node->left) {
        dfs(node->left, depth + 1, maxDepth, leftHeight);
    }
    if (node->right) {
        dfs(node->right, depth + 1, maxDepth, rightHeight);
    }

    // 当前节点的高度
    maxHeight = std::max(leftHeight, rightHeight) + 1;
}

int main() {
    // 构建一棵测试树
    //         1
    //       /   \
    //      2     3
    //     / \     \
    //    4   5     6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    int maxDepth = 0;
    int treeHeight = 0;

    dfs(root, 0, maxDepth, treeHeight);

    std::cout << "Maximum Depth: " << maxDepth << std::endl;
    std::cout << "Tree Height: " << treeHeight << std::endl;

    // 清理内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

代码解析

参数解释：
- depth：当前节点的深度（从根节点到该节点的边数）。
- maxDepth：在遍历过程中记录的最大深度。
- maxHeight：当前节点的高度（从该节点到叶子节点的最长路径）。
递归处理：
- 在递归进入时，计算深度 depth。
- 在递归返回时，计算高度 maxHeight。
结果：
- maxDepth：记录整棵树的最大深度。
- treeHeight：最终根节点的高度即为整棵树的高度。

时间与空间复杂度

时间复杂度：
$O(n)$
- 每个节点访问一次。
空间复杂度：
$O(h)$
- 递归调用栈的深度为树的高度 $h$。

运行结果

输入：

         1
       /   \
      2     3
     / \     \
    4   5     6

输出：

Maximum Depth: 2
Tree Height: 2

总结

深度和高度的计算可以在一个 DFS 中同时完成。
通过递归参数记录深度，返回值计算高度，从而高效完成树的遍历。
此方法简单直观，适用于树的结构分析任务。

数据结构算法, 数据结构算法面经

数据结构算法面经

本文由作者按照 CC BY 4.0 进行授权

计算二叉树层高

方法 1：递归实现

思路

C++ 实现

方法 2：迭代实现

思路

C++ 实现

时间与空间复杂度

递归方法

迭代方法

示例运行

输入：

输出：

总结

给一个连续非空子数组，找它乘积最大的（动态规划）

问题分析

实现步骤

C++ 实现

代码解析

时间和空间复杂度

测试用例

输入：

输出：

解释：

总结

排序算法，哪些是稳定的，哪些是不稳定的

稳定的排序算法

1. 冒泡排序（Bubble Sort）

2. 插入排序（Insertion Sort）

3. 归并排序（Merge Sort）

4. 基数排序（Radix Sort）

5. 计数排序（Counting Sort）

不稳定的排序算法

1. 选择排序（Selection Sort）

2. 快速排序（Quick Sort）

3. 堆排序（Heap Sort）

4. 希尔排序（Shell Sort）

排序算法稳定性总结表

稳定性对实际应用的影响

选择排序算法的依据

布隆过滤器介绍

布隆过滤器（Bloom Filter）简介

布隆过滤器的基本原理

布隆过滤器的特性

布隆过滤器的构造与公式

误报率公式

优化哈希函数的数量

优缺点

优点：

缺点：

常见应用场景

代码实现（C++ 示例）

示例运行

扩展

总结

为什么不用布隆过滤器

1. 误报问题

2. 不支持删除

3. 空间使用效率并非总是最优

4. 依赖哈希函数质量

5. 数据重建成本高

6. 对误报率要求严格的场景

7. 不适用于大范围动态数据

8. 无法获取元素本身

总结：什么时候不用布隆过滤器

布隆过滤器的适用场景

树的深度和高度。能否都在一个dfs里面呢？

深度和高度的定义

DFS 中同时计算深度和高度

C++ 实现

代码解析

时间与空间复杂度

运行结果

输入：

输出：

总结

热门标签