做简单网站需要学什么软件,企业网站建设费用入哪个科目,iis7配置多个网站,福州企业名录来源地址
一 数据结构 1 堆和树之间的区别
区别就在于树是没有特定顺序的#xff0c;你需要遍历整个树才能找到特定元素#xff1b;而堆是有序的#xff0c;你可以直接找到最大#xff08;或最小#xff09;的元素。
堆#xff1a;假设你正在开发一个任务调度系统你需要遍历整个树才能找到特定元素而堆是有序的你可以直接找到最大或最小的元素。
堆假设你正在开发一个任务调度系统需要根据任务的优先级进行调度。你可以使用一个最小堆来实现任务队列将任务按照优先级插入到堆中并始终保持最小优先级的任务在堆顶部。这样每次从堆顶部取出任务时你总是能够获取到当前最高优先级的任务进行处理。
树结构计算机的文件系统通常被组织成树状结构。根目录是整个文件系统的起点每个文件夹可以包含子文件夹和文件从而形成层次结构。
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 在数组中的索引位置。
取模运算是一种数学运算它计算某个数除以另一个数的余数。在这个场景中我们使用取模运算是为了将哈希值映射到数组的有效范围内。
作用如下 均匀分布通过取模运算我们可以将哈希值均匀地映射到桶数组的各个索引位置上。这样可以避免将大部分数据集中在某几个桶中提高散列的均匀性。 确定索引位置取模运算得到的结果就是一个具体的索引位置在数组中可以直接通过该索引访问或存储元素。这样可以快速定位到对应的桶提高查找、插入、删除等操作的效率。
举个例子来说明 假设有一个桶数组长度为10即capacity10而某个 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保证了树的平衡性。查找、插入和删除操作的时间复杂度为O(logn)相较于普通二叉搜索树具有更好的性能保证。
通过保持树的平衡状态AVL树能够提供快速的查找、插入和删除操作。然而AVL树相对于普通二叉搜索树的平衡性要求更高因为它需要频繁地进行旋转操作来维持平衡。这也使得AVL树在插入和删除操作时比较耗费时间。
8 堆
也是一种二叉树 堆Heap是一种特殊的树形数据结构通常以完全二叉树的形式存在。它解决了在动态数据集中快速找到最大或最小元素的问题并且能够高效地支持插入和删除操作。
堆有两种常见的形式最大堆Max Heap和最小堆Min Heap。在最大堆中父节点的值大于或等于其子节点的值而在最小堆中父节点的值小于或等于其子节点的值。
堆解决的问题是
快速找到最大或最小元素通过使用堆可以保证根节点为最大最大堆或最小最小堆的元素。这样可以在O(1)的时间复杂度内找到最大或最小元素而不需要遍历整个数据集。高效支持插入和删除操作堆具有自平衡的性质当新元素插入或旧元素删除时堆会自动进行调整保持堆的性质。这样可以在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])# 从第 k1 个元素开始保持堆的长度为 kfor i in range(k, len(nums)):# 若当前元素大于堆顶元素则将堆顶元素出堆、当前元素入堆if nums[i] heap[0]:heapq.heappop(heap)heapq.heappush(heap, nums[i])return heap9 图 潜在好友推荐是社交网络分析中的一个常见问题图可以用来实现这个功能。下面是一种基于图的潜在好友推荐的简单实现方法 构建图将社交网络中的用户表示为图的节点用户之间的好友关系表示为图的边。每个节点可以附带用户的属性信息如兴趣、职业等。 确定目标用户选择需要推荐好友的目标用户。 寻找邻居节点从目标用户节点开始遍历其直接连接的邻居节点即其已有的好友。 排除已有好友将目标用户已有的好友从候选节点列表中排除以保证不会重复推荐已经是好友的人。 计算相似度对于剩下的候选节点计算它们与目标用户的相似度。可以使用各种相似度度量方法如共同好友数量、兴趣爱好的匹配程度等。 推荐潜在好友根据相似度评分选择相似度高的候选节点作为潜在好友推荐给目标用户。
此方法仅是一种简单的示例并且可能需要根据具体场景和需求进行改进和扩展。在实际应用中可能会考虑更复杂的算法和更多的因素如社区结构、用户行为等。同时还可以使用图相关的算法和技术来提高潜在好友推荐的准确性和效果如基于图的路径搜索、节点中心性分析等。
需要注意的是潜在好友推荐是一个复杂的问题涉及到数据隐私、算法设计等方面的考量具体实现要根据具体情况进行权衡和规划。
