蓝桥杯备战

2023-03-26 21:13| 来源: 网络整理| 查看: 265

一：链表

在Python中，链表可以通过定义一个节点类来实现。节点类包含两个成员变量：一个用于存储节点的值，一个用于指向下一个节点的指针

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def prepend(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def insert_after_node(self, prev_node, data): if not prev_node: print("Previous node does not exist.") return new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node def delete_node(self, key): curr_node = self.head if curr_node and curr_node.data == key: self.head = curr_node.next curr_node = None return prev_node = None while curr_node and curr_node.data != key: prev_node = curr_node curr_node = curr_node.next if curr_node is None: return prev_node.next = curr_node.next curr_node = None def print_list(self): curr_node = self.head while curr_node: print(curr_node.data) curr_node = curr_node.next

在上述示例中，Node类代表链表的节点，LinkedList类代表整个链表。LinkedList类包含了一系列方法，如append、prepend、insert_after_node、delete_node和print_list，用于对链表进行常见的操作。其中，append方法用于在链表尾部添加一个节点，prepend方法用于在链表头部添加一个节点，insert_after_node方法用于在指定节点之后插入一个节点，delete_node方法用于删除指定值的节点，print_list方法用于打印整个链表

补充：

①图的邻接表

图的邻接表是一种常见的图存储结构，它使用链表来表示图中的每个顶点及其邻接顶点。对于每个顶点，都有一个对应的链表，链表中存储了与该顶点直接相连的其他顶点。通常情况下，邻接表会存储图的所有顶点及其对应的邻接顶点。

使用邻接表可以有效地存储稀疏图，因为只需要存储每个顶点的邻接点，而不需要存储图中所有可能的边。相比于邻接矩阵，邻接表可以更加节省存储空间。

在邻接表中，每个节点包含两个主要部分：一个表示顶点本身的值（例如一个数字或一个字符串），以及一个指向该顶点的邻接链表的指针。邻接链表中的每个节点表示该顶点直接相邻的一个顶点，并包含一个指向下一个邻接节点的指针。

下面是一个简单的示例，展示了一个无向图的邻接表：

Graph: 1 ------- 2 | | | | 3 ------- 4 | | 5 Adjacency List: Vertex 1: 2 -> 3 Vertex 2: 1 -> 4 Vertex 3: 1 -> 4 -> 5 Vertex 4: 2 -> 3 Vertex 5: 3 在上面的示例中，每个顶点的邻接链表中包含了与之相邻的所有顶点，例如顶点1的邻接链表中包含了顶点2和3

具体实现：

在Python中，可以使用类来实现链表数据结构。下面是一个使用链表实现图的邻接表的示例代码：

class Node: def __init__(self, val=None): self.val = val self.next = None class Graph: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_list = [None] * num_vertices def add_edge(self, src, dest): node = Node(dest) node.next = self.adj_list[src] self.adj_list[src] = node node = Node(src) node.next = self.adj_list[dest] self.adj_list[dest] = node def print_graph(self): for i in range(self.num_vertices): print(f"Adjacency list of vertex {i}") print(f"head", end="") node = self.adj_list[i] while node: print(f" -> {node.val}", end="") node = node.next print(" \n") # Example usage g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 4) g.add_edge(1, 2) g.add_edge(1, 3) g.add_edge(1, 4) g.add_edge(2, 3) g.add_edge(3, 4) g.print_graph()

首先，定义了一个 Node 类，用于表示链表中的节点。该类包含一个 val 属性来保存节点的值，以及一个 next 属性来保存下一个节点的引用。

然后，定义了一个 Graph 类，用于表示图。在构造函数中，首先初始化了图的节点数 num_vertices，以及一个空的邻接表 adj_list，用于保存每个节点的相邻节点。

Graph 类还包含了一个 add_edge 方法，用于添加一条边。该方法接收源节点 src 和目标节点 dest 作为参数，然后创建两个节点 node，一个添加到源节点的邻接表中，另一个添加到目标节点的邻接表中。这样就能够保存每个节点的相邻节点了。

最后，Graph 类还包含了一个 print_graph 方法，用于打印邻接表。该方法遍历每个节点的邻接表，输出每个节点的相邻节点。

在示例中，首先创建了一个包含 5 个节点的图。然后使用 add_edge 方法添加了多条边，创建了一个简单的无向图。最后使用 print_graph 方法打印了邻接表的内容

②：实现哈希表

哈希表（Hash Table），也称为散列表，是一种根据关键字（Key）直接访问存储位置的数据结构。它通过将关键字映射到一个索引（Index）来实现高效的数据访问，从而可以在常数时间内（O(1)）进行插入、删除和查找操作。

哈希表的基本思想是将关键字通过哈希函数（Hash Function）转换成一个整数索引，然后将值存储在对应的索引位置上。由于哈希函数可以将不同的关键字映射到不同的索引上，所以在哈希表中进行查找时，只需要通过哈希函数计算出关键字对应的索引，然后直接访问对应位置的元素即可。

哈希表的优点在于能够实现快速的插入、删除和查找操作，具有较好的平均时间复杂度。但是哈希表的缺点在于其无法保证元素的顺序，而且哈希函数的设计和冲突处理会影响哈希表的性能。

具体实现：

class Node: def __init__(self, key, value): self.key = key self.value = value self.next = None class LinkedList: def __init__(self): self.head = None def add_node(self, key, value): new_node = Node(key, value) if not self.head: self.head = new_node else: current = self.head while current.next: current = current.next current.next = new_node def delete_node(self, key): if not self.head: return if self.head.key == key: self.head = self.head.next return current = self.head while current.next: if current.next.key == key: current.next = current.next.next return current = current.next def get_node(self, key): current = self.head while current: if current.key == key: return current.value current = current.next return None class HashTable: def __init__(self, capacity=100): self.capacity = capacity self.table = [None] * self.capacity def hash_function(self, key): return hash(key) % self.capacity def add_key_value_pair(self, key, value): index = self.hash_function(key) if not self.table[index]: self.table[index] = LinkedList() self.table[index].add_node(key, value) def delete_key(self, key): index = self.hash_function(key) if not self.table[index]: return self.table[index].delete_node(key) def get_value(self, key): index = self.hash_function(key) if not self.table[index]: return None return self.table[index].get_node(key)

Node 类定义了链表节点，包含 key 和 value 属性，以及指向下一个节点的指针 next。LinkedList 类定义了链表，包含 head 属性，表示链表头节点。它提供了添加节点、删除节点和查找节点的操作。HashTable 类定义了哈希表，包含 capacity 属性和 table 属性，capacity 表示哈希表的容量，table 是一个数组，每个元素是一个链表。它提供了哈希函数，添加键值对、删除键和查找值的操作。当哈希表中发生冲突时，它使用链表来解决冲突。

具体来说，哈希函数 hash_function 使用 Python 自带的 hash 函数来计算键的哈希值，并将其与哈希表容量取模，得到键的索引值。当添加键值对时，首先计算键的哈希值，然后将键值对插入对应索引处的链表中。当删除键时，同样需要计算键的哈希值，然后在对应索引处的链表中查找并删除对应节点。当查找值时，同样需要计算键的哈希值，然后在对应索引处的链表中查找

③：LRU缓存

LRU是Least Recently Used的缩写，意为最近最少使用。它是一种常见的缓存替换算法，用于在计算机中管理缓存空间。

当使用缓存来提高系统性能时，LRU算法可以帮助系统将最近最少使用的数据从缓存中淘汰，以便为新的数据腾出空间。该算法的基本思想是在缓存中保留最近被访问的数据，当缓存空间满时，淘汰最近最少使用的数据，以便为新数据腾出空间。

LRU算法通常使用一个链表来记录缓存中的数据访问顺序，最近被访问的数据排在链表的前面，最近最少使用的数据排在链表的后面。当缓存满时，需要淘汰最后面的数据，将新数据插入到链表的前面。

LRU算法可以提高缓存的命中率，从而提高系统性能。然而，实现LRU算法需要消耗较大的计算资源，因此需要权衡计算资源和缓存命中率之间的关系。

具体实现：

class Node: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None self.prev = None class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def add_node(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def remove_node(self, node): node.prev.next = node.next node.next.prev = node.prev def move_to_head(self, node): self.remove_node(node) self.add_node(node) def pop_tail(self): node = self.tail.prev self.remove_node(node) return node def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self.move_to_head(node) return node.value def put(self, key, value): if key in self.cache: node = self.cache[key] node.value = value self.move_to_head(node) else: node = Node(key, value) self.cache[key] = node self.add_node(node) if len(self.cache) > self.capacity: tail = self.pop_tail() del self.cache[tail.key]

这段代码使用了双向链表来存储数据，其中头节点和尾节点不存储数据。同时，我们维护了一个哈希表来保存每个节点的位置。在访问和插入操作中，我们将节点移动到链表的头部，以保证最近访问的节点总是在链表头部。当容量达到上限时，我们淘汰链表尾部的节,我们可以创建一个 LRU 缓存对象并设置容量。例如：我们可以创建一个 LRU 缓存对象并设置容量。例如：

cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) cache.get(1) # 返回 1 cache.put(3, 3) # 将键值对 (2,2) 淘汰 cache.get(2) # 返回 -1，因为缓存中已经没有键为 2 的数据 cache.put(4, 4) # 将键值对 (1,1) 淘汰 cache.get(1) # 返回 -1，因为缓存中已经没有键为 1 的数据 cache.get(3) # 返回 3 cache.get(4) # 返回 4

达到上限时，LRU 缓存淘汰了最近最少使用的节点，以便为新的节点腾出空间。

在上面的实现中，add_node() 方法用于向链表头部添加新节点，remove_node() 方法用于删除链表中的节点，move_to_head() 方法用于将一个节点移动到链表头部，pop_tail() 方法用于弹出链表尾部的节点。当添加一个新的节点时，我们将其添加到链表头部，并将其存储在哈希表中。当访问一个节点时，我们将其移动到链表头部以表示最近访问，同时返回该节点的值。当缓存达到容量上限时，我们从链表尾部删除最近最少使用的节点，并从哈希表中删除其对应的键值对。

二：队列

在Python中，可以使用 queue 模块来实现队列。queue 模块提供了三种队列类型：Queue、LifoQueue 和 PriorityQueue。

Queue 类型：先进先出队列from queue import Queue # 创建一个队列，参数为可选的最大队列长度 q = Queue(maxsize=0) # 将元素放入队列 q.put(item) # 从队列中取出元素 item = q.get() # 检查队列是否为空 q.empty() # 检查队列是否已满（只有在指定了最大队列长度时才有效） q.full() # 返回队列中的元素数 q.qsize()

2.LifoQueue 类型：后进先出队列

from queue import LifoQueue # 创建一个后进先出队列，参数为可选的最大队列长度 q = LifoQueue(maxsize=0) # 将元素放入队列 q.put(item) # 从队列中取出元素 item = q.get() # 检查队列是否为空 q.empty() # 检查队列是否已满（只有在指定了最大队列长度时才有效） q.full() # 返回队列中的元素数 q.qsize()

3.PriorityQueue 类型：带有优先级的队列

from queue import PriorityQueue # 创建一个带有优先级的队列，参数为可选的最大队列长度 q = PriorityQueue(maxsize=0) # 将元素放入队列，可以指定优先级（数字越小，优先级越高） q.put((priority, item)) # 从队列中取出元素，取出的元素是优先级最高的元素 item = q.get()[1] # 检查队列是否为空 q.empty() # 检查队列是否已满（只有在指定了最大队列长度时才有效） q.full() # 返回队列中的元素数 q.qsize()

补充：队列实现广度优先搜索

在 Python 中，我们可以使用队列数据结构来实现广度优先搜索算法。以下是使用 Python 的内置队列模块实现 BFS 算法的示例代码：

from queue import Queue def bfs(graph, start): visited = set() # 已访问节点集合 queue = Queue() # 创建一个队列 queue.put(start) # 将起始节点入队 while not queue.empty(): node = queue.get() # 取出队首节点 if node not in visited: visited.add(node) # 对当前节点进行相关操作 print(node) # 将当前节点的所有未访问过的邻居节点入队 for neighbor in graph[node]: if neighbor not in visited: queue.put(neighbor) # 示例图 graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } # 从节点 A 开始进行 BFS bfs(graph, 'A')

在这个示例代码中，我们首先定义了一个 bfs 函数来实现 BFS 算法。该函数接受两个参数：图（用字典表示）和起始节点。

在函数内部，我们创建了一个空集合 visited 用于存储已访问过的节点，以及一个队列 queue 用于存储待访问的节点。

接着，我们将起始节点 start 入队，然后进行循环。在循环中，我们从队列中取出队首节点 node，判断其是否已经被访问过。如果没有，我们将其加入到已访问集合中，并进行一些与当前节点相关的操作（这里仅打印节点的值）。

然后，我们遍历当前节点 node 的邻居节点，并将未访问过的邻居节点入队。这样，我们就完成了一个广度优先搜索的遍历过程。

需要注意的是，在这个示例代码中，我们使用了 Python 内置的队列模块 Queue 来创建队列，其实现了一个线程安全的队列。同时，我们也使用了 Python 内置的集合类型 set 来存储已访问节点的集合。

三：优先队列

Python优先队列（Priority Queue）是一种数据结构，类似于队列，但是可以按照元素的优先级进行排序和取出。元素的优先级通常由一个可以比较的关键字表示，因此可以使用Python内置的heapq模块实现。

Python优先队列可以用于很多场景，例如任务调度、贪心算法等。在任务调度中，每个任务都有一个优先级，优先级高的任务先执行；在贪心算法中，每个物品都有一个价值和重量，选择价值/重量比最高的物品先选取。

Python优先队列有两种实现方式：一种是使用heapq模块，另一种是使用queue模块中的PriorityQueue类。heapq模块实现简单，但是需要手动维护队列的顺序；PriorityQueue类实现更加方便，但是需要对元素进行封装，使其具有可比较性。

在 Python 中，可以使用 heapq 模块来实现优先队列。heapq 模块提供了一个 heappush 函数和一个 heappop 函数，可以分别用于将元素插入到优先队列中和从队列中弹出最小的元素。

以下是一个使用 heapq 实现优先队列的例子：

import heapq # 创建一个空的优先队列 pq = [] # 将元素插入到队列中 heapq.heappush(pq, 3) heapq.heappush(pq, 1) heapq.heappush(pq, 4) heapq.heappush(pq, 2) # 弹出最小的元素 print(heapq.heappop(pq)) # 输出 1 # 弹出最小的元素 print(heapq.heappop(pq)) # 输出 2

在这个例子中，我们首先创建了一个空的优先队列 pq。然后，我们使用 heappush 函数将 4 个元素插入到队列中。接下来，我们使用 heappop 函数两次从队列中弹出最小的元素，并分别输出它们的值

注意，由于 heapq 实现的是小根堆，因此队列中的元素总是按照升序排列。如果要实现大根堆，则可以在插入元素时将元素取相反数，这样最大的元素就变成了最小的元素

补充：

①优先队列实现最短路算法

这里的参数 graph 是一个字典，其键表示图中的节点，值是另一个字典，用于存储从该节点可到达的邻居节点及其权重。start 参数表示起点。该算法使用堆实现优先队列。distances 字典用于存储每个节点的距离，初始值为正无穷。堆 pq 中的元素是 (距离, 节点) 的二元组。在每次循环中，从堆中取出距离最小的节点 curr_node，如果其距离大于其它到达该节点的路径，则跳过该节点。否则，遍历其邻居节点，并计算到邻居节点的距离。如果该距离比当前存储的距离更短，则更新 distances 字典，并将邻居节点加入堆中。最终，返回 distances 字典，其中每个键表示一个节点，对应的值是起点到该节点的最短距离。

import heapq def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 pq = [(0, start)] while pq: curr_dist, curr_node = heapq.heappop(pq) if curr_dist > distances[curr_node]: continue for neighbor, weight in graph[curr_node].items(): distance = curr_dist + weight if distance 1 or len(stack) > 0: if n > 1: stack.append(n) n -= 1 else: result *= stack.pop() return result

这个函数使用一个栈来实现阶乘的递归计算。在每次循环中，我们检查当前的n值是否大于1。如果n大于1，我们将n压入栈中，并将n减1。否则，我们从栈中弹出一个数并将其乘以当前的结果。这样，我们就可以使用栈来模拟递归调用的过程，而不需要使用实际的递归函数。

②：括号匹配

def is_valid_parentheses(s: str) -> bool: stack = [] mapping = {")": "(", "}": "{", "]": "["} for c in s: if c in mapping: if not stack or mapping[c] != stack.pop(): return False else: stack.append(c) return not stack

③：表达式求值

def eval_expr(expr): # 定义运算符的优先级 priority = {'+': 1, '-': 1, '*': 2, '/': 2} # 定义运算符栈和操作数栈 op_stack = [] num_stack = [] # 将表达式字符串转换为列表 tokens = expr.split() # 遍历表达式列表 for token in tokens: # 如果是数字，压入操作数栈 if token.isdigit(): num_stack.append(int(token)) # 如果是运算符 elif token in priority: # 如果运算符栈不为空，且栈顶运算符的优先级大于等于当前运算符 while op_stack and priority[op_stack[-1]] >= priority[token]: # 从运算符栈和操作数栈中弹出两个数，进行运算，并将结果压入操作数栈 num2 = num_stack.pop() num1 = num_stack.pop() op = op_stack.pop() if op == '+': num_stack.append(num1 + num2) elif op == '-': num_stack.append(num1 - num2) elif op == '*': num_stack.append(num1 * num2) elif op == '/': num_stack.append(num1 / num2) # 将当前运算符压入运算符栈 op_stack.append(token) # 如果是左括号，压入运算符栈 elif token == '(': op_stack.append(token) # 如果是右括号，弹出运算符栈中的运算符，直到遇到左括号，并将括号中的表达式求值后压入操作数栈 elif token == ')': while op_stack[-1] != '(': num2 = num_stack.pop() num1 = num_stack.pop() op = op_stack.pop() if op == '+': num_stack.append(num1 + num2) elif op == '-': num_stack.append(num1 - num2) elif op == '*': num_stack.append(num1 * num2) elif op == '/': num_stack.append(num1 / num2) op_stack.pop() # 弹出左括号 # 处理剩余的运算符 while op_stack: num2 = num_stack.pop() num1 = num_stack.pop() op = op_stack.pop() if op == '+': num_stack.append(num1 + num2) elif op == '-': num_stack.append(num1 - num2) elif op == '*': num_stack.append(num1 * num2) elif op == '/': num_stack.append(num1 / num2) # 返回最终结果 return num_stack.pop()

在上述代码中，我们定义了两个栈：运算符栈和操作数栈。遍历表达式字符串时，如果是数字，就将其压入操作数栈；如果是运算符，就比较其优先级，并根据情况从操作数栈和运算符栈中弹出数值和运算符进行计算，最后将计算结果压入操作数栈；如果是左括号，就将其压入运算符栈；如果是右括号，就弹出运算符栈中的运算符，直到遇到左括号，并将括号中的表达式求值后压入操作数栈。最后，将剩余的运算符和操作数进行计算，直到操作数栈中只剩下一个数值，即为表达式的求值结果。

下面是一个例子，演示如何使用上述代码计算一个简单的中缀表达式：

expr = '3 + 4 * 2 / ( 1 - 5 )' result = eval_expr(expr) print(result) # 输出结果为 -5.0

在上述例子中，我们计算了表达式3 + 4 * 2 / ( 1 - 5 )的值，最终结果为-5.0。

五：哈希

在 Python 中，哈希（Hash）是一种用于加密、数据结构等方面的重要算法。哈希函数可以将任意长度的消息转换为固定长度的哈希值（也称为散列值或摘要），通常用于数据的唯一标识和加密。

Python中内置的哈希函数有很多种，其中最常用的是 hash() 函数。hash() 函数可以接受任何可哈希对象作为参数，例如数字、字符串、元组等不可变类型的对象。哈希函数的返回值是一个整数，该整数可以作为对象的哈希值使用。

以下是一些示例代码，展示了 Python 中哈希的基本用法：

# 使用hash函数计算数字的哈希值 print(hash(123)) # 输出：123 # 使用hash函数计算字符串的哈希值 print(hash('hello world')) # 输出：-1324515428312633404 # 使用hash函数计算元组的哈希值 print(hash((1, 2, 3))) # 输出：529344067295497451

需要注意的是，哈希函数的返回值并不是唯一的，因此不同的对象可能会有相同的哈希值。此外，可变类型的对象（例如列表和字典）不能被哈希，因为它们的值可以更改，因此不能用于数据结构中需要唯一标识的情况。

六：二叉树

在 Python 中，可以使用类和对象来实现二叉树数据结构。以下是一个基本的二叉树类示例：

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None def insert_left(self, value): if self.left_child is None: self.left_child = BinaryTree(value) else: new_node = BinaryTree(value) new_node.left_child = self.left_child self.left_child = new_node def insert_right(self, value): if self.right_child is None: self.right_child = BinaryTree(value) else: new_node = BinaryTree(value) new_node.right_child = self.right_child self.right_child = new_node def get_left_child(self): return self.left_child def get_right_child(self): return self.right_child def set_root_value(self, value): self.value = value def get_root_value(self): return self.value

补充：

①：二叉搜索树(BST）

class TreeNode: def __init__(self, val=None, left=None, right=None): self.val = val self.left = left self.right = right class BST: def __init__(self): self.root = None def insert(self, val): if not self.root: self.root = TreeNode(val) else: self._insert(val, self.root) def _insert(self, val, node): if val

【本文地址】

公司简介

联系我们