链表（Linked List）的基本概念链表是一种常见的数据结构，它由一系列节点（Node）组成。每个节点包含两部分：数据部分和指向下一个节点的指针（Pointer）。链表通过这些指针将节点按顺序连接在一起。 链表的类型 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。 双链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。 循环链表（Circular Linked List）：单链表或双链表的最后一个节点的指针又指向了链表的头节点，形成一个环形结构。 链表的基本操作 创建链表：首先创建头节点（Head Node），然后逐个添加后续节点。 插入节点 在头部插入：创建新节点，将新节点的指针指向原头节点，然后更新头节点为新节点。 在中间插入：找到要插入位置的前一个节点，创建新节点，将新节点的指针指向插入位置的节点，然后将前一个节点的指针指向新节点。 在尾部插入：找到链表的尾节点，创建新节点，将尾节点的指针指向新节点，并将新节点的指针设为 None。 删除节点 删除头节点：将头节点指向下一个节 ...

哈希表（Hash Table）的基本概念哈希表是一种数据结构，它可以在平均情况下提供非常快速的插入、删除和查找操作。其基本思想是通过一个哈希函数将键（key）映射到一个特定的索引（index），然后将对应的值（value）存储在该索引位置。 哈希函数（Hash Function） 哈希函数是哈希表的核心，它将输入的键转换为数组的索引。例如，对于一个简单的整数键的哈希函数可以是hash(key) = key % array_size，这里array_size是存储数据的数组的大小。 一个好的哈希函数应该尽量减少冲突（Collision），即不同的键被映射到相同的索引位置。常见的哈希函数构造方法包括直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法等。 处理冲突（Collision Resolution） 链地址法（Chaining）：当发生冲突时，在该索引位置创建一个链表，将新元素添加到链表中。这种方法简单且易于实现，但在最坏情况下，查找时间可能会退化到O(n)，其中n是链表的长度。 开放定址法（Open Addressing）：当发生冲突时，按照某种规则在哈希表中寻找下 ...

栈（Stack）的基本概念栈是一种重要的数据结构，它具有后进先出（Last In First Out，LIFO）的特点。可以把栈想象成一叠盘子，最后放上去的盘子会最先被拿走。 栈的基本操作 入栈（Push）：将元素添加到栈的顶部。 出栈（Pop）：从栈的顶部移除一个元素。 查看栈顶元素（Peek 或 Top）：获取栈顶元素的值，但不移除它。 判断栈是否为空（IsEmpty）：检查栈中是否有元素。 栈的应用场景 表达式求值：在算术表达式求值中，栈可以用于处理运算符的优先级和括号的匹配。例如，将中缀表达式转换为后缀表达式，然后利用栈进行求值。 函数调用栈：在程序执行过程中，当一个函数调用另一个函数时，当前函数的执行状态会被保存到一个栈中（函数调用栈）。当被调用函数执行完毕后，从栈中恢复上一个函数的执行状态继续执行。 括号匹配：在编译器和文本编辑器中，栈可以用于检查括号是否匹配。例如，在检查一段代码或者一个数学表达式中的括号是否成对出现且匹配正确时。 撤销（Undo）操作：在许多软件应用中，撤销操作可以通过栈来实现。每次执行一个操作，该操作的信息被压入栈中。当需要撤销时，从栈中弹出最近的 ...

队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO - First In First Out）的原则。 队列的基本操作 入队（Enqueue）：在队列的尾部添加一个元素。 出队（Dequeue）：从队列的头部移除一个元素。 查看队首元素（Peek）：获取队列头部的元素，但不移除它。 判断队列是否为空（IsEmpty）：检查队列中是否有元素。 队列的应用场景 广度优先搜索（BFS）：在图的广度优先搜索算法中，队列用于存储待访问的节点。 任务调度：操作系统中的任务调度，例如按照先来先服务的原则处理进程。 消息传递系统：在消息队列中间件中，消息按照发送的先后顺序排队等待接收者处理。 Python中的queue模块在 Python 中，queue模块提供了同步的队列类，这些队列类可用于在多线程编程中安全地传递数据。以下是queue模块中主要的队列类及其基本用法： Queue类 Queue类实现了一个基本的先进先出（FIFO）队列。 12345678910111213141516171819>>> import queue>>> q = ...

前缀树（Trie）简介前缀树，也称为字典树，是一种树形数据结构。它的核心思想是利用字符串的公共前缀来减少存储空间和提高查询效率。它由节点组成，每个节点包含多个指向子节点的指针（通常是一个固定大小的数组或者是一个哈希表），以及一个标记位用于表示从根节点到该节点是否构成一个完整的字符串。 工作原理 插入操作 从根节点开始，对于要插入的字符串中的每个字符，检查当前节点是否存在与该字符对应的子节点。 如果不存在，则创建一个新的子节点；如果存在，则沿着对应的子节点继续处理下一个字符。 当处理完字符串的最后一个字符后，将最后到达的节点的标记位置为表示一个完整字符串的结束。 查询操作 同样从根节点开始，按照待查询字符串的字符顺序依次在树中查找对应的子节点。 如果在某一步找不到对应的子节点，则说明该字符串不存在于树中；如果能顺利找到最后一个字符对应的节点且该节点的标记位表示是一个完整字符串的结束，那么说明该字符串存在于树中。 删除操作（相对复杂） 首先要找到要删除的字符串对应的节点路径。 如果该节点是其他字符串的中间节点，则不能直接删除，而是要清除该节点上表示字符串结束的标记位。 如果 ...

堆的定义堆（Heap）是一种特殊的树形数据结构，通常是一个完全二叉树。在堆中，每个节点都满足堆的性质： 最大堆：父节点的值大于或等于其所有子节点的值。例如，在最大堆中，根节点是整个堆中的最大值。 最小堆：父节点的值小于或等于其所有子节点的值。在最小堆中，根节点是整个堆中的最小值。 堆的存储堆通常使用数组来实现存储。对于完全二叉树，假设根节点存储在数组索引为 0 的位置，对于任意节点存储在数组索引为 i 的位置： 它的左子节点存储在数组索引为 2 * i + 1 的位置。 它的右子节点存储在数组索引为 2 * i + 2 的位置。 它的父节点存储在数组索引为 (i - 1) // 2 的位置（向下取整）。 堆的基本操作 插入元素： 先将新元素添加到堆的末尾（数组的最后一个位置）。 然后将新元素与其父节点进行比较，如果不满足堆的性质，则与父节点交换位置。 重复这个过程，直到新元素满足堆的性质或者到达根节点。 删除元素： 在最大堆中，删除操作通常是删除根节点（最大值）。将根节点与堆的最后一个元素交换位置，然后删除最后一个元素。 新的根节点可能不满足堆的性质，需要将其与子节 ...

二叉树的遍历 按照根节点的访问顺序分为前序、中序和后序遍历 遍历二叉树的时间复杂度为O(n)，空间复杂度为O(h) 二叉树剪枝：https://leetcode.cn/problems/pOCWxh/ 12345678910class Solution: def pruneTree(self, root: TreeNode) -> TreeNode: if root is None: return None root.left = self.pruneTree(root.left) root.right = self.pruneTree(root.right) if root.left is None and root.right is None and root.val == 0: return None else: return root 序列化与反序列化二叉树: 12345678910111213141516171819 ...

二分搜索算法的基本思想是：每次比较中间元素与目标元素，如果相等则找到；如果中间元素小于目标元素，则在右半部分继续搜索；如果中间元素大于目标元素，则在左半部分继续搜索。这个过程不断重复，直到找到目标元素或者搜索区间为空。 1234567891011121314151617181920def biSearch(nums, target, start, end): if start == end: if target > nums[end]: return end + 1 if target < nums[start]: return start return start if start == end - 1 and nums[start] < target < nums[end]: return end middle = (start + end) // 2 if nums[middle] == target: return m ...

计数法排序 适用于数值范围比较小的情形 时间复杂度为O(n + k) 空间复杂度为O(k) 12345678910111213141516class Solution: def sortArray(self, nums: List[int]) -> List[int]: minNum = nums[0] maxNum = nums[0] for n in nums: minNum = min(minNum, n) maxNum = max(maxNum, n) count = [0 for _ in range(maxNum - minNum + 1)] for n in nums: count[n - minNum] += 1 res = [] for i, c in enumerate(count): while c > 0: res.append( ...

回溯法回溯法是一种搜索算法，常用于解决组合优化问题和枚举问题等。以下是关于回溯法的详细介绍： 基本概念 解空间：回溯法通常用于求解问题的所有可能解，这些解构成一个解空间。解空间可以用树或图的结构来表示，其中每个节点代表一个部分解。 约束条件条件：在搜索解空间的过程中，需要根据问题的约束条件来判断一个部分解是否有可能扩展为一个完整的可行解。 递归和回溯：回溯法通常使用递归的方式来遍历解空间树。在递归的过程中，当发现当前的部分解不满足约束条件或者不可能得到更优的解时，就进行回溯，即撤销上一步的选择，尝试其他的选择。 算法步骤 定义问题的解空间：确定问题的解可以表示为什么形式，以及所有可能的解构成的空间结构。 确定状态空间树的结构：根据问题的特点构建状态空间树，树的节点代表问题的部分解，从根节点到叶子节点的路径代表一个完整的解。 深度优先搜索：从根节点开始，以深度优先的方式搜索状态空间树。在搜索过程中，根据约束条件判断每个节点是否可行，如果可行则继续向下搜索，否则回溯到上一层。 剪枝操作：在搜索过程中，利用约束条件进行剪枝，即剪掉那些不可能产生可行解或最优解的子树，以提高算法的效率。 记录 ...