文章

数据结构算法高频总结四

发表于 更新于
作者 匆匆那年 43 分钟阅读

数据结构相关，图的种类，表示方法，图有哪些经典算法+描述算法

图的种类

  1. 无向图（Undirected Graph）：
    • 边没有方向，节点 $u$ 和 vv 之间的连接用 $u-v$ 表示。
  2. 有向图（Directed Graph）：
    • 边有方向，节点 $u$ 和 $v$ 之间的连接用$ u \to v$ 表示。
  3. 带权图（Weighted Graph）：
    • 边带有权值，如表示距离、费用等。
  4. 无权图（Unweighted Graph）：
    • 边没有权值。
  5. 稠密图（Dense Graph）：
    • 边的数量接近 $n^2$（$n$ 为节点数）。
  6. 稀疏图（Sparse Graph）：
    • 边的数量远小于 $n^2$。
  7. 连通图（Connected Graph）：
    • 无向图中，任意两个节点之间都存在路径。
  8. 强连通图（Strongly Connected Graph）：
    • 有向图中，任意两个节点之间都存在双向路径。
  9. 完全图（Complete Graph）：
    • 图中任意两个节点之间都有边。
  10. 二分图（Bipartite Graph）：
    • 图的节点可以分为两个不相交的集合 $U$ 和 $V$，其中每条边的两个端点分别属于不同的集合。
  11. 树（Tree）：
    • 是一种特殊的无向图，连通且没有环。

图的表示方法

  1. 邻接矩阵（Adjacency Matrix）：

    • 使用一个 $n \times n$ 的矩阵表示图，矩阵的值表示节点之间是否有边。
    • 特点：
      • 空间复杂度：$O(n^2)$。
      • 判断两节点是否有边：$O(1)$。
      • 不适合稀疏图，浪费空间。

    示例（无向图）：

    1
2
3
4
5

    节点：0, 1, 2
邻接矩阵：
0 1 0
1 0 1
0 1 0

  2. 邻接表（Adjacency List）：

    • 每个节点存储一个链表或数组，表示与该节点相连的节点。
    • 特点：
      • 空间复杂度：$O(n + m)$（mm 为边数）。
      • 遍历某节点的邻居：$O(\text{degree})$。
      • 更适合稀疏图。

    示例（无向图）：

    1
2
3

    节点：0 -> [1]
      1 -> [0, 2]
      2 -> [1]

  3. 边集列表（Edge List）：

    • 使用一个列表存储所有的边，边由起点、终点和权值组成。
    • 特点：
      • 空间复杂度：$O(m)$。
      • 适合稠密图的边遍历。

    示例：

    1

    边列表：[(0, 1, 2), (1, 2, 3)]

图的经典算法及描述

1. 图的遍历

  • 深度优先搜索（DFS）：
    • 描述：递归或使用栈实现，从一个节点出发，沿着一条路径深入访问，直到不能继续时回溯。
    • 时间复杂度：$O(n + m)$。
    • 用途：
      • 检测连通性。
      • 判断是否有环。
  • 广度优先搜索（BFS）：
    • 描述：使用队列实现，从一个节点出发，按层逐步访问邻居节点。
    • 时间复杂度：$O(n + m)$。
    • 用途：
      • 求最短路径（无权图）。
      • 判断二分图。

2. 最小生成树（MST）

  • Kruskal 算法：
    • 描述：使用并查集，按权值升序排序边，依次加入边，避免形成环。
    • 时间复杂度：$O(m \log m)$。
    • 用途：
      • 计算最小生成树。
  • Prim 算法：
    • 描述：从一个节点开始，逐步加入权值最小的边。
    • 时间复杂度：$O(n^2) 或 O((n + m) \log n)$（使用优先队列）。
    • 用途：
      • 计算最小生成树。

3. 最短路径

  • Dijkstra 算法：
    • 描述：适用于非负权图，从起点开始，依次找到到达每个节点的最短路径。
    • 时间复杂度：$O((n + m) \log n)$（使用优先队列）。
    • 用途：
      • 计算单源最短路径。
  • Bellman-Ford 算法：
    • 描述：适用于有负权图，逐步松弛边，最多执行 $n-1$ 轮。
    • 时间复杂度：$O(nm)$。
    • 用途：
      • 计算单源最短路径。
      • 检测负环。
  • Floyd-Warshall 算法：
    • 描述：动态规划算法，适用于全源最短路径。
    • 时间复杂度：$O(n^3)$。
    • 用途：
      • 计算所有节点对之间的最短路径。

4. 拓扑排序

  • Kahn 算法：
    • 描述：基于入度，逐步移除入度为 0 的节点。
    • 时间复杂度：$O(n + m)$。
    • 用途：
      • 拓扑排序（有向无环图）。
  • DFS 拓扑排序：
    • 描述：基于 DFS 的后序遍历结果反转得到。
    • 时间复杂度：$O(n + m)$。

5. 连通性相关

  • Tarjan 算法（强连通分量）：
    • 描述：通过 DFS 记录节点的访问顺序和回溯点，划分强连通分量。
    • 时间复杂度：$O(n + m)$。
    • 用途：
      • 求强连通分量。
  • 桥和割点：
    • 描述：使用 DFS 找到图中对连通性至关重要的边和节点。
    • 时间复杂度：$O(n + m)$。

6. 网络流

  • Edmonds-Karp 算法：
    • 描述：基于 BFS 的最大流算法。
    • 时间复杂度：$O(nm^2)$。
    • 用途：
      • 计算最大流。
  • Dinic 算法：
    • 描述：分层图 + 分段流推送。
    • 时间复杂度：$O(n^2m)$。
    • 用途：
      • 计算最大流。

总结

  • 图的种类定义了图的基本性质，如是否有向、带权、稠密或稀疏等。
  • 图的表示方法选择取决于图的规模和操作需求。
  • 经典算法广泛应用于路径规划、连通性分析、网络流优化等场景，了解其适用条件和复杂度对于选择正确的算法至关重要。

求最大的k个数字

要从一个数组中找到最大的 $k$ 个数字，有多种方法可以实现，取决于数组的大小、$k$ 的大小以及对性能的需求。以下是几种常见的方法：

1. 使用最小堆（推荐）

思路

  • 使用一个大小为 $k$ 的最小堆，堆顶保存当前最大的 $k$ 个数字中的最小值。
  • 遍历数组：
    1. 如果当前数字大于堆顶数字，则将堆顶移除，并将当前数字插入堆中。
    2. 最终，堆中的 $k$ 个数字即为最大的 $k$ 个数字。

时间复杂度

  • 建堆：$O(k)$。
  • 遍历数组（每次操作堆）：$O((n-k) \log k)$。
  • 总时间复杂度：$O(n \log k)$。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <vector>
#include <queue>

std::vector<int> findTopK(const std::vector<int>& nums, int k) {
    if (nums.empty() || k <= 0) return {};

    // 定义一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 构建初始堆
    for (int i = 0; i < k; ++i) {
        minHeap.push(nums[i]);
    }

    // 遍历数组的剩余部分
    for (int i = k; i < nums.size(); ++i) {
        if (nums[i] > minHeap.top()) {
            minHeap.pop(); // 移除堆顶
            minHeap.push(nums[i]); // 插入当前数字
        }
    }

    // 将堆中的元素取出
    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }

    return result;
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4, 8, 7};
    int k = 3;

    std::vector<int> result = findTopK(nums, k);

    std::cout << "Top " << k << " largest numbers: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. 快速选择算法（类似快速排序的思想）

思路

  • 利用快速排序的分区（partition）思想，每次选定一个基准点，将数组划分为两部分：
    1. 左侧部分的数字比基准点小。
    2. 右侧部分的数字比基准点大。
  • 递归或迭代查找右侧部分，直到找到第 $k$ 大的数字所在的分区。
  • 优点：时间复杂度比堆排序更优，平均为 $O(n)$。
  • 缺点：最坏情况下（不平衡分区）时间复杂度为 $O(n^2)$。

时间复杂度

  • 平均时间复杂度：$O(n)$。
  • 最坏时间复杂度：$O(n^2)$。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left - 1;

    for (int j = left; j < right; ++j) {
        if (nums[j] > pivot) { // 注意，这里是从大到小排序
            ++i;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i + 1], nums[right]);
    return i + 1;
}

std::vector<int> quickSelect(std::vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k - 1) {
            return std::vector<int>(nums.begin(), nums.begin() + k);
        } else if (pivotIndex < k - 1) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4, 8, 7};
    int k = 3;

    std::vector<int> result = quickSelect(nums, k);

    std::cout << "Top " << k << " largest numbers: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 排序后取前 $k$ 个数字

思路

  • 将数组按照降序排序。
  • 直接返回前 $k$ 个数字。
  • 优点：简单易实现。
  • 缺点：时间复杂度较高，尤其是当 $k$ 远小于 $n$ 时，排序是不必要的开销。

时间复杂度

  • 时间复杂度：$O(n \log n)$。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

std::vector<int> sortAndSelect(const std::vector<int>& nums, int k) {
    std::vector<int> sortedNums = nums;
    std::sort(sortedNums.begin(), sortedNums.end(), std::greater<int>()); // 降序排序
    return std::vector<int>(sortedNums.begin(), sortedNums.begin() + k);
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4, 8, 7};
    int k = 3;

    std::vector<int> result = sortAndSelect(nums, k);

    std::cout << "Top " << k << " largest numbers: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

方法比较

方法时间复杂度空间复杂度适用场景
最小堆$O(n \log k)$$O(k)$$k \ll n$，需要在线性时间内找到最大的 $k$ 个数
快速选择$O(n)$（平均）$O(1)$$k$ 较小时，快速选择更快
排序后截取$O(n \log n)$$O(n)$简单易实现，适用于任何场景，但性能不是最佳

总结

  • 如果数组较大且 $k$ 较小，推荐使用 最小堆 或 快速选择算法。
  • 如果数组规模较小或对实现简单性有要求，可以使用 排序后截取 方法。
  • 快速选择 更适合性能敏感场景，但实现稍微复杂。

hash解决冲突（开放定址法、链地址法、再哈希法、建立公共溢出区），四种方法详细的过程、思路

哈希表是通过将键值映射到存储位置的方式来实现快速查找的，但当两个键映射到同一个位置时，就会发生冲突（称为哈希冲突）。为了解决冲突，常用以下四种方法：

1. 开放定址法（Open Addressing）

思路： 当冲突发生时，通过探测（或称搜索）空闲的哈希表位置，将冲突的元素存放到下一个合适的位置。

主要探测策略：

  • 线性探测（Linear Probing） 若位置 hash(key) 已被占用，则尝试 hash(key) + 1, hash(key) + 2, ... 直到找到空位。 缺点：会形成“聚集”，导致性能下降。

  • 二次探测（Quadratic Probing） 若位置 hash(key) 已被占用，则尝试 hash(key) + 1^2, hash(key) + 2^2, ...。 优点：避免了线性探测中的聚集现象。缺点：可能产生二次聚集。

  • 双重哈希（Double Hashing） 使用两个不同的哈希函数 h1(key) 和 h2(key)。当位置 h1(key) 被占用时，尝试位置：

    $h(i) = [h1(key) + i \cdot h2(key)] \mod m$

    其中，m 是表的大小。双重哈希能有效减少聚集。

优点：

  • 空间利用率高，因为数据全存在哈希表内。

缺点：

  • 删除操作复杂，因为需要避免“断链”。
  • 插入、查找的平均性能在冲突较多时会下降。

2. 链地址法（Chaining）

思路： 每个哈希表的槽位存储一个指针，指向一个链表。所有映射到同一槽位的键值对存储在这个链表中。

具体过程：

  1. 计算键值的哈希值，定位到哈希表的槽位。
  2. 如果槽位为空，则在该槽位创建一个链表，并将新键值对插入其中。
  3. 如果槽位已被占用（链表不为空），将新键值对添加到链表的头部或尾部。

优点：

  • 解决冲突非常灵活，冲突的元素直接链在一起。
  • 插入和删除操作相对简单。

缺点：

  • 在链表很长时，查找性能会下降。
  • 链表需要额外的指针存储空间。

3. 再哈希法（Rehashing）

思路： 如果发生冲突，使用一个新的哈希函数重新计算键值的哈希值，直到找到一个未被占用的位置。

具体过程：

  1. 计算初始哈希值 h1(key)。
  2. 如果槽位被占用，则计算新的哈希值 h2(key)。
  3. 依次尝试 h(i) = h1(key) + i \cdot h2(key) % m。

特点：

  • 再哈希法类似于双重哈希，但重点在于不断切换哈希函数。
  • 再哈希法的效果取决于哈希函数的设计和种类。

优点：

  • 在冲突发生时增加了更多随机性，有效减少聚集现象。

缺点：

  • 实现复杂，且需要维护多个哈希函数。
  • 在哈希函数选择不当时可能效率较低。

4. 建立公共溢出区（Overflow Area）

思路： 为哈希表分配一个固定的溢出区，所有发生冲突的数据都存储在这个溢出区中。

具体过程：

  1. 计算键值的哈希值，定位到哈希表槽位。
  2. 如果槽位为空，则将数据存入该槽位。
  3. 如果槽位已被占用，将冲突的数据存储到溢出区。
  4. 查找时，首先查找主哈希表，未找到时查溢出区。

优点：

  • 实现简单，避免复杂的冲突处理策略。
  • 主哈希表的数据保持较紧凑。

缺点：

  • 溢出区可能成为性能瓶颈（类似于链地址法的长链表问题）。
  • 溢出区需要额外的存储空间。

总结对比

方法优点缺点适用场景
开放定址法无需额外空间，数据全部存在哈希表内插入、删除复杂，性能下降严重空间有限且冲突少的场景
链地址法灵活性高，冲突影响较小链表需要额外存储空间，链表过长影响性能冲突概率高的场景
再哈希法增加随机性，减少聚集现象需要多个哈希函数，设计较复杂哈希函数设计合理的场景
公共溢出区实现简单，避免复杂冲突处理策略溢出区性能瓶颈冲突频繁但有额外存储空间

选择方法时需根据哈希表的大小、冲突概率、性能需求等综合考虑。

链地址法和再哈希法之间的关联和区别，两者分别使用场景，两者底层的数据结构，关联和区别

链地址法和再哈希法都是解决哈希冲突的经典方法，但它们的实现方式和适用场景存在显著差异。以下是详细分析：

1. 链地址法

底层数据结构

  • 每个哈希槽位维护一个链表或类似的动态数据结构（如动态数组）。
  • 所有冲突的元素存储在对应槽位的链表中。

实现思路

  1. 使用一个主哈希函数计算键值对应的槽位。
  2. 如果槽位已被占用，将冲突的键值对插入到链表中。

特点

  • 空间利用：链表的长度理论上无限制，只需额外的指针或动态存储空间。
  • 插入效率：平均时间复杂度 $O(1)$（假设哈希函数均匀分布）。
  • 查找效率：平均时间复杂度 $O(1 + \alpha)$，其中 $\alpha = \frac{n}{m}$（负载因子，n 为总元素数，m 为槽位数）。
  • 删除效率：简单且高效，只需在链表中操作。
  • 适用场景：数据量大且冲突概率较高时效果较好，因为链表的动态扩展能力强。

2. 再哈希法

底层数据结构

  • 使用一个固定大小的数组作为哈希表。
  • 冲突时通过多个不同的哈希函数依次探测下一个位置。

实现思路

  1. 使用第一个哈希函数计算键值的初始槽位。
  2. 如果槽位被占用，则使用第二个哈希函数重新计算新的槽位。
  3. 重复此过程，直到找到空闲槽位。

特点

  • 空间利用：数据全部存储在哈希表中，不需要额外空间。
  • 插入效率：依赖探测次数，最坏情况下可能退化为 $O(n)$。
  • 查找效率：依赖哈希函数分布，平均时间复杂度 $O(1)$。
  • 删除效率：较为复杂，可能需要标记删除位以维持连续性。
  • 适用场景：数据量较小、冲突概率低且需要高空间利用率时效果较好。

3. 链接与关联

  • 共同点：
    1. 都用于解决哈希冲突。
    2. 都依赖哈希函数的分布均匀性来保证性能。
    3. 查找和插入效率都与负载因子 $\alpha$ 有关，负载因子越高，效率越低。
  • 不同点：
比较项链地址法再哈希法
数据存储方式哈希槽位存储链表或动态结构的头指针数据存储在固定大小的哈希表中
空间利用率需要额外的链表存储空间空间利用率较高
插入冲突处理将冲突元素插入链表使用另一哈希函数计算新位置
查找性能与链表长度成正比与探测次数成正比
删除复杂度简单，直接删除链表节点较复杂，需要维护哈希表连续性
适用场景数据量大，冲突概率高数据量小，冲突概率低

4. 适用场景

链地址法

  • 场景特点：
    • 哈希表负载较高（即负载因子 $\alpha > 0.5$）。
    • 数据量较大，可能发生较多冲突。
    • 哈希函数分布可能不够均匀。
  • 典型应用：
    • 数据库中的键值存储。
    • 高负载的缓存系统。

再哈希法

  • 场景特点：
    • 哈希表负载较低（即负载因子 $\alpha < 0.5$）。
    • 数据量较小，冲突概率较低。
    • 空间资源有限，要求较高的空间利用率。
  • 典型应用：
    • 小型嵌入式系统。
    • 内存受限的应用场景。

5. 总结关联和区别

方面链地址法再哈希法
冲突解决使用链表存储冲突元素通过多次哈希计算重新定位
空间效率较低，需要链表额外空间较高，所有数据存储在表内
时间效率随链表长度增加，可能降低冲突多时探测时间增加
实现复杂度简单，链表操作易实现较复杂，需要维护多个哈希函数
删除操作高效复杂，需要标记或重哈希

链地址法适合冲突频繁的大数据场景，而再哈希法适合小型数据量、低冲突场景。两者在实际应用中常根据具体需求和资源限制来选择。

链表和数组的底层结构设计、关联、区别、应用场景

链表和数组是两种最基本的数据结构，它们在底层设计、操作特性和适用场景上各有优劣。

1. 底层结构设计

数组（Array）

  • 内存布局：
    • 数组是连续内存块。
    • 元素通过索引直接访问，地址计算公式：address = base_address + index * size_of_element。
  • 特性：
    • 静态数组：大小固定，在创建时确定。
    • 动态数组（如 std::vector）：在需要扩容时，分配新的更大内存，并将原数据拷贝到新内存中。
    • 操作简单，随机访问效率高。

链表（Linked List）

  • 内存布局：
    • 链表是由多个节点组成，节点在内存中分布不连续。
    • 每个节点包含：
      • 数据域：存储实际数据。
      • 指针域：指向下一个节点的地址（对于单链表）。
  • 类型：
    • 单链表：每个节点有一个指针指向下一个节点。
    • 双链表：每个节点有两个指针，分别指向前后节点。
    • 循环链表：链表尾节点指向链表头节点。

2. 关联性

链表和数组可以看作是两种存储线性数据的方式，它们的关联体现在以下几点：

  1. 逻辑结构：
    • 两者都存储线性数据，数据之间有前后顺序。
  2. 转换：
    • 数组可以通过遍历转化为链表，链表通过动态分配实现。
  3. 动态数组与链表的交集：
    • 动态数组在扩容时实现了链表的部分动态特性。
  4. 实现栈和队列：
    • 数组和链表都可作为栈和队列的底层数据结构。

3. 区别

方面数组（Array）链表（Linked List）
内存布局连续分布，分配一块固定大小的内存分布不连续，每个节点动态分配内存
访问方式通过索引随机访问，时间复杂度 $O(1)$通过遍历节点顺序访问，时间复杂度 $O(n)$
插入效率在数组中间插入需要移动大量元素，时间复杂度 $O(n)$插入操作只需调整指针，时间复杂度 $O(1)$
删除效率删除中间元素需要移动后续元素，时间复杂度 $O(n)$删除操作只需调整指针，时间复杂度 $O(1)$
扩展能力静态数组不能扩展，动态数组扩展需重新分配内存动态分配内存，无需重新分配
空间利用率需要连续大块内存，可能浪费部分空间每个节点需要额外存储指针，空间利用率较低
遍历性能遍历性能较高，适合顺序访问遍历性能较低，尤其是双链表
实现复杂度实现简单，操作直接实现复杂，需要维护指针和动态内存分配

4. 应用场景

数组的应用场景

  1. 快速随机访问：
    • 适合频繁的查找操作，如实现哈希表的底层存储。
  2. 大小已知，数据固定：
    • 适合操作系统中堆栈的实现。
  3. 少量插入和删除：
    • 在需要大量查询的场景，如缓存系统、排名系统。

链表的应用场景

  1. 频繁插入和删除：
    • 适合数据动态变化的场景，如队列、内存管理器的空闲块链表。
  2. 未知大小或动态增长：
    • 数据大小未知或不断扩展，如实现链式队列、链式栈。
  3. 需要灵活结构：
    • 适合实现图的邻接表或动态分配的数据结构。

5. 总结

数据结构优点缺点适用场景
数组随机访问快，结构简单插入、删除慢，内存分配固定频繁查找、大小已知、数据稳定
链表插入、删除快，动态扩展灵活随机访问慢，指针额外占用空间频繁插入删除、数据动态增长
  • 选择关键：根据具体需求决定。需要高效随机访问时选数组，需要高效插入删除时选链表。

大数问题

在C++中解决大数问题时，通常会遇到整数超出内置数据类型（如 int 或 long long）范围的情况。常用方法是通过字符串模拟大数的运算，例如实现大数的加法、减法、乘法和除法。以下是实现大数加法和乘法的完整代码与详细过程：

大数加法

大数加法通过字符串逐位相加模拟实现。关键点包括从最低位开始逐位相加，并处理进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <string>
#include <algorithm>

std::string addBigNumbers(const std::string &num1, const std::string &num2) {
    std::string result = "";
    int carry = 0; // 进位
    int len1 = num1.size(), len2 = num2.size();
    int i = len1 - 1, j = len2 - 1;

    while (i >= 0 || j >= 0 || carry) {
        int digit1 = (i >= 0) ? num1[i--] - '0' : 0;
        int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
        int sum = digit1 + digit2 + carry;
        carry = sum / 10; // 更新进位
        result += (sum % 10) + '0'; // 当前位的结果
    }

    std::reverse(result.begin(), result.end()); // 结果需要反转
    return result;
}

int main() {
    std::string num1, num2;
    std::cout << "输入两个大数：" << std::endl;
    std::cin >> num1 >> num2;

    std::string result = addBigNumbers(num1, num2);
    std::cout << "大数加法结果：" << result << std::endl;

    return 0;
}

大数乘法

大数乘法通过模拟手工乘法的方式实现，每一位与另一位相乘后叠加到结果中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

std::string multiplyBigNumbers(const std::string &num1, const std::string &num2) {
    int len1 = num1.size(), len2 = num2.size();
    std::vector<int> result(len1 + len2, 0);

    for (int i = len1 - 1; i >= 0; --i) {
        for (int j = len2 - 1; j >= 0; --j) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];

            result[i + j + 1] = sum % 10; // 更新当前位
            result[i + j] += sum / 10;   // 处理进位
        }
    }

    // 将结果转换为字符串
    std::string product;
    for (int num : result) {
        if (!(product.empty() && num == 0)) { // 跳过前导零
            product += num + '0';
        }
    }

    return product.empty() ? "0" : product;
}

int main() {
    std::string num1, num2;
    std::cout << "输入两个大数：" << std::endl;
    std::cin >> num1 >> num2;

    std::string result = multiplyBigNumbers(num1, num2);
    std::cout << "大数乘法结果：" << result << std::endl;

    return 0;
}

大数减法

实现大数减法时，需要考虑两个数字的大小关系以决定结果的正负号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <string>
#include <algorithm>

std::string subtractBigNumbers(const std::string &num1, const std::string &num2) {
    // 判断正负
    bool negative = false;
    std::string n1 = num1, n2 = num2;
    if (num1 < num2) {
        std::swap(n1, n2);
        negative = true;
    }

    std::string result = "";
    int len1 = n1.size(), len2 = n2.size();
    int carry = 0;

    for (int i = 0; i < len1; ++i) {
        int digit1 = n1[len1 - 1 - i] - '0';
        int digit2 = (i < len2) ? n2[len2 - 1 - i] - '0' : 0;

        int diff = digit1 - digit2 - carry;
        if (diff < 0) {
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }

        result += diff + '0';
    }

    while (result.size() > 1 && result.back() == '0') {
        result.pop_back(); // 去掉前导零
    }

    std::reverse(result.begin(), result.end());
    return (negative ? "-" : "") + result;
}

int main() {
    std::string num1, num2;
    std::cout << "输入两个大数 (num1 - num2):" << std::endl;
    std::cin >> num1 >> num2;

    std::string result = subtractBigNumbers(num1, num2);
    std::cout << "大数减法结果：" << result << std::endl;

    return 0;
}

大数除法

大数除法通过模拟手工除法逐位计算商，关键是维护当前的余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <string>
#include <algorithm>

std::string divideBigNumbers(const std::string &num1, const std::string &num2) {
    if (num2 == "0") {
        return "Error: Division by zero";
    }

    std::string result = "";
    std::string remainder = "0";

    for (char digit : num1) {
        remainder += digit; // 将当前位加入余数
        while (remainder.size() > 1 && remainder[0] == '0') {
            remainder.erase(remainder.begin()); // 去掉前导零
        }

        int quotient = 0;
        while (std::stoll(remainder) >= std::stoll(num2)) {
            remainder = subtractBigNumbers(remainder, num2);
            ++quotient;
        }

        result += quotient + '0';
    }

    while (result.size() > 1 && result[0] == '0') {
        result.erase(result.begin()); // 去掉前导零
    }

    return result.empty() ? "0" : result;
}

int main() {
    std::string num1, num2;
    std::cout << "输入两个大数 (num1 / num2):" << std::endl;
    std::cin >> num1 >> num2;

    std::string result = divideBigNumbers(num1, num2);
    std::cout << "大数除法结果：" << result << std::endl;

    return 0;
}

大数阶乘

阶乘涉及的数字迅速变大，需要使用大数加法和乘法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <string>
#include <vector>

std::string multiplyBigNumbers(const std::string &num1, const std::string &num2);

std::string factorial(int n) {
    std::string result = "1";
    for (int i = 2; i <= n; ++i) {
        result = multiplyBigNumbers(result, std::to_string(i));
    }
    return result;
}

std::string multiplyBigNumbers(const std::string &num1, const std::string &num2) {
    int len1 = num1.size(), len2 = num2.size();
    std::vector<int> result(len1 + len2, 0);

    for (int i = len1 - 1; i >= 0; --i) {
        for (int j = len2 - 1; j >= 0; --j) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];

            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }

    std::string product;
    for (int num : result) {
        if (!(product.empty() && num == 0)) {
            product += num + '0';
        }
    }

    return product.empty() ? "0" : product;
}

int main() {
    int n;
    std::cout << "输入一个整数 n 计算 n!：" << std::endl;
    std::cin >> n;

    std::string result = factorial(n);
    std::cout << n << "! 的结果是：" << result << std::endl;

    return 0;
}

大数幂乘

幂乘是重复乘法的过程，可以用快速幂优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <string>

std::string multiplyBigNumbers(const std::string &num1, const std::string &num2);

std::string powerBigNumbers(const std::string &base, int exponent) {
    std::string result = "1";
    std::string currentBase = base;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = multiplyBigNumbers(result, currentBase);
        }
        currentBase = multiplyBigNumbers(currentBase, currentBase);
        exponent /= 2;
    }

    return result;
}

std::string multiplyBigNumbers(const std::string &num1, const std::string &num2) {
    int len1 = num1.size(), len2 = num2.size();
    std::vector<int> result(len1 + len2, 0);

    for (int i = len1 - 1; i >= 0; --i) {
        for (int j = len2 - 1; j >= 0; --j) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];

            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }

    std::string product;
    for (int num : result) {
        if (!(product.empty() && num == 0)) {
            product += num + '0';
        }
    }

    return product.empty() ? "0" : product;
}

int main() {
    std::string base;
    int exponent;
    std::cout << "输入一个大数和指数 (base^exponent):" << std::endl;
    std::cin >> base >> exponent;

    std::string result = powerBigNumbers(base, exponent);
    std::cout << base << "^" << exponent << " 的结果是：" << result << std::endl;

    return 0;
}
数据结构算法, 数据结构算法面经
数据结构算法 面经
本文由作者按照 CC BY 4.0 进行授权