数据结构部分

来源地址

一 数据结构

1 堆和树之间的区别

区别就在于树是没有特定顺序的，你需要遍历整个树才能找到特定元素；而堆是有序的，你可以直接找到最大（或最小）的元素。

堆：假设你正在开发一个任务调度系统，需要根据任务的优先级进行调度。你可以使用一个最小堆来实现任务队列，将任务按照优先级插入到堆中，并始终保持最小优先级的任务在堆顶部。这样，每次从堆顶部取出任务时，你总是能够获取到当前最高优先级的任务进行处理。

树结构：计算机的文件系统通常被组织成树状结构。根目录是整个文件系统的起点，每个文件夹可以包含子文件夹和文件，从而形成层次结构。

2 所有数据结构都是基于数组、链表或二者的组合实现的

基于数组实现的数据结构也称“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构也称“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。

3 基本数据类型

就是整数，浮点，字符，布尔类型：基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1 比特。在绝大多数现代操作系统中，1 字节（byte）由 8 比特（bit）组成。

基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。例如以下代码，我们用相同的数据结构（数组）来存储与表示不同的基本数据类型，包括 int、float、char、bool 等。

4 列表=“动态数组”

5 双向队列

在队列中，我们仅能删除头部元素或在尾部添加元素。如图 5-7 所示，「双向队列 double-ended queue」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

双向列表的应用

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。

6 哈希表 = 散列表

我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value，实现高效的元素查询

1）哈希表的简单实现，仅用数组

在哈希算法中，将哈希值对桶数量（数组的长度）capacity 取模，是为了确定该 key 在数组中的索引位置。

取模运算是一种数学运算，它计算某个数除以另一个数的余数。在这个场景中，我们使用取模运算是为了将哈希值映射到数组的有效范围内。

作用如下：

1. 均匀分布：通过取模运算，我们可以将哈希值均匀地映射到桶数组的各个索引位置上。这样可以避免将大部分数据集中在某几个桶中，提高散列的均匀性。

2. 确定索引位置：取模运算得到的结果就是一个具体的索引位置，在数组中可以直接通过该索引访问或存储元素。这样可以快速定位到对应的桶，提高查找、插入、删除等操作的效率。

举个例子来说明：
假设有一个桶数组，长度为10（即capacity=10），而某个 key 经过哈希函数计算后得到的哈希值为 27。如果我们直接将哈希值作为索引，那么该 key 对应的索引位置就超出了数组的长度。但如果我们对容量取模（27 % 10），则得到的结果为 7，表示该 key 应该放在数组的第 7 个位置上。

所以，对容量取模可以将哈希值映射到合适的索引位置，确保数据分布均匀且能够准确定位到对应的桶。

2）哈希冲突

两key对应一个值了，这时候就需要扩容哈希表
「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75时，系统会将哈希表扩容至原先的 2倍。

哈希表的存储可能如下所示：
桶1: 空
桶2: 学生A, 85
桶3: 学生B, 92
桶4: 空
桶5: 学生C, 78
桶6: 空
桶7: 空
桶8: 空
桶9: 空
桶10: 空

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

1、改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
2、仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。
哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

开放寻址有三法

7 树

二叉树的基本单元是节点，每个节点（父节点）包含值、左子节点引用（指针）和右子节点引用。

插入和删除节点

遍历

前序遍历首先访问根节点，然后递归地遍历左子树和右子树
中序遍历先遍历左子树，然后访问根节点，最后遍历右子树
后序遍历先遍历左子树，然后遍历右子树，最后访问根节点

二叉搜索树

查找节点

从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

插入节点

也是先查找能插入节点的位置

删

AVL树

AVL树是一种自平衡二叉搜索树，它解决了普通二叉搜索树可能出现的性能问题。普通二叉搜索树在插入、删除操作频繁时，可能会变得不平衡，导致查找、插入、删除等操作的时间复杂度从O(logn)退化到O(n)，严重影响了性能。

AVL树通过引入平衡因子（balance factor）来保持树的平衡状态。每个节点都有一个平衡因子，用来表示左子树和右子树的高度差。平衡因子可以为-1、0或1。当插入或删除节点后，AVL树会通过旋转操作，即左旋和右旋，来重新调整树的结构，使得每个节点的平衡因子保持在[-1, 0, 1]的范围内。

AVL树的特点如下：

1. 每个节点的左子树和右子树的高度差最多为1，保证了树的平衡性。
2. 查找、插入和删除操作的时间复杂度为O(logn)，相较于普通二叉搜索树具有更好的性能保证。

通过保持树的平衡状态，AVL树能够提供快速的查找、插入和删除操作。然而，AVL树相对于普通二叉搜索树的平衡性要求更高，因为它需要频繁地进行旋转操作来维持平衡。这也使得AVL树在插入和删除操作时比较耗费时间。

8 堆

也是一种二叉树
堆（Heap）是一种特殊的树形数据结构，通常以完全二叉树的形式存在。它解决了在动态数据集中快速找到最大或最小元素的问题，并且能够高效地支持插入和删除操作。

堆有两种常见的形式：最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

堆解决的问题是：

1. 快速找到最大或最小元素：通过使用堆，可以保证根节点为最大（最大堆）或最小（最小堆）的元素。这样可以在O(1)的时间复杂度内找到最大或最小元素，而不需要遍历整个数据集。
2. 高效支持插入和删除操作：堆具有自平衡的性质，当新元素插入或旧元素删除时，堆会自动进行调整，保持堆的性质。这样可以在O(logn)的时间复杂度内完成插入和删除操作，相较于其他排序或搜索算法更高效。

Top-k问题，选择堆是因为它的时间复杂度最小

def top_k_heap(nums: list[int], k: int) -> list[int]:
    """基于堆查找数组中最大的 k 个元素"""
    # 初始化小顶堆
    heap = []
    # 将数组的前 k 个元素入堆
    for i in range(k):
        heapq.heappush(heap, nums[i])
    # 从第 k+1 个元素开始，保持堆的长度为 k
    for i in range(k, len(nums)):
        # 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if nums[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, nums[i])
    return heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9 图

潜在好友推荐是社交网络分析中的一个常见问题，图可以用来实现这个功能。下面是一种基于图的潜在好友推荐的简单实现方法：

1. 构建图：将社交网络中的用户表示为图的节点，用户之间的好友关系表示为图的边。每个节点可以附带用户的属性信息（如兴趣、职业等）。

2. 确定目标用户：选择需要推荐好友的目标用户。

3. 寻找邻居节点：从目标用户节点开始，遍历其直接连接的邻居节点，即其已有的好友。

4. 排除已有好友：将目标用户已有的好友从候选节点列表中排除，以保证不会重复推荐已经是好友的人。

5. 计算相似度：对于剩下的候选节点，计算它们与目标用户的相似度。可以使用各种相似度度量方法，如共同好友数量、兴趣爱好的匹配程度等。

6. 推荐潜在好友：根据相似度评分，选择相似度高的候选节点作为潜在好友推荐给目标用户。

此方法仅是一种简单的示例，并且可能需要根据具体场景和需求进行改进和扩展。在实际应用中，可能会考虑更复杂的算法和更多的因素，如社区结构、用户行为等。同时，还可以使用图相关的算法和技术来提高潜在好友推荐的准确性和效果，如基于图的路径搜索、节点中心性分析等。

需要注意的是，潜在好友推荐是一个复杂的问题，涉及到数据隐私、算法设计等方面的考量，具体实现要根据具体情况进行权衡和规划。